带有机器维修和两车辆派送的单机排序问题  

Single Machine Scheduling with a Maintenance Interval and Two Vehicles Delivery Coordination

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

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

出　　处：《运筹与管理》2022年第11期72-76,共5页Operations Research and Management Science

基　　金：江苏高校哲学社会科学研究一般项目(2021SJA2279);南京审计大学金审学院校级课题(JSXJKT2012)。

摘　　要：研究了带有机器维修和工件派送的单机排序问题,该问题可以被视为一个集成生产和出站配送的排序模型。不同体积的工件需要在带有一个维修区间的机器上加工,且加工不可中断,然后由固定容量的两辆同类车批次交付给单客户,目标函数是极小化最大完工时间,本文提出了2-近似算法,并证明了2是紧界。This paper investigates a single machine scheduling problem with a maintenance interval and job delivery coordination.The 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 to a customer by two homogeneous vehicles with a limited load capacity in batches in the distribution center.The goal is minimize the makespan.We present a 2-approximation algorithm for the case,and also,we show that the performance ratio is tight.

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

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