Linear programming & metaheuristic approach for scheduling in the hybrid flowshop with resource constraints

• Autorzy: Figielska E.
• Języki publikacji: EN

Abstrakty

EN

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and additional renewable resources. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which join the linear programming based procedures with metaheuristic algorithms: genetic, simulated annealing and tabu search algorithm. The performance of the proposed algorithms is experimentally evaluated by comparing the solutions with a lower bound on the optimal makespan. Results of a computational experiment show that these algorithms are able to produce good solutions in short computation time and that the metaheuristics significantly improve the results for the most difficult problems.

Słowa kluczowe

EN

flowshop; parallel machines; resource constraints; heuristics; linear programming; genetic algorithms; simulated annealing; tabu search

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2011
• Tom: Vol. 40, no 4
• Strony: 1209--1230
• Opis fizyczny: Bibliogr. 34 poz., wykr.

Twórcy

autor

Figielska E.

• Warsaw School of Information Technology Newelska 6, 01--447 Warsaw, Poland,

Bibliografia

• Aarts, E.H.L. and van Laarhoven, P.J.M. (1987) Simulated Annealing: Theory and Applications. Reidel, Dordrecht.
• Adler, L., Fraiman, N., Kobacker, E., Pinedo, M., Plotnicoff, T.P. and Wu, T.P. (1993) A scheduling support system for the packaging industry. Operations Research 41(4), 641-648.
• Aldowaisan,T. and Allahverdi,A. (2003) New heuristics for no-wait flowshops to minimize makespan. Computers & Operations Research 30, 1219-1231.
• Błażewicz, J., Cellary,W., SłowińskiR. and Węglarz, J. (1987) Scheduling under Resource Constraints: Deterministic Models. J.C. Baltzer, Basel.
• Brah, S.A. (1988) Scheduling in a flow shop with multiple processors. Unpublished Ph.D. Dissertation, University of Huston, Huston, TX.
• Brah, S.A. and Loo, L.L. (1999) Heuristics for scheduling in a flow shop with multiple processors. European Journal of Operational Research 113, 113-122.
• Chen, B. (1995) Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. Journal of the Operational Research Society 46, 234-244.
• Cheng, T.C.E., Gupta, J.N.D. and Wang, G. (2000) A review of flowshop scheduling research with setup times. Production and Operations Management 9, 262-282.
• Crama, Y. (1997) Combinatorial optimization models for production scheduling in automated manufacturing systems. European Journal of Opera tional Research 99, 136-153.
• De Werra, D. (1984) Preemptive scheduling, linear programming and Network flows. Place country-regionSIAM Journal on Algebraic and Discrete Methods 5, 11-20.
• De Werra, D. (1988) On the two-phase method for preemptive scheduling. European. Journal of Operational Research 37, 227-235.
• Figielska, E. (20080 A new heuristic for scheduling the two-stage flowshop with additional resources. Computers and Industrial Engineering 54, 750-763.
• Figielska, E. (2009) A genetic algorithmand 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 56, 142-152.
• Glover, F. (1989) Tabu search. Part 1. ORSA Journal of Computing 1, 190-206.
• Goldberg, D.E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley.
• Goldberg, D.E., Korb, D. and Deb, K. (1989) Messy genetic algorithms: motivation, analysis, and first results. Complex Systems 3, 493-530.
• Gupta, J.N.D. (1988) Two stage hybrid flowshop scheduling problem. Journal of Operational Research Society 39, 359-364.
• Gupta, J.N.D. and Stafford, E.F. Jr. (2006) Flowshop scheduling research after five decades. European Journal of Operational Research 169, 699-711.
• Haouari, M. and M’Hallah, R. (1997) Heuristic algorithms for the twostage hybrid flowshop problem. Operations Research Letters 21, 43-53.
• Holland, J.H. (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.
• Hoogeveen, J.A., Lenstra, J.K. and Veltman,B. (1996) Preemptive scheduling in a two-stage multiprocessor flow shop is NP.-hard. European Journal of Operational Research 89, 172-175.
• Jin, Z., Yang, Z. and Ito, T. (2006) Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem. International Journal of Production Economics 100, 322-334.
• Kellerer, H. and Strusevich, V.A. (2003) Scheduling parallel dedicated machines under a single non-shared resource. European Journal of Operational Research 147, 345-364.
• Linn, R. and Zhang,W. (1999) Hybrid flow shop scheduling: a survey. Computers and Industrial Engineering 37, 57-61.
• Low, C. (2005) Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Computers and Operations Research 32, 2013-2025.
• Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E. (1953) Equation of state calculations by fast computing machines. Journal of Chemical Physics 21(6), 1087-1092.
• Oguz, C. and Ercan, M.F. (2005) A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Journal of Scheduling 8, 323-351.
• Salvador, M.S. (1973) A solution of a special class of flowshop scheduling problems. In: S.E. Elmaghraby, ed., Symposium of the Theory of Scheduling and Its Applications. Springer-Verlag, New York, 83-91.
• Serafini, P. (1996) Scheduling jobs on several machines with the job splitting property. Operations Research 44 (4), 617-628.
• Słowiński,R. (1980) Two approaches to problems of resource allocation among project activities - A comparative study. Journal of Operational Research Society 31, 711-723.
• Słowiński, R. (1981) L’ordonanacement des taches preemptives sur les processeurs independants en presence de ressources supplementaires. RAIRO Inform./ Comp. Science, 15, 2, 155-166.
• Suresh, V. (1997) A note on scheduling of two-stage flow shop with multiple processors. International Journal of Production Economics 49, 77-82
• Vignier, A., Billaut, J.C. and Proust, C. (1999) Les problemes d’ordonnancement de type flow-shop hybride: État de l’art. RAIRO Recherche opérationnelle 33(2), 117-83.
• Wardono, B. and Fathi, Y. (2004) A tabu search algorithm for the multistage parallel machine problem with limited buffer capacities. European Journal of Operational Research 155, 380-401.