Routing open shop and flow shop scheduling problems |
| |
Authors: | Wei Yu Zhaohui Liu Leiyang Wang Tijun Fan |
| |
Institution: | a Department of Mathematics, East China University of Science and Technology, Shanghai 200237, China;b Institute of Operations and Supply Chain Management, East China University of Science and Technology, Shanghai 200237, China |
| |
Abstract: | We consider a generalization of the classical open shop and flow shop scheduling problems where the jobs are located at the vertices of an undirected graph and the machines, initially located at the same vertex, have to travel along the graph to process the jobs. The objective is to minimize the makespan. In the tour-version the makespan means the time by which each machine has processed all jobs and returned to the initial location. While in the path-version the makespan represents the maximum completion time of the jobs. We present improved approximation algorithms for various cases of the open shop problem on a general graph, and the tour-version of the two-machine flow shop problem on a tree. Also, we prove that both versions of the latter problem are NP-hard, which answers an open question posed in the literature. |
| |
Keywords: | Scheduling Routing Open shop Flow shop Complexity Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|