PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Some heuristics for makespan minimization in permutation flow-shop

Identyfikatory
Warianty tytułu
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.
Twórcy
autor
autor
  • Ecole des Mines de Saint-Etienne, 158 cours Fauriel, 42023 Saint-Etienne Cedex, France, phone: (+33) 4 77 42 01 66, dolgui@emse.fr
Bibliografia
  • [1] Tanaev V.S., Gordon V.S. and Shafranski Y.M., Scheduling Theory. Single-Stage Systems, Kluwer Academic Publishers, 1994.
  • [2] Nigmatullin R.G., Complexity of Approximate Methods for Combinatorial Problems, Soviet Mathematical Doklady, 16, 1199–1203, 1975.
  • [3] Chu C. and Proth J.-M., L’ordonnancement et ses applications, Masson, Paris, 1996.
  • [4] Johnson S.M., Optimal two-and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68, 1954.
  • [5] 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.
  • [6] Osman I.H., Potts C.N., Simulated annealing for permutation flow-shop scheduling, Omega, 17, (6), 551-557, 1989.
  • [7] 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.
  • [8] 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.
  • [9] Laha D., and Sarin S.C., A heuristic to minimize total flow time in permutation flow shop, Omega, 37 (3), 734-739, 2009.
  • [10] 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.
  • [11] Tanaev V.S., Sotskov Y.N. and Strusevitch V.A., Scheduling Theory. Multi-Stage Systems, Kluwer Academic Publishers, 1994.
  • [12] Petrov V., Manufacturing System Planning, Mashinostroenie, Leningrad, 1966a - in Russian.
  • [13] Petrov V., Flow Line Group Production Planning. Business Publications, London, 1966b.
  • [14] 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.
  • [15] 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.
  • [16] Ofitserov D., Computer-Aided Production Planning in an Automatic Factory, Ph.D. Dissertation, Institute of Engineering Cybernetics, Minsk, Belarus, 1987.
  • [17] Taha H.A., Operations research: An Introduction, MacMillan Publishing Co, Inc. New York, 1982.
  • [18] Feigin L., Statistic Estimation of Optimum in the General Scheduling Problem, Izvestia AN SSSR, Engineering Cybernetics, 2, 221-224, 1982 - in Russian.
  • [19] Chichinadze V.K., The ψ-transform for Solving Linear and Non-Linear Programming Problems, Automatica, 5, 347-355, 1969.
  • [20] 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.
  • [21] Dolgui A., and Sysoev V., Une heuristique d’optimisation globale basée sur la ψ- transformation, RAIRO Operations Research, 37, 119-141, 2003.
  • [22] 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.
  • [23] Artamonov I.M., An Algorithm for the Resolution of the Johnson-Bellman Problem, Research in Mathematics, Kichinev, 68, 3-10, 1982 - in Russian.
  • [24] 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.
  • [25] Levner E.B., Optimal Planning for Many Machines, Automation and Remote Control, Moskow, 12, 94-100, 1973 - in Russian.
  • [26] 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BAR0-0065-0035
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.