带单机器人的流水作业排序问题的复杂性  

Complexity Result for Flow-shop Scheduling Problem with a Single Robot

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

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

出　　处：《内蒙古民族大学学报（自然科学版）》2021年第6期461-464,共4页Journal of Inner Mongolia Minzu University：Natural Sciences

基　　金：国家自然科学基金项目(61763009)。

摘　　要：研究n个工件在2台机器上加工的流水作业排序问题,目标函数是使完工时间达到最小.当一个工件在一台机器上完工后到下一台机器上加工之前的时间间隔,称之为运输时间的时间间隔,所有运输均由单运输机来完成,机器人在同一时间只运输一个工件,证明对于这种特殊的排序问题仍然是强NP-困难的.The flow-shop scheduling problem of n jobs processed on two machines is studied and the objective function is to minimize the makespan.Between the completion of an operation and the beginning of the next oper-ation of the same job,there is a time lag called a transportation delay.All transportation delays have to be done by a single robot,which can perform at most one transportation at a time.This special case is proved to be NP hard in the strong sense.

关 键 词：流水作业排序问题 复杂性 单机器人 

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