文献类型：期刊文献

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

英文题名：A Flowshop Scheduling Problem Related with Waiting-Times

作者：俞文[1];许三保[1]

机构：[1]华东理工大学应用数学研究所

年份：1994

卷号：20

期号：3

起止页码：378

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;国家哲学社会科学学术期刊数据库;Scopus;CSCD:【CSCD2011_2012】；

基金：国家自然科学基金

语种：中文

中文关键词：时间表(运筹);等待时间;流水作业;计算复杂性;数值三维匹配

外文关键词：scheduling(operations rescarch);waiting-times;flowsho pproblem;com-plexity;numerical 3-dimensional matching

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