带广义偏序约束的Flow-Shop排序问题  

FLOW-SHOP SCHEDULING WITH GENERALIZED PRECEDENCE CONSTRAINTS

作　　者：杜东雷[1] 韩继业[1] 

机构地区：[1]中国科学院应用数学所,北京100080

出　　处：《应用数学学报》1997年第4期587-592,共6页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金

摘　　要：本文研究了一种新的排序问题:带‘广义偏序”约束的flow-shop排序问题.如工件Jj与工件.。之间有广义偏序,则Jj→Jk,且Jj的完工时间与Jk的开工时间的间隔不小于ljk和不大于ujk,0ljkujk.问题的目标函数是最大完工时间.我们证明了:具有比较简单的广义偏序约束的两台机器的flow-shop问题亦是NP-hard.我们给出了相应的启发式算法.对于单位加工时间,证明了一种较复杂的广义偏序约束的flow-shop问题是多项式可解的.A new kind of flow-shop scheduling problem, flow-shop with generalized precedeuce constraints, is considered in this paper. When task Jjprecedes task Jk, the time between the end of task Jj and the beginning of task Jk must be at least ljk, but no more than ujk, where 0 ljk ujk. The objective is to minimize makespan. For some precedence relations, the problem is shown to be NP-hard, and some heuristics are given with worst-case analysis. For some special cases, polynomial algorithms are offered.

关 键 词：Folw-shop排序 广义偏序 排序 流水作业问题 

分 类 号：O223[理学—运筹学与控制论]