Jednomaszynowy problem szeregowania zadań z przezbrojeniami

• Autorzy: Bożejko W. , Wodecki M.

Warianty tytułu

EN

Single machine scheduling problem with sequence-dependent setup times

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiamy algorytm populacyjny rozwiązywania jednomaszynowego problemu szeregowania zadań z przezbrojeniami, w którym należy zminimalizować sumę kosztów opóźnień. W literaturze jest on oznaczany przez 1 | s[ij] | sigma w[i]T[i] należy do klasy problemów silnie NP-trudnych. Wykonaliśmy obliczenia na reprezentatywnej grupie danych testowych, a otrzymane wyniki porównujemy z najlepszymi znanymi w literaturze. Dla wielu przykładów uzyskaliśmy poprawę najlepszych rozwiązań.

EN

In the paper we propose a population-based algorithm for solving single machine scheduling problem with total tardiness criterion and sequence-dependent setup times. It is represented by 1 | s[ij] | sigma w[i]T[i] in literature and it belongs to the strongly NP-hard class. Calculations on the representative group of benchmark instances were done and results were compared with the best known from literature. Obtained solutions were better than benchmark ones in many instances.

Słowa kluczowe

PL

problem jednomaszynowy; problem NP-trudny; szeregowanie zadań; algorytm ewolucyjny; algorytm hybrydowy

EN

single machine problem; NP-hard; scheduling; evolutionary algorithm; hybrid algorithm

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 143
• Strony: 21--26
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Bożejko W.

autor

Wodecki M.

• Instytut Informatyki, Automatyki i Robotyki Politechniki Wrocławskiej, 50-370 Wrocław, Wybrzeże Wyspiańskiego 27, tel. [phone],

Bibliografia

• 1. Armentano V.A., Mazzini R.: A genetic algorithm for scheduling on a single machine set-up times and due dates. Production Planning & Control, 11(7), 2000, p. 713-720.
• 2. Bożejko W., Wodecki M.: A hybrid evolutionary algorithm for the permutation optimization problem. ISDA 05, IEEE Computer Society, 2005, p. 326-331.
• 3. Cicirello V.A., Smith S.F.: Enhancing stochastic search performance by value-based randomization of heuristics. Journal of Heuristics, 11, 2005, p. 5-34.
• 4. Gagne C, Price W.L., Gravel M.: Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times. Journal of the Operational Research Society, 53, 2002, p.895-906.
• 5. Lee Y.H., Bhaskaran K., Pinedo M.: A heuristic to minimize the total weighted tardiness with sequence-dependent setups. HE Transactions, 29, 1997, p. 45-52.
• 6. Panwalkar S.S., Dudek R.A., Smith M.L.: Sequencing research and the industrial scheduling problem. Symposium on the theory of scheduling and its applications (ed. Elmaghraby S.E.), Springer-Verlag, Berlin 1973.
• 7. Sun X., Noble J.S., Klein CM.: Single-machine scheduling with sequence dependent setup to minimize total weighted squared tardiness. HE Transactions, 31, 1999, p. 113-124.
• 8. Tan K.C., Narasimban R., Rubin PA., Ragatz G.L.: A comparison on four methods for minimizing total tardiness on a single processor with sequence dependent setup times. Omega, 28, 2000, p. 313-326.