使总完工时间达到最小的流水作业排序问题  

Minimizing the total completion time for flow-shop scheduling problems with a single server

作　　者：时凌 龙彩燕 张琼 SHI Ling;LONG Cai-yan;ZHANH Qiong(Basic Teaching Department,Guangzhou College of Technology and Business,Guangzhou 510850,China)

机构地区：[1]广州工商学院基础教学部,广东广州510850

出　　处：《西南民族大学学报（自然科学版）》2020年第6期638-642,共5页Journal of Southwest Minzu University(Natural Science Edition)

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

摘　　要：研究带单服务器且服务时间相等的流水作业排序问题,该流水作业排序问题的目标函数是使总完工时间达到最小.利用目标和的数字匹配这个强NP-困难问题到带单服务器且服务时间相等的流水作业排序问题的归约,证明带单服务器且服务时间相等的流水作业排序问题问题也是强NP-困难的.引入加工顺序为最小加工时间优先的新启发式算法,并证明该启发式算法的上界是6/5,且该上界是紧的.In this paper,the problem of flow-shop scheduling problem with a single server and equal server times is studied.The objective function of this problem is to minimize the total completion time.Using reduction of the stronglyNP-hard problem of the numerical matching with target sums to the flow-shop scheduling problem with a single server and equal servers,it is proved that this problem is alsoNP-hard in the strong sense.A new heuristic algorithm is introduced in which the processing sequence is shortest processing time first.It is proved the worst-case bound for the problem is 6/5,and the bound is tight.

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

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