A FPTAS for a two-stage hybrid flow shop problem and optimal algorithms for identical jobs

作者：Wei, Qi; Shan, Erfang^*; Kang, Liying

来源：Theoretical Computer Science, 2014, 524: 78-89.

DOI：10.1016/j.tcs.2014.01.004

• Scheduling
• Fully polynomial time approximation
• Two-stage flow shop
• Makespan

In this paper, a two-machine two-stage flow shop problem with flexible tasks is considered. Each job has two tasks: the first task can be processed on either machine, called flexible task, while the second task must be processed on the second machine and can't be processed unless the first task is completed. The problem is to determine the assignment of the flexible tasks to the machines for each job, with the objective of minimizing the makespan. We present a fully polynomial time approximation scheme (FPTAS) for the problem. Moreover, we consider the problems with identical jobs and buffer capacity, and present some optimal algorithms for them. For the problems with identical jobs, we find an interesting result: If the buffer is not less than 2, more buffer capacity cannot bring better result.

• 出版日期2014-3-6
• 单位浙江大学; 上海大学; 浙江大学宁波理工学院