Problem gniazdowy z ograniczeniem bez czekania. Algorytmy konstrukcyjne

• Autorzy: Makuchowski M.

Warianty tytułu

EN

The no-wait job shop problem. Heuristic algorithms

• Języki publikacji: PL

Abstrakty

PL

W pracy opisana jest pewna procedura konstrukcji rozwiązania dla problemu gniazdowego z ograniczeniem bez czekania. Pokazano także sposób jej wykorzystania do budowy bardzo wydajnych algorytmów zarówno konstrukcyjnych, jak i popraw. W pracy prezentuje się algorytmy konstrukcyjne, bazujące na wspomnianej procedurze. Ich efektywność przebadano na dobrze znanych w literaturze przykładach testowych.

EN

This paper describes some solution constructive procedure dedicated to a job shop problem with the no-wait constraint and a makespan criterion. Very efficient heuristic algorithms based on the presented procedure are discussed. The efficiency of the algorithms is tested on well-known literature benchmarks.

Słowa kluczowe

PL

problem gniazdowy; problem NP-trudny; algorytm konstrukcyjny; algorytm HBB; algorytm HNEH

EN

no-wait job shop problem; NP-hard; heuristic algorithm; HBB algorithm; HNEH algorithm

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2008
• Tom: z. 150
• Strony: 167--173
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Makuchowski M.

• Politechnika Wrocławska,

Bibliografia

• 1. Wismer D.A.: Solution of the flowshop scheduling-problem with no intermediate queues. Operations Research. 20, 1972, p. 689.
• 2. Hall N., Sriskandarajah C: A survey of machine scheduling-problems with blocking and no-wait in process. Operations Research. 44(3), 1996, p. 510.
• 3. Lenstra J., Rinnooy Kan A.: Computational complexity of discrete optimization problems. Annals of Discrete Mathematics, 4, 1979, p. 121.
• 4. Mascis A., Pacciarelli D.: Job shop scheduling with blocking and no-wait constraints, European Journal of Operational Research. 142(3), 2002, p. 498.
• 5. Macchiaroli R., Mole S., Riemma S.: Modelling and optimization of industrial manufacturing processes subject to no-wait constrains, International Journal of Production Research, 37(11), 1999, p. 2585.
• 6. Raaymakers W., Hoogeveen J.: Scheduling multipurpouse batch process industries with no-wait restrictions by simulated annealing, European Journal of Operational Research. 126, 2000, p. 131.
• 7. Schuster C, Framinan J.: Approximative procedures for no-wait job shop scheduling, Operations Research Letters. 31, 2003, p. 308.
• 8. Graham R., Lawler E., Lenstra J., Rinnooy Kan A.: Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 1979, p. 287.
• 9. Hansen R, Maldenovic N.: Variable neighborhood search. Principles and applications, European Journal of Operational Research. 130, 2001, p. 449
• 10. Nawaz M., Enscore Jr.E.E., Ham I.: A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, OMEGA International Journal of Management Science, 11, 1983, p. 91