文献类型：期刊文献

英文题名：Routing open shop and flow shop scheduling problems

作者：Yu, Wei[1];Liu, Zhaohui[1];Wang, Leiyang[1];Fan, Tijun[2]

机构：[1]E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China;[2]E China Univ Sci & Technol, Inst Operat & Supply Chain Management, Shanghai 200237, Peoples R China

年份：2011

卷号：213

期号：1

起止页码：24

外文期刊名：EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

收录：;EI(收录号：20111913960905);WOS:【SCI-EXPANDED(收录号:WOS:000291082100003)】；

基金：The authors are grateful to the anonymous referees for their helpful comments. This research is supported by the National Natural Science Foundation of China (Grants No. 10771067 and No. 70871038) and the Fundamental Research Funds for the Central Universities of China.

语种：英文

外文关键词：Scheduling; Routing; Open shop; Flow shop; Complexity; Approximation algorithm

摘要：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. (C) 2011 Elsevier B.V. All rights reserved.