Complexity of flow shop scheduling problems with transportation constraints |
| |
| Institution: | 1. Departament d''Organització d''Empreses, DOE – ETSEIB, Universitat Politècnica de Catalunya BarcelonaTech, Avda. Diagonal, 647, 7th Floor, 08028 Barcelona, Spain;2. CDE – EPSEB, Universitat Politècnica de Catalunya BarcelonaTech, Gregorio Marañón 44-50, 3rd Floor, 08028 Barcelona, Spain;3. Departament de Estadística e Investigación Operativa, ETSEIB, Universitat Politècnica de Catalunya BarcelonaTech, Avda. Diagonal, 647, 6th Floor, 08028 Barcelona, Spain;1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China;2. Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing, China |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
