摘要
研究单位工件、有序约束的三台机流水作业排序问题,目标是极小化工件的最大完工时间。在序约束关系形成最长链图结构的情形下,首先对其顶点(工件)集进行自然分层,然后在相邻顶点层之间尽可能寻找一对相容工件,最后将每一层工件在三台流水作业机上进行最优排序,并由一对相容工件衔接相邻层,得到最坏情况界不超过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.
作者
陈占文
张安
陈永
陈光亭
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)
出处
《杭州电子科技大学学报（自然科学版）》
2020年第3期88-91,共4页
Journal of Hangzhou Dianzi University：Natural Sciences
基金
国家自然科学基金资助项目(11571252,11771114)。
关键词
流水作业
序约束
最长链图
近似算法
最坏情况分析
flow shop
precedence constraint
longest-chain graph
approximation algorithm
worst-case analysis
