Minimizing makespan in general flow-shop scheduling problem using a GA-based improvement heuristic

• Autorzy: Semančo P.
• Języki publikacji: EN

Abstrakty

EN

In the paper an improvement heuristic is proposed for permutation flow-shop problem based on the idea of evolutionary algorithm. The approach employs constructive heuristic that gives a good initial solution. GA-based improvement heuristic is applied in conjunction with three well-known constructive heuristics, namely CDS, Gupta’s algorithm and Palmer’s Slope Index. The approach is tested on benchmark set of 10 problems range from 4 to 25 jobs and 4 to 30 machines. The results are also compared to the best-known lower-bound solutions.

Słowa kluczowe

EN

flow-shop production; evolutionary algorithm

• Wydawca: Polskie Towarzystwo Promocji Wiedzy ; Lublin University of Technology
• Czasopismo: Applied Computer Science
• Rocznik: 2011
• Tom: Vol. 7, no 1
• Strony: 57--64
• Opis fizyczny: Bibliogr. 22 poz., fig., tab.

Twórcy

autor

Semančo P.

• Technical University of Kosice, Slovakia

Bibliografia

• 1. ALLAHVERDI. A.. NG. C.T.. CHENG. T.C.E.. & KOVALYOV. M.Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research. 187. 985-1032.
• 2. BALAS. E.. & VAZACOPOULOS. A. (1998). Guided local search with shifting bottleneck for job shop scheduling. Management Science. 44 (2). 262-275.
• 3. BLUM. C.. & M. SAMPELS. (2004). An ant colony optimization algorithm for shop scheduling problems. Journal of Mathematical Modelling and Algorithms. 3(3). 285-308.
• 4. BRUCKER. P.. JURISCH. B.. & SIEVERS. B. (1994). A branch and bound algorithm for the job shop scheduling problem. Discrete Applied Mathematics. 49(1). 109-127.
• 5. CAMPBELL. H.G.. DUDEK. R.A.. & SMITH. M.L. (1970). A heuristic algorithm for the n job, m machine sequencing problem. Management Science. 16(10). 630-637.
• 6. DANNENBRING. D.G. (1977). An evaluation of flow shop sequencing heuristics. Management Science. 23(11). 1174-1182.
• 7. ENGIN. O.. & DOYEN. A. (2004). A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Generation Computer Systems. 20. 1083-1095.
• 8. GAREY. M.R.D.. JOHNSON. D.S.. & SETHI. R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research. 1. 117-129.
• 9. GENDREAU. M.. LAPORTE. G.. & SEMET. F. (1998). A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research. 106(2-3). 539-545. Elsevier.
• 10. GUPTA. J.N.D. (1972). Heuristic algorithms for multistage flowshop scheduling problem. AIIE Transactions. 4 (1). 11-18.
• 11. GUPTA. J.N.D. (1975). Analysis of combinatorial approach to flowshop scheduling problems.
• 12. HEJAZI. S.R.. & SAGHAFIAN. S. (2005). Flowshop scheduling problems with makespan criterion: a review. International Journal of Production Research. 43(14). 2895-2929.
• 13. HENDIZADEH. S.H.. ELMEKKAWY. T.Y.. & WANG. G.G. (2007). Bi-criteria scheduling of a flowshop manufacturing cell with sequence dependent setup time. European Journal of Industrial Engineering. 1. 391-413.
• 14. JOHNSON. S. M. (1954). Optimal two and three stage production schedules with set-up times. Naval Research Logistics Quarterly. 1. 61-68.
• 15. NAGAR. A.. HERAGU. S.S.. & HADDOCK. J. (1996). A combined branch-and-bound and genetic algorithm based approach for a flowshop-scheduling problem. Annal. Oper. Res. 63. 397-414.
• 16. NAWAZ. M.E.. ENSCORE. I.. & HAM. I. (1983). A heuristic algorithm for the m machine, n job flow shop sequence problem. OMEGA. 11 (1). 91-95.
• 17. NEPPALLI. V.R.. CHEN. C.L. & GUPTA. J.N.D. (1996). Genetic algorithms for the two-stage bicriteria flowshop problem. Eur. J. Oper. Res.. 95. 356–373.
• 18. OGBU. F.A.. & SMITH. D.K. (1990). The application of the simulated annealing algorithm to the solution of the n/m/Cmax owshop problem. Computers & Operations Research. 17. 3243-253.
• 19. PALMER. D. S. (1965). Sequencing jobs through a multi-stage process in the minimum total time – a quick method of obtaining a near optimum. Opers Res. Q.. 16. 101-107.
• 20. PINEDO. M. (2008). Scheduling: Theory. algorithms and Systems. Prentice Hall. New Jersey: Springer.
• 21. RIBAS. R.. LEISTEN. J.M. (2010). Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Computers and Operations Research. 37(8).1439-1454.
• 22. ZOBOLAS. G. I.. TARANTILIS. C. D.. & IOANNOU. G. (2009) Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers and Operations Research. 36 (4). 1249-1267.