带有机器维修和工件派送的单机排序问题  

Single machine scheduling with a maintenance interval and job delivery coordination

作　　者：蔡伟 杨梅 CAI Wei;YANG Mei(Nanjing Audit University Jinshen College,Nanjing 210046,China;School of Arts and Sciences,China University of Petroleum-Beijing at Karamay,Karamay 834000,China)

机构地区：[1]南京审计大学金审学院,江苏南京210046 [2]中国石油大学(北京)克拉玛依校区,新疆克拉玛依834000

出　　处：《青海师范大学学报（自然科学版）》2021年第1期19-25,共7页Journal of Qinghai Normal University(Natural Science Edition)

基　　金：南京审计大学金审学院校级课题(JSXJKT2012)。

摘　　要：研究了带有机器维修和工件派送的单机排序问题,该问题可以被视为一个集成生产和出站配送的排序模型.不同体积的工件需要在带有一个维修区间的机器上加工,且加工不可中断,然后由固定容量的车辆批次交付给顾客,车辆派送完一批后需要返回派送中心交付下一个批次,工件派送到不同客户处所需的时间不同.目标函数是最小化最大完工时间.本文主要研究工件加工完成后由单车辆派送到多顾客的情形,提出了5/2-近似算法;对单客户的特殊情况该算法的界是2且是紧界.This paper investigates a single machine scheduling problem with a maintenance interval and job delivery coordination,our problem can also be viewed as an integrated production and outbound distribution scheduling model.Each job needs to be processed without preemption on the single machine with a maintenance,which demands different amount of storage space during transportation.After processing in the manufacturing center,they need to be delivered by vehicles with a limited load capacity in batches in the distribution center.When the vehicle deliveries a shipment to a customer it has to return back to manufac-turing center to delivery the next shipment,and it takes different constant time for the round trips between the machine and the different customers.The goal is minimize the makespan.We present a 5/2-approximation algorithm for the case which jobs are processed and delivered to multiple customers by a single vehicle;for a particular case of a customer,the bound of the algorithm is 2 and the performance ratio is tight.

关 键 词：单机排序 机器维修 工件派送 近似算法 最坏情况分析 

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