并行机生产与具有等待时间限制的成批运输协调调度问题

研究了运输阶段具有等待时间限制的成批运输与并行机生产协调调度问题，目标为最小化制造期与运输费用之和．通过复杂性分析，证明其是强NP难问题，提出启发式算法并证明其最坏情况性能比为4—1／m．当一个运输批必须在同一台机器加工时，证明其也是强NP难问题．将加工时间与等待时间限定值进行比较，分别提出两个启发式算法，并证明其最坏...

Scheduling production on parallel machines and batch delivery withlimited waiting time constraint

This paper studies a coordinated scheduling problem of production on parallel machines and batch delivery where
the finished jobs must be deliveried in a limited time. The objective is to minimize the sum of the makespan and the total
delivery cost. Through the complexity analysis, it is proved that the problem is strongly NP-hard, and a heuristic algorithm
is provided with the worst-case ratio 4 − 1/m??. A special case is also considered, where the jobs in a batch delivery must be
processed on the same machine. For this case, it is proved that the problem is strongly NP-hard, and two heuristic algorithms
are provided with the worst-case ratio 2−1/m?? and 4−1/m?? according to the comparation with the limited waiting time and
the processing times, respectively.