带单服务器的流水作业排序问题的复杂性  

Complexity for flow-shop scheduling problems with a single server

作　　者：时凌 张琼 龙彩燕 SHI Ling;ZHANG Qiong;LONG Caiyan(Institute of General Education,Guangzhou College of Technology and Business,Guangzhou 510850,China)

机构地区：[1]广州工商学院通识教育学院,广东广州510850

出　　处：《延边大学学报（自然科学版）》2022年第4期332-335,共4页Journal of Yanbian University（Natural Science Edition）

基　　金：国家自然科学基金(61763009);广州工商学院院级科研课题立项项目(KA201831);广州工商学院校级科研项目(KAZX2021008)。

摘　　要：研究了一个带单服务器且加工时间相等的两机流水作业排序问题,其目标函数是使总完工时间达到最小.研究表明,该流水作业排序问题是强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.

关 键 词：流水作业排序问题 总完工时间 单服务器 最坏性能比 

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