带单服务器和相同加工时间的流水作业排序问题

数学物理学报 ›› 2012, Vol. 32 ›› Issue (6): 1121-1125.

带单服务器和相同加工时间的流水作业排序问题

时凌¹, 程学光²

1.湖北民族学院数学系湖北恩施 445000;
2.武汉大学数学与统计学院武汉 430072

收稿日期:2011-05-20 修回日期:2012-03-16 出版日期:2012-12-25 发布日期:2012-12-25

Scheduling a Single Server and Equal Processing Times in a Two-machine Flow-shop

SHI Ling¹, CHENG Xue-Guang²

1.Department of Mathematics, Hubei University for Nationalities, Hubei Enshi 445000;

2.School of Mathematics and Statistics, Wuhan University, Wuhan 430072

Received:2011-05-20 Revised:2012-03-16 Online:2012-12-25 Published:2012-12-25

摘要/Abstract

摘要：

研究带单服务器和相同加工时间的两台机器的流水作业排序问题, 证明该问题是强NP -困难的, 引入一个简单的贪婪算法证明其紧界是3/2.

关键词: 两台机器, 流水作业, 单服务器, NP -困难, 最坏性能比

Abstract:

We consider the problem of two-machine flow-shop scheduling with a single server and equal processing times, we show that this problem is NP-hard in the strong sense and present a simple greedy algorithm for it with worst-case bound 3/2.

Key words: Two-machine, Flow-shop, Single server, Complexity, NP-hardness, Worst-case analysis

中图分类号:

90B35

时凌, 程学光. 带单服务器和相同加工时间的流水作业排序问题[J]. 数学物理学报, 2012, 32(6): 1121-1125.

SHI Ling, CHENG Xue-Guang. Scheduling a Single Server and Equal Processing Times in a Two-machine Flow-shop[J]. Acta mathematica scientia,Series A, 2012, 32(6): 1121-1125.