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

doi:10.12005/orms.2022.0355

运筹与管理 ›› 2022, Vol. 31 ›› Issue (11): 72-76.DOI: 10.12005/orms.2022.0355

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

蔡伟¹, 杨梅²

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

收稿日期:2020-11-10 出版日期:2022-11-25 发布日期:2022-12-14
作者简介:蔡伟(1995-)男,江苏南京人,讲师,硕士,研究方向:排序理论;杨梅(1994-)女,四川乐山人,讲师,硕士,研究方向:排序理论。
基金资助:
江苏高校哲学社会科学研究一般项目(2021SJA2279);南京审计大学金审学院校级课题(JSXJKT2012)

Single Machine Scheduling with a Maintenance Interval and Two Vehicles DeliveryCoordination

CAI Wei¹, YANG Mei²

1. Basic Teaching Department, Nanjing Audit University Jinshen College, Nanjing 210046, China;
2. College of Arts and Sciences, China University of Petroleum——Beijing at Karamay, Karamay 834000, China

Received:2020-11-10 Online:2022-11-25 Published:2022-12-14

摘要/Abstract

摘要： 研究了带有机器维修和工件派送的单机排序问题,该问题可以被视为一个集成生产和出站配送的排序模型。不同体积的工件需要在带有一个维修区间的机器上加工,且加工不可中断,然后由固定容量的两辆同类车批次交付给单客户,目标函数是极小化最大完工时间,本文提出了2-近似算法,并证明了2是紧界。

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

Abstract: 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.

Key words: single machine scheduling, machine maintenance, job delivery, approximation algorithm, worst-case performance analysis

中图分类号:

蔡伟, 杨梅. 带有机器维修和两车辆派送的单机排序问题[J]. 运筹与管理, 2022, 31(11): 72-76.

CAI Wei, YANG Mei. Single Machine Scheduling with a Maintenance Interval and Two Vehicles DeliveryCoordination[J]. Operations Research and Management Science, 2022, 31(11): 72-76.

参考文献

[1] Maggu P L, Das G. On sequencing problem with transportation times of jobs[J]. Pure and Applied Mathematika Science, 1980, 12(6): 1-6.
[2] Chang Y C, Lee C Y. Machinescheduling with job delivery coordination[J]. European Journal of Operational Research, 2004, 158(2): 470-487.
[3] Li C L, Lee C Y, et al. Machine scheduling with deliveries to multiple customer locations[J]. European Journal of Operational Research, 2005, 164(1): 39-51.
[4] Zhong W Y, Dosa G, Tan Z Y. On the machine scheduling problem with delivery coordination[J]. European Journal of Operational Research, 2007, 182(3): 1057-1072.
[5] Lu L F, Yuan J J. Single machine scheduling with job delivery to minimize makespan[J]. Asia Pacific Journal of Operational Research, 2008, 25(1): 1-10.
[6] Dong J M, Wang X S, Hu J L. Single machine scheduling with job delivery to multiple customers[J]. Journal of Scheduling, 2018, 21(3): 337-348.
[7] Jiang D K, Tan J Y. Scheduling with job delivery coordination on single machine[J]. Optimization Letters, 2018, 12(2): 265-272.
[8] Lee C Y. Machine scheduling with an availability constraint[J]. Journal of Global Optimization, 1996, 9(3): 395-416.
[9] Lee C Y. Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint[J]. Operations Research Letter, 1997, 20(3): 129-139.
[10] Ji M, He Y, Cheng T C E. Single-machine scheduling with periodic maintenance to minimize makespan[J]. Journal of Industrial Management Optimization, 2007, 34(6): 1764-1770.
[11] Wang X, Cheng T C E. Machine scheduling with an availability constraint and job delivery coordination[J]. Naval Research Logistics, 2007, 54(1): 11-20.
[12] Fan J, Lu X W, Liu P H.Integrated scheduling of production and delivery on a single machine with availability constraint[J]. Theoretical Computer Science, 2015, 562: 581-589.
[13] Hu J L, Luo T B, Su X T. Machine scheduling with a maintenance interval and job delivery coordination[J]. Optimization Letters, 2016, 10(8): 1645-1656.
[14] David Simchi-Levi. New worst-case results for the bin-packing problem[J]. Naval Research Logistics, 1994, 41(4): 579-585.

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

Single Machine Scheduling with a Maintenance Interval and Two Vehicles DeliveryCoordination

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

[1]	包晓光, 焦长春. 线型/圈型网络上单台车辆分群调度问题[J]. 运筹与管理, 2022, 31(7): 17-21.
[2]	刘春来, 王建军. 具有老化效应的单机共同工期安排和工件可拒绝排序问题[J]. 运筹与管理, 2021, 30(7): 66-70.
[3]	吴晨晨, 王丽, 徐春明, 徐大川. 鲁棒动态设施选址问题的近似算法[J]. 运筹与管理, 2020, 29(5): 61-66.
[4]	井彩霞, 吴瑞强, 贾兆红. 并行分批排序综述[J]. 运筹与管理, 2020, 29(1): 223-239.
[5]	王星, 徐大川. 软容量约束带随机需求的设施选址问题的近似算法[J]. 运筹与管理, 2018, 27(4): 35-38.
[6]	余英, 程明宝. 带学习效应和资源依赖的单机排序模型[J]. 运筹与管理, 2018, 27(1): 53-58.
[7]	刘春来, 王建军. 具有退化工件和老化效应的单机可拒绝排序问题[J]. 运筹与管理, 2017, 26(6): 95-101.
[8]	包晓光, 刘朝晖, 余炜. 线形网络上单台车辆分群调度问题[J]. 运筹与管理, 2017, 26(5): 125-129.
[9]	余海燕, 申成然, 符证菘. 周期性需求的供应商配送排程优化研究[J]. 运筹与管理, 2016, 25(6): 83-90.
[10]	余英, 舒彤, 曾春花. 工件带简单线性恶化函数和共同交货期单机排序问题[J]. 运筹与管理, 2016, 25(1): 154-157.
[11]	苏兵, 张萌, 姬浩. 应急救援物资紧缺的配送车辆路径选择研究[J]. 运筹与管理, 2013, 22(6): 57-64.
[12]	汪磊扬. 考虑常数客户批运输的单机排序问题[J]. 运筹与管理, 2013, 22(5): 29-34.
[13]	张新功, 严广乐, 唐国春, 唐海波. 具有指数和位置学习效应的机器排序问题[J]. 运筹与管理, 2011, 20(2): 97-101.