A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times |
| |
| Authors: | Jinliang Cheng George Steiner Paul Stephenson |
| |
| Affiliation: | 1. Utrecht University, Netherlands;2. University of Sydney, Australia;1. FIQ, Universidad Nacional del Litoral, Santiago del Estero 2829, Santa Fe 3000, Argentina;2. CIEM (Universidad Nacional de Córdoba, CONICET), Medina Allende s/n, Córdoba 5000, Argentina;3. INTEC (Universidad Nacional del Litoral, CONICET),Güemes 3450, Santa Fe 3000, Argentina;1. Graduate School of Engineering, University of Fukui, 3-9-1 Bunkyo, Fukui 910-8507, Japan;2. Physico Chemical Fundamentals of Combustion, RWTH Aachen University, Templergraben 55, Aachen D52056, Germany;3. Institut für Technische Verbrennung, RWTH Aachen University, Templergraben 64, D52056 Aachen, Germany;4. Physikalisch-Technische Bundesanstalt, Bundesallee 100, Braunschweig D38116, Germany;1. Department of Industrial and Management Systems Engineering, Kuwait University, Kuwait;2. Department of Mathematics and Natural Sciences, Gulf University for Science and Technology, Kuwait;1. School of Science, Guizhou Minzu University, Guiyang 550025, China;2. Collaborative Innovation Center of Biomass Energy, Henan Province, Henan Agricultural University, Zhengzhou 450002, China;3. Key Laboratory of Low-grade Energy Utilization Technologies and Systems, Ministry of Education of China, Chongqing University, Chongqing 400044, China;4. State Key Laboratory of Pulp and Paper Engineering, South China University of Technology, Guangzhou 510640, China |
| |
| Abstract: | We consider the three-machine permutation flow-shop scheduling problem with release times where the objective is to minimize the maximum completion time. A special solvable case is found for the F2/rj/Cmax problem, which sharpens the boundary between easy and hard cases and can be used to compute a tight lower bound for our problem. Two dominance rules are generalized and applied to generating initial schedules, directing the search strategy and decomposing the problem into smaller ones. The branch and bound algorithm proposed here combines an adaptive branching rule with a fuzzy search strategy to narrow the search tree and lead the search to an optimal solution as early as possible. Our extensive numerical experiments have led to a classification of ‘easy' vs. ‘hard' problems, dependent only on the relative size of the release times. The algorithm has quickly solved approximately 90% of the hardest test problem instances with up to 200 jobs and 100% of the large problems classified as easy. |
| |
| Keywords: | Permutation flow shop Makespan Release times |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
