曹立思，国际商学院，讲师，管理学博士，生产运营管理，Two Parallel Machines Scheduling with Two-Vehicle Job Delivery to Minimize Makespan；发表期刊《Complexity》，ISSN：1076-2787，SCI二区，文章刊发在2020年第1期。

英文摘要

Two Parallel Machines Scheduling with Two-Vehicle Job Delivery to Minimize Makespan

（考虑订单完成时间的双机加工和分批次运输协作排序问题研究）

A problem of parallel machine scheduling with coordinated job deliveries is handled to minimize the makespan. Different jobs call for dissimilar sizes of storing space in the process of transportation. Arange of jobs of one customer in the problem have priority to be processed on two identical parallel machines without preemption and then delivered to the customer by two vehicles in batches. For this NP-hard problem, we first prove that it is impossible to have a polynomial heuristic with a worst-case performance ratio bound less than 2 unless P=NP. Thereafter, we develop a polynomial heuristic for this problem, the worst-case ratio of which is bounded by 2.

中文摘要：本文研究了在考虑加工与运输协同调度的平行机排序问题中，如何实现完成所有工件加工和运输所需时间的最小化。在此排序问题中，需要先安排客户的所有工件由两台平行机进行加工，再由两辆车分批次送达客户。由于工件的尺寸不同且车辆有容量限制，因此在运输过程中需要考虑工件如何分批装载。本文首先指出该排序问题是一个NP难问题，然后证明了不存在最坏情况界小于2的多项式时间启发式算法。通过分析该问题的最优解性质，本文设计了一个多项式时间启发式算法，并从理论上证明了该算法的最坏情况界为2。