带强制工期的双机开放车间排序问题

《带强制工期的双机开放车间排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第20卷第4期2011年8月运筹与管理OPERATIONSRESEARCHANDMANAGEblENTSCIENCEV01．20，No．4Aug．2011带强制工期的双机开放车间排序问题钟雪灵1，王国庆2，程明宝3，李晓春4(1．广东金融学院计算机系．广东广州510520；2．暨南大学管理学院，广东广州510632；3．广东工业大学管理学院．广东广州510520；4．华南师范大学南海校区，广东南海528225)摘要：讨论了强制工期相等的凡个工件在双机开放车间加工。在允许机器空闲的条件下，寻找一个工件排序，使得最大提前完工时间最小。由于工件不允许延迟，同题

2、可能会无可行排序。先讨论了问题的可行性。如果问题可行，找出一个可行序列作为预排序列，并提出了一个算法计算每个工件尽可能迟的开工时间。而后，提出了一个多项式时间最优算法，在预排序列的基础上，通过调整两台机器上最先加工的工件来获得最优排序。关键词：运筹学；排序；开放车间；强制工期；最大提前完工时间中图分类号：0223文章标识码：A文章编号：1007—3221(2011)04．0108．05TwoMachinesOpenShopSchedulingwithIdenticalDeadlineZHONGXue．1in91，WANGGuo．qin92，CHENGMi

3、ng．ba03，LIXiao．chun4(1．DepartmentofComputer，GuangdongUniversityofFinance，Guangzhou510520，China；2．DepartmentofBusinessAdministration，JinanUniversity，Guangzhou，510632，China；3．SchoolofManagement，GuangdongUniversityofTechnology，Guangzhou510520，China；4．NanhaiCampus，SouthChinaNormalUni

4、versity，Nan-hai528225，China)Abstract：ThispaperdiscussestheprobleminwhichnjobswithcommondeadlinehavetObeprocessedontwomachinesopenshopconsideringtheidleinsert．Theobjectiveistofindajobsequenceanddeterminejobs’start·ingtimesSOastominimizethemaximumearliness．Sincetardyjobsareprohibit

5、ed，it’Spossiblethatthereisnofeasiblesequencefortheproblem，Weconsiderthefeasibilityprimarily．Iftheproblemisfeasible．wefirstpre-determineasequenceanddevelopanalgorithmtocomputejobs’startingtimestomakejobsprocessaslateaspossible．Then，apolynomialtimealgorithmisdevelopedtoachieveoptim

6、alitythroughadjustingthefirstpro·cessingjobonthetwomachinesbasedonthepre—determinedsequence．Keywords：operationalresearch；scheduling；openshop；deadline；maximumearliness0引言近年来，提前／延迟(Earliness／tardiness，E／T)排序问题是重要的研究热点之一。产生了大量的成果。在该类问题中，工件应该尽可能的在其工期上完工，既不提前，也不延迟。Garey等‘11做了初步研究，得出在单

7、机的环境下该问题都是为NP—hard。此后众多学者作了进一步研究。Baker和Seudder㈨作了详尽的综述。然而，在一些生产活动中，延迟被绝对禁止，或者延迟费用相比提前费用高许多而使得延迟不能收稿日期：2009—04—02基金项目：教育部人文社会科学研究项目基金(09YJC630088)作者简介：钟雪灵(1980-)，男．广东河源人．讲师，博士．研究方向：排序理论与算法；王回庆(1961．)，男，教授．博士．博士生导师，研究方向：生产运作与物流管理；程明宝(1972．)，男，副教授。博士，研究方向：排序理论与算法，物流；李晓春(1983．)，女，讲师，

8、博士。研究方向：生产运作与物流管理。第4期钟雪灵，等：带强制工期的双机开放车间排