Two-stage open shop scheduling with a bottleneck machine |
| |
| Institution: | 1. Faculty of Business Information, Shanghai Business School, Shanghai 200235, PR China;2. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Kowloon, Hong Kong;3. Flaginfo-Sufe Joint AI Lab, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, PR China;4. School of Management and E-Business, Contemporary Business and Trade Research Center, Zhejiang Gongshang University, Hangzhou 310018, PR China;5. Business School, University of Shanghai for Science and Technology, Shanghai 200093, PR China |
| |
| Abstract: | It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P≠NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m⩾2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
