带有运输且加工具有灵活性的无等待流水作业排序问题  

A no-wait flowshop scheduling problem with processing flexibility and transportation

作　　者：仲维亚[1] 马晓茹[2] 

机构地区：[1]上海大学管理学院,上海200444 [2]上海大学理学院,上海200444

出　　处：《运筹学学报》2016年第4期93-101,共9页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11571221;11301327)

摘　　要：研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题,其中每阶段只有一台机器,每个工件有两道工序需要依次在两台机器上加工,工件在两台机器上的加工及两道工序之间不允许等待.给出两种近似算法,并分别分析其最坏情况界.第一种算法是排列排序,证明了最坏情况界不超过5/2;第二种算法将工件按照两道工序加工时间之和的递增顺序排序,证明其最坏情况界不超过2.最后,通过数值模拟比较算法的性能.对问题中各参数取不同值的情况,分别生成若干个实例,用算法得到的解与最优解的下界作比值,通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.This paper addresses the performance of scheduling algorithms for a two- stage no-walt flowshop scheduling problem with processing flexibility and transportation, where each stage has one machine. Each job, composed of two operations, must be pro- cessed through the two stages without waiting time. We propose two approximation al- gorithms. The first algorithm is list scheduling and the second schedules the jobs in non-decreasing order of the total processing time of each job＇s two operations. We show that the worst case ratio of the algorithms is no more than 5/2 and 2, respectively. At last, we conduct numerical experiments to compare the performance of the algorithms. For the cases with different value of the parameters, we generate several instances. For every instance, the ratio of the algorithm＇s objective value and the optimal solution＇s ob- jective value is obtained. For each case, the maximum, minimum and average value of the instances＇ ratio are obtained to analyze the performance of the two algorithms.

关 键 词：排序 运输 流水作业 近似算法 

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