Heuristic and stochastic methods in optimization |
| |
| Affiliation: | 1. Vilnius Gediminas Technical University, Sauletekio st 11, Vilnius, Lithuania;2. DIKU - Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen, Denmark;1. Otto-von-Guericke-University Magdeburg, Faculty of Economics and Management, Management Science, P.O. Box 4120, 39016 Magdeburg, Germany;2. Department of Industrial & Systems Engineering, University of Florida, 303 West Hall, Gainesville, FL 32611-6595, USA;3. Department of Industrial Engineering, Bogaziçi University, 34342, Bebek-Istanbul, Turkey;4. Koç University, Department of Industrial Engineering, 34450 Sariyer-Istanbul, Turkey;5. University of Vienna, Department of Management Science, Bruenner Strasse 72, 1210 Vienna, Austria;1. Graduate School of Systems, Information and Engineering, University of Tsukuba, Tsukuba Science City, Ibaraki 305-8573, Japan;2. Faculty of Engineering, Information and Systems, University of Tsukuba, Tsukuba Science City, Ibaraki 305-8573, Japan;1. Zaragoza Logistics Center, Spain;2. IESE Business School, Spain;3. Jiangsu Normal University, China;4. International Business College, Dongbei University of Finance and Economics, Dalian, China;1. CNRS, IRIT, Toulouse, France;2. CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France;3. IKERBASQUE, Basque Foundation for Science, 48011 Bilbao, Spain;4. UPV/EHU, University of the Basque Country, 20018 Donostia, Spain;5. Univ. de Toulouse, INP, LAAS, F-31400 Toulouse, France;1. Insight Centre for Data Analytics, University College Cork, Cork, Ireland;2. Department of Business Administration, İzmir University of Economics, İzmir, Turkey;3. Department of Computer Engineering, İzmir University of Economics, İzmir, Turkey;4. Department of Industrial Engineering, İzmir University of Economics, İzmir, Turkey |
| |
| Abstract: | The shifting bottleneck (SB) heuristic is among the most successful approximation methods for solving the job shop problem. It is essentially a machine based decomposition procedure where a series of one machine sequencing problems (OMSPs) are solved. However, such a procedure has been reported to be highly ineffective for the flow shop problems. In particular, we show that for the 2-machine flow shop problem, the SB heuristic will deliver the optimal solution in only a small number of instances. We examine the reason behind the failure of the machine based decomposition method for the flow shop. An optimal machine based decomposition procedure is formulated for the 2-machine flow shop, the time complexity of which is worse than that of the celebrated Johnson’s rule. The contribution of the present study lies in showing that the same machine based decomposition procedures which are so successful in solving complex job shops can also be suitably modified to optimally solve the simpler flow shops. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
