Some Heuristics for Makespan Minimization in Permutation Flow-Shop

• Autorzy: Alexandre Dolgui , Dmitry Ofitserov
• Języki publikacji: EN

Abstrakty

EN

This paper deals with the study of makespan optimization for the flow-shop production systems with or without infinite buffers between machines. Two scheduling algorithms are presented. They are based on several ideas from global optimization for continuous functions. In particular, ψ-transform technique is employed. This is a very interesting research direction to find heuristics with solid theoretical foundations and with a possibility to estimate subsequently their error. Consequently, problems of real size and actual complexity can be dealt with a certain confidence in the quality of the results. The algorithms proposed include also the Petrov matrix and the Gilmore-Gomory methods. The effciency of the algorithms proposed is illustrated with numerical tests on examples known in literature and on randomly generated tests.(original abstract)

Słowa kluczowe

EN

Optimalization; Algorithms; Matrix; Heuristics

PL

Optymalizacja; Algorytmy; Macierze; Heurystyka

• Czasopismo: Management and Production Engineering Review
• Rocznik: 2010
• Tom: 1
• Numer: nr 4
• Strony: 19--25

Twórcy

autor

Alexandre Dolgui

• Ecole des Mines de Saint Etienne, France

autor

Dmitry Ofitserov

• World Bank, USA

Bibliografia

• Tanaev V.S., Gordon V.S. and Shafranski Y.M., Scheduling Theory. Single-Stage Systems, Kluwer Academic Publishers, 1994.
• Nigmatullin R.G., Complexity of Approximate Methods for Combinatorial Problems, Soviet Mathematical Doklady, 16, 1199-1203, 1975.
• Chu C. and Proth J.-M., L'ordonnancement et ses applications, Masson, Paris, 1996.
• Johnson S.M., Optimal two-and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68, 1954.
• Proust C., Influence des idées de S.M. Johnson sur la résolution de problémes d'ordonnancement de type n/m/F, contraintes diverses/Cmax, Working paper, Laboratoire d'Informatique, Universit´e de Tours, France, 1989.
• Osman I.H., Potts C.N., Simulated annealing for permutation flow-shop scheduling, Omega, 17, (6), 551-557, 1989.
• Ladhari T., and Haouari M., A computational study of the permutation flow shop problem based on a tight lower bound, Computers & Operations Research, 32 (7), 1831-1847, 2005.
• Zobolas G.I., Tarantilis C.D., and Ioannou G., Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm, Computers & Operations Research, 36 (4), 1249-1267, 2009.
• Laha D., and Sarin S.C., A heuristic to minimize total flow time in permutation flow shop, Omega, 37 (3), 734-739, 2009.
• Ribas I., Companys R., and Tort-Martorell X., Comparing three-step heuristics for the permutation flow shop problem, Computers & Operations Research, 37 (12), 2062-2070, 2010.
• Tanaev V.S., Sotskov Y.N. and Strusevitch V.A., Scheduling Theory. Multi-Stage Systems, Kluwer Academic Publishers, 1994.
• Petrov V., Manufacturing System Planning, Mashinostroenie, Leningrad, 1966a - in Russian.
• Petrov V., Flow Line Group Production Planning. Business Publications, London, 1966b.
• Lvov Y., Research of Optimal Flow-shop Scheduling Using Stochastic Methods, Works of the Institute for Engineering and Economy of Leningrad, 62/2, 15-33, 1966 - in Russian.
• Campbell H.G., Dudek R.A. and Smith M.L., A Heuristic Algorithm for the n Job, m Machine Sequencing Problem, Management Science, 16, B630-B637, 1970.
• Ofitserov D., Computer-Aided Production Planning in an Automatic Factory, Ph.D. Dissertation, Institute of Engineering Cybernetics, Minsk, Belarus, 1987.
• Taha H.A., Operations research: An Introduction, MacMillan Publishing Co, Inc. New York, 1982.
• Feigin L., Statistic Estimation of Optimum in the General Scheduling Problem, Izvestia AN SSSR, Engineering Cybernetics, 2, 221-224, 1982 - in Russian.
• Chichinadze V.K., The ψ-transform for Solving Linear and Non-Linear Programming Problems, Automatica, 5, 347-355, 1969.
• Dolgui A. and Ofitserov D., A Stochastic Method for Discrete and Continuous Optimization in Manufacturing Systems, Journal of Intelligent Manufacturing, 8 (5), 405-413, 1997.
• Dolgui A., and Sysoev V., Une heuristique d'optimisation globale basée sur la ψ- transformation, RAIRO Operations Research, 37, 119-141, 2003.
• Boender C.G.E., Rinnooy Kan A.H.G., Timmer G.T. and Stougie L., A Stochastic Method for Global Optimization, Mathematical Programming, 22, 125-140, 1982.
• Artamonov I.M., An Algorithm for the Resolution of the Johnson-Bellman Problem, Research in Mathematics, Kichinev, 68, 3-10, 1982 - in Russian.
• Gilmore P.C. and Gomory R.E., Sequencing a one State-Variable Machine: A Solvable Case of the Travelling Salesman Problem, Operations Research, 12, 655-659, 1964.
• Levner E.B., Optimal Planning for Many Machines, Automation and Remote Control, Moskow, 12, 94-100, 1973 - in Russian.
• Papadimitriou C.H. and Kanellakis P.C., Flow-Shop Scheduling with Limited Temporary Storage, Journal of the Association for Computing Machinery, 27, 533-549, 1980.