An Ant Colony Optimization Algorithm for Scheduling Parallel Machines with Sequence-Dependent Setup Costs

• Autorzy: Figielska E.

Warianty tytułu

PL

Zastosowanie algorytmu mrówkowego do szeregowania zadań na maszynach równoległych z uwzględnieniem kosztów przezbrojeń zależnych od kolejności zadań

• Języki publikacji: EN

Abstrakty

EN

The paper addresses the problem of scheduling preemptive jobs on parallel unrelated machines in the presence of renewable resource constraints and sequence-dependent setup costs. The objective is to minimize the weighted sum of makespan and setups. The problem is known to be NP-hard. To solve this problem, a heuristic is proposed which uses column generation technique and an ant colony optimization algorithm. The results of a computational experiment indicate that the heuristic is able to produce good results in reasonable computation time.

PL

Artykuł dotyczy zagadnienia szeregowania zadań podzielnych na równoległych dowolnych maszynach z uwzględnieniem ograniczeń na dostępność zasobów odnawialnych oraz kosztów przezbrojeń zależnych od kolejności wykonywania zadań. Celem jest minimalizacja ważonej sumy czasu trwania harmonogramu i przezbrojeń. Zagadnienie należy do klasy problemów NP-trudnych. W celu jego rozwiązania, zaproponowany został algorytm heurystyczny, wykorzystujący technikę generacji kolumn, oraz algorytm mrówkowy. Wyniki eksperymentu obliczeniowego wskazują, że algorytm ten jest zdolny dostarczyć dobrej jakości wyniki w rozsądnym czasie.

Słowa kluczowe

EN

ant colony optimization; unrelated machines; sequence-dependent setup costs; resource constraints

PL

algorytm mrówkowy; dowolne maszyny; koszty przezbrojeń; kolejność zadań; ograniczenia zasobowe

• Wydawca: Warszawska Wyższa Szkoła Informatyki
• Czasopismo: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
• Rocznik: 2013
• Tom: nr 9
• Strony: 15--26
• Opis fizyczny: Bibliogr. 16 poz., tab., wykr.

Twórcy

autor

Figielska E.

• Warsaw School of Computer Science

Bibliografia

• [1] Fortemps O., Ost C., Pirlot M., Teghem J., Tuyttens D., Using metaheuristics for solving a production scheduling problem in a chemical firm, “International Journal of Production Economics” 1996, Vol. 46-47 (13), s. 13-26
• [2] Sherali H.D., Sarin S.C., Kodialam M.S, Models and algorithm for a two stage production process, “Production Planning and Control” 1990, Vol.1 (1), s. 27-39
• [3] Serafini P., Scheduling jobs on several machines with the job splitting property, “Operations Research” 1996, Vol. 44 (4), s. 617-628
• [4] Ruiz R., Maroto C., A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility, “European Journal of Operational Research” 2006, Vol. 169, s. 781-800
• [5] Allahverdi A., Ng C.T., Cheng T.C.E., Kovalyov M.Y., A survey of scheduling problems with setup times or costs, “European Journal of Operational Research” 2008, Vol. 187, s. 985-1032
• [6] Rocha P.L., Ravetti M.G., Mateus G.R., Pardalos P.M., Exact algorithms for scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times, “Computers & Operations Research” 2008, Vol. 35 (4), s. 1250-1264
• [7] Driessel R., Mönch L., Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times, “Computers & Industrial Engineering” 2011, Vol. 61 (2), s. 336-345
• [8] Słowiński R., Two approaches to problems of resource allocation among project activities - A comparative study, “Journal of Operational Research Society” 1980, Vol. 31, s. 711-723
• [9] Werra D. De, On the two-phase method for preemptive scheduling, “European Journal of Operational Research” 1988, Vol. 37, s. 227-235
• [10] Figielska E., Preemptive scheduling with changeovers: using column generation technique and genetic algorithm, “Computers and Industrial Engineering” 1999, Vol. 37, s. 3-66
• [11] Dantzig G.B., Wolfe P., Decomposition principle for linear programs, “Operations Research” 1960, Vol. 8, s. 101-111
• [12] Gilmore P.C., Gomory R.E., A linear programming approach to the cutting-stock problem, “Operations Research” 1961, Vol. 9, s. 849-859
• [13] Chen Z.-L., Lee C.-Y., Parallel machine scheduling with a common due window, “European Journal of Operational Research” 2002, Vol. 136, s. 512-527
• [14] Figielska E., A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources, “Computers and Industrial Engineering” 2009, Vol. 56, s. 142-151
• [15] Dorigo M., Maniezzo V., Colorni A., Ant system: optimization by a colony of cooperating agents, “IEEE Transactions on Systems, Man and Cybernetics” 1996, Vol. 26 (1), s. 29-41
• [16] Mohan B.C., Baskaran R., A survey: Ant Colony Optimization based recent research and implementation on several engineering domain, “Expert Systems with Applications” 2012, Vol. 39, s. 4618-4627