Complexity of flow shop scheduling problems with transportation constraints
Complexity of flow shop scheduling problems with transportation constraints
复制标题
DOI：
10.1016/j.ejor.2003.03.002
复制
发表时间：
2005-02
期刊：
影响因子：
--
通讯作者：
A. Soukhal;A. Oulamara;P. Martineau
中科院分区：
文献类型：
--
作者：
A. Soukhal;A. Oulamara;P. Martineau
在大多数制造和分销系统中，半成品作业通过自动导引车、机器人和输送机等运输工具从一个加工设施转移到另一个加工设施，而成品作业通过卡车等车辆交付给仓库或客户。本文研究了考虑运输的两台机器流水车间调度问题。完成的工作从加工厂转移，并通过卡车交付给客户。在这些模型中明确考虑了运输能力和运输时间。通过分析流水作业问题的复杂性，研究了流水作业问题。对于最大完工时间的目标函数，我们证明了这个问题是强NP-困难的能力时，卡车的限制为两个或三个部分，在每台机器的输出无限的缓冲区。这个问题与额外的限制，如阻塞，也被证明是强NP难的。
In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as Automated Guided Vehicles, robots and conveyors, and finished jobs are delivered to warehouses or customers by vehicles such as trucks. This paper investigates two-machine flow shop scheduling problems taking transportation into account. The finished jobs are transferred from the processing facility and delivered to customers by truck. Both transportation capacity and transportation times are explicitly taken into account in these models. We study the class of flow shop problems by analysing their complexity. For the makespan objective function, we prove that this problem is strongly NP-hard when the capacity of a truck is limited to two or three parts with an unlimited buffer at the output of the each machine. This problem with additional constraints, such as blocking, is also proven to be strongly NP-hard.