An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan |
| |
| Authors: | Manzhan Gu Xiwen Lu Jinwei Gu |
| |
| Affiliation: | 1.School of Mathematics and Statistics,Shandong University,Weihai, Shandong,China;2.Department of Mathematics,East China University of Science and Technology,Shanghai,China;3.School of Mechanical,Electrical & Information Engineering, Shandong University, Weihai, Shandong,China;4.School of Mathematics,Shanghai University of Finance and Economics,Shanghai,China;5.College of Economics and Management,Shanghai University of Electric Power,Shanghai,China |
| |
| Abstract: | ![]()
This paper considers the large-scale mixed job shop scheduling problem with general number of jobs on each route. The problem includes ordinary machines, batch machines (with bounded or unbounded capacity), parallel machines, and machines with breakdowns. The objective is to find a schedule to minimize the makespan. For the problem, we define a virtual problem and a corresponding virtual schedule, based on which our algorithm TVSA is proposed. The performance analysis of the algorithm shows the gap between the obtained solution and the optimal solution is O(1), which indicates the algorithm is asymptotically optimal. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
