一类带特殊序约束的三台机流水作业排序问题  

Three-machine Flow-shop Scheduling Problem Under a Class of Special Precedence Constraints

作　　者：陈占文 张安[1] 陈永[1] 陈光亭[2] CHEN Zhanwen;ZHANG An;CHEN Yong;CHEN Guangting(School of Sciences,Hangzhou Dianzi University,Hangzhou Zhejiang 310018,China;School of Electronics and Information Engineering,Taizhou University,Taizhou Zhejiang 318000,China)

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018 [2]台州学院电子与信息工程学院,浙江台州318000

出　　处：《杭州电子科技大学学报（自然科学版）》2020年第3期88-91,共4页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：国家自然科学基金资助项目(11571252,11771114)。

摘　　要：研究单位工件、有序约束的三台机流水作业排序问题,目标是极小化工件的最大完工时间。在序约束关系形成最长链图结构的情形下,首先对其顶点(工件)集进行自然分层,然后在相邻顶点层之间尽可能寻找一对相容工件,最后将每一层工件在三台流水作业机上进行最优排序,并由一对相容工件衔接相邻层,得到最坏情况界不超过3/2的多项式时间近似算法。通过构造实例进一步证明了界是紧的。This paper studies three-machine flow-shop scheduling problem for unit jobs under precedence constraints,whose objective is to minimize the maximum completion time of jobs.For a class of special precedence constraints namely the longest-chain graph(LCG),the vertices(jobs)in LCG are firstly layered in a natural way.Then we greedily search for a pair of agreeable jobs between adjacent layers.Finally,by optimally scheduling jobs in the same layer and connecting adjacent layers with a pair of agreeable jobs,we succeed in designing a polynomial time approximation algorithm with worst-case ratio no more than 3/2.Our instance shows that the bound is actually tight.

关 键 词：流水作业 序约束 最长链图 近似算法 最坏情况分析 

分 类 号：O221.7[理学—运筹学与控制论]