An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan
An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan
复制标题
DOI：
10.1007/s10878-015-9974-7
复制
发表时间：
2015-11
影响因子：
1
通讯作者：
Manzhan Gu;Xiwen Lu;Jinwei Gu
中科院分区：
文献类型：
--
作者：
Manzhan Gu;Xiwen Lu;Jinwei Gu
本文研究了每条路线上工件数为一般的大规模混合车间调度问题。问题包括普通机器、批处理机（有界或无界容量）、并行机和故障机器。目标是找到一个时间表，以尽量减少完工时间。针对该问题，我们定义了一个虚拟问题和相应的虚拟调度，并在此基础上提出了算法TVSA。对算法的性能分析表明，所得解与最优解之间的差距为O（1），表明算法是渐近最优的。
This paper considers the large-scale mixed job shop scheduling problem withgeneralnumber 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 algorithmTVSAis proposed. The performance analysis of the algorithm shows the gap between the obtained solution and the optimal solution isO(1), which indicates the algorithm is asymptotically optimal.