Combining a genetic algorithm with a column generation algorithm for solving a scheduling problem

• Autorzy: Figielska E.
• Konferencja: Evolutionary Computation and Global Optimization (10; Krajowa Konferencja Algorytmy Ewolucyjne i Optymalizacja Globalna; 11-13.06.2007; Będlewo, Poland)
• Języki publikacji: EN

Abstrakty

EN

This paper deals with the problem of minimal makespan scheduling in a two-stage flowshop with parallel unrelated machines and renewable resources at the first stage and a single machine at the second stage. A heuristic for solving this problem is developed which combines a genetic algorithm with a column generation algorithm. The results of a computational experiment show that the proposed heuristic requires almost three times less CPU time than the heuristic with a standard column generation algorithm, while producing the same quality solutions.

Słowa kluczowe

EN

genetic algorithm; computational experiment

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2007
• Tom: z. 160
• Strony: 71--78
• Opis fizyczny: Bibliogr. 19 poz., tab.

Twórcy

autor

Figielska E.

• Warsaw School of Computer Science Warsaw Poland,

Bibliografia

• [1] Brah, S.A. and L.L. Loo (1999). Heuristics for scheduling in a flow shop with multiple processors. Europ. J. of Opernl. Res. 113, 113-112
• [2] Chen, B. (1995). Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage, J. of Opernl. Res. Soc. 46, 234-244.
• [3] Dantzig, G.B. and P. Wolfe (1960). Decomposition principle for linear programs. Oper. Res. 8, 101-111.
• [4] Figielska, E (1999). Preemptive scheduling with change overs: using column generation technique and genetic algorithm, Computers and Industrial Engineering 37, 63-66.
• [5] Figielska, E. (2006). Solving a flowshop scheduling problem with resource constraints, Evolutionary Computation and Global Optimization, Prace naukowe PW, Elektronika 156, 139-146.
• [6] Figielska, E. (2006). Combining an optimizing method with a genetic algorithm to solve a flowshop scheduling problem with additional resources, Proceedings of the 11th IEEE International Conference on Emerging Technologies and Factory Automation, 1080-1086, Prague, Czech Republic.
• [7] Gilmore, P.C. and R.E. Gomory (1961). A linear programming approach to the cuttingstock problem, Oper. Res. 9, 849-859.
• [8] Goldberg D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley.
• [9] Gupta J.N.D. (1988). Two stage hybrid flowshop scheduling problem. J. of Opernl. Res. Soc. 39, 359-364.
• [10] Haouari, M. and R. M'Hallah (1997). Heuristic algorithms for the two-stage hybrid flowshop problem, Oper. Res. Let. 21, 43-53.
• [11] Holland J.H. (1975). Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI.
• [12] Hoogeveen J.A., J.K. Lenstra and B. Veltman (1996). Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. Europ. J. of Opernl. Res. 89, 172-175.
• [13] Linn, R, W. Zhang (1999). Hybrid flow shop scheduling: a survey. Comp. and Ind. Engin. 37, 57-61.
• [14] Nowicki, E., Smutnicki Cz. (1995). The flow shop with parallel machines: A tabu search approach. Europ. J. of Opernl. Res. 106, 226-253.
• [15] Ruiz, R., C. Maroto (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. Europ. J. of Opernl. Res. 169, 781-800.
• [16] Slowinski, R. (1980). Two approaches to problems of resource allocation among project activities - A comparative study. J. Opl. Res. Soc. 31, 711-723.
• [17] Slowinski, R. (1981), L'ordonanacement des taches preemptives sur les processeurs independants en presence de ressources supplementaires. RAIRO Inform./Comp. Science, vol. 15, No.2, 155-166.
• [18] Suresh, V (1997). A note on scheduling of two-stage flow shop with multiple processors. Int. J. of Prod. Econ. 49, 77-82
• [19] De Werra, D. (1988). On the two-phase method for preemptive scheduling. Europ. J. Of Opernl. Res. 37, 227-235.