摘要
研究了一个带单服务器且加工时间相等的两机流水作业排序问题,其目标函数是使总完工时间达到最小.研究表明,该流水作业排序问题是强NP-困难的.针对该流水作业排序问题构造了一种新的加工顺序,并证明该加工顺序的紧界为7/6.
We consider the problem of two-machine flow-shop scheduling with a single server and equal processing times, the objective function is to minimize total completion time.We show that this problem is NP-hard in the strong sense and present a busy schedule for it with worst case ratio 7/6, and the bound is tight.
作者
时凌
张琼
龙彩燕
SHI Ling;ZHANG Qiong;LONG Caiyan(Institute of General Education,Guangzhou College of Technology and Business,Guangzhou 510850,China)
出处
《延边大学学报（自然科学版）》
CAS
2022年第4期332-335,共4页
Journal of Yanbian University（Natural Science Edition）
基金
国家自然科学基金(61763009)
广州工商学院院级科研课题立项项目(KA201831)
广州工商学院校级科研项目(KAZX2021008)。
关键词
流水作业排序问题
总完工时间
单服务器
最坏性能比
flow-shop scheduling problem
total completion time
a single server
worst case ratio
