带运输时间和单自动机的流水作业排序  

Flow-shop scheduling problems with transportation delays and a single robot

作　　者：时凌 张琼 时义梅 刘丁酉[3] Shi Ling;Zhanq Qionq;Shi Yimei;Liu Dinvou(Basic Teaching Department,Guangzhou College of Technology and Business,Guangzhou,Guangdong 510850,China;School of Science,Hubei University for Nationalities,Enshi,Hubei 445000,China;School of Mathematics and Statistics,Wuhan University,Wuhan,Hubei 430072,China)

机构地区：[1]广州工商学院基础教学部,广东广州510850 [2]湖北民族民族学院理学院,湖北恩施445000 [3]武汉大学数学与统计学院,湖北武汉430072

出　　处：《石河子大学学报（自然科学版）》2018年第4期524-528,共5页Journal of Shihezi University(Natural Science)

基　　金：国家自然科学基金(6134030),广州工商学院2018院级科研(KA201831)项目

摘　　要：本文研究n个工件在2台机器上加工的流水作业排序问题。同一工件在一台机器上完工后在下一台机器加工之前有一个时间间隔即运输时间,所有运输时间都是由单自动机来完成运输,同一时间自动机只能运输一个工件,本文主要研究所有加工时间均匀等于1的情况下该问题的复杂性,并给出新的启发式算法,证明该算法的最坏性能比是3/2,且上界是紧的。The paper considers the problem of scheduling n jobs in a two-machine flow-shop to minimize the weighted sum of completion times. Between the completion of an operation and the beginning of the next operation of the same job, there is a time lag, which wherever to it as the transportation delays. All transportation delays have to be done by a single robot, which can perform at most onetransportation at a time. New complexity results are derived for all processing times equals 1. For a new heuristic algorithm, the worst-case performance is3/2,and the bound is tight.

关 键 词：流水作业排序问题 复杂性 运输时间 单自动机 

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