加工时间与等待时间线性相关的流水作业问题

A Flowshop Scheduling Problem Related with Waiting-Times

摘要: 在流水作业中，每个工件在一个机器上加工完毕之后直至在下一台机器上开始加工的时间，被称为等待时间，在所研究的问题中，等待时间使该工件的加工时间产生线性延伸，要求找出时间表使加工全长最小化，在两台机器的情况下，当延伸系数允许取两个不同值时，该问题已被证明是难问题，文献上曾指出，当延伸系数只取同一值时，该问题的计算复杂性尚未判定，本文证明，在上迷限制下，该问题也是难问题。

Abstract: We discuss a makespan problem of two machine flowshop in which any job waiting-time caus s a linear extension in the job processing-time on the second machine.The problem is known to he NP-hard when the waiting-time extension coefficients have two arbitrary values.In this paper, the problem is proved to be NP-hard too when the waiting-time extension coefficients have the same arbitrary value.