Solving a flowshop scheduling problem with additional resource constraints

• Autorzy: Figielska E.
• Konferencja: Evolutionary Computation and Global Optimization 2006 / National Conference (9 ; 31.05-2.06.2006 ; Murzasichle, Poland)
• Języki publikacji: EN

Abstrakty

EN

The paper considers the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machinne at the second stage. At the first stage jobs require some amounts of additional renewable resources. The objective is the minimization of the makespan. The problem is NP-hard. A heuristic which combines column generation technique with a genetic algorithm is proposed. Several problems with randomly generated parameters are solved. The results indicate that the heuristic is a promising tool for solving the considered problem.

Słowa kluczowe

EN

heuristics; algorithm; two-stage flowshop scheduling problem; parallel unrelated machines; genetic algorithm

PL

heurystyka; algorytm; algorytm genetyczny

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2006
• Tom: z. 156
• Strony: 139--146
• Opis fizyczny: Bibliogr. 17 poz., tab., wykr.

Twórcy

autor

Figielska E.

• Mila College School of Higher Education in Warsaw, Warsaw, Poland,

Bibliografia

• [1] Barnhart, C.E. Johnson, G. Nemhauser, M. Savelsbergh and P. Yance (1998). Branch and price: column generation for solving huge integer problems. Oper. Res. 46, 316-329.
• [2] 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
• [3] 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.
• [4] Chen, Z.-L. and C.-Y. Lee (2002). Parallel machine scheduling with a common due window. Europ. J. of Opernl Res., 136, 512-527.
• [5] Dantzig, G.B. and P. Wolfe (1960). Decomposition principle for linear programs. Oper. Res. 8, 101-111.
• [6] Figielska, E. (1999). Preemptive scheduling with changeovers: using column generation technique and genetic algorithm. Comp. and Ind. Engin. 37, 63-66.
• [7] Gilmore, P.C. and R.E. Gomory (1961). A linear programming approach to the cutting-stock 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] Ogŭz, C, M.F. Ercan, T.C.E. Cheng and Y.F. Fung (2003). Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow shop. Europ. J. of Opernl Res. 149, 390-403.
• [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] Słowiński, R. (1980). Two aproaches to problems of resource allocation among project activities - A comparative study. J. Opl Res. Soc. 31,711-723.
• [17] Suresh, V (1997). A note on scheduling of two-stage flow shop with multiple processors. Int. J. of Prod. Econ. 49, 77-82.