目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法

doi:10.15960/j.cnki.issn.1007-6093.2019.04.008

运筹学学报 ›› 2019, Vol. 23 ›› Issue (4): 95-104.doi: 10.15960/j.cnki.issn.1007-6093.2019.04.008

目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法

李刚刚^1,*, 鲁习文²

1. 江西财经大学信息管理学院, 南昌 330013;
2. 华东理工大学理学院, 上海 200237

收稿日期:2017-09-11 发布日期:2019-12-04
通讯作者: 李文华 E-mail:lgg198505@126.com
基金资助:
国家自然科学基金（Nos.11626120，11901255），江西省教育厅科技项目（No.GJJ150447）

An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time

LI Ganggang^1,*, LU Xiwen²

1. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China;
2. School of Science, East China University of Science and Technology, Shanghai 200237, China

Received:2017-09-11 Published:2019-12-04

摘要/Abstract

摘要： 单台机器带一个维修时间段的排序问题，目标是最小化所有工件的运输时间和.在这篇文章里，重新研究了该问题，并给出了一个时间复杂性为O（n³）的近似算法，将性能比从3/2改进到5/4.

关键词: 排序, 运输时间, 维修, 算法, 性能比

Abstract: The single-machine scheduling problem with a period of maintenance to minimize total delivery time has been studied. In this paper, we revisit the problem and propose an algorithm with time complexity of O(n³) to improve the worst-case ratio from 3/2 to 5/4.

Key words: scheduling, delivery time, maintenance, algorithm, worst-case ratio

中图分类号:

O224

李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.

LI Ganggang, LU Xiwen. An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time[J]. Operations Research Transactions, 2019, 23(4): 95-104.

参考文献

[1] Schmidt G. Scheduling with limited machine availability[J]. European Journal of Operational Research, 2000, 121:1-15.
[2] Sanlaville E, Schmidt G. Machine scheduling with availability constraints[J]. Acta Informatica, 1998, 35:795-811.
[3] Li G G, Lu X W. Approximation algorithms for the single-machine scheduling with a period of maintenance[J]. Optimization Letters, 2016, 10:543-562.
[4] Santos C, Magazine M. Batching in single operation manufacturing systems[J]. Operations Research Letters, 1985, 4:99-103.
[5] Tang C S. Scheduling batches on parallel machines with major and minor set-ups[J]. European Journal of Operational Research, 1990, 46:28-37.
[6] Chen Z L. Integrated production and outbound distribution scheduling:review and extensions[J]. Operations Research, 2010, 58:130-148.
[7] Chen Z L, Pundoor G. Order assignment and scheduling in a supply chain[J]. Operations Research, 2006, 54:555-572.
[8] Hall N G, Potts C N. Supply chain scheduling:batching and delivery[J]. Operations Research, 2003, 51:566-584.
[9] Hall N G, Potts C N. The coordination of scheduling and batch deliveries[J]. Annals of Operations Research, 2005, 135:41-64.
[10] Lee C Y, Chen Z L. Machine scheduling with transportation considerations[J]. Journal of Scheduling, 2001, 4:3-24.
[11] Chen Z L, Vairaktarakis G L. Integrated scheduling of production and distribution operations[J]. Management Science, 2005, 51:614-628.
[12] Li C L, Vairaktarakis G, Lee C Y. Machine scheduling with deliveries to multiple customer locations[J]. European Journal of Operational Research, 2005, 164:39-51.
[13] Ullrich C A. Integrated machine scheduling and vehicle routing with time windows[J]. European Journal of Operational Research, 2013, 227:152-165.
[14] Ahmadi J H, Ahmadi R H, Dasu S, et al. Batching and scheduling jobs on batch and discrete processors[J]. Operations Research, 1992, 40:750-763.

[1]	黄志鹏, 李兴权, 朱文兴. 超大规模集成电路布局的优化模型与算法[J]. 运筹学学报, 2021, 25(3): 15-36.
[2]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[3]	周宇阳, 张惠珍, 马良. 求解应急医疗设施分层递进式选址问题的改进免疫算法[J]. 运筹学学报, 2021, 25(2): 15-34.
[4]	钱晓慧, 王湘美. 一种单位化的增量梯度算法[J]. 运筹学学报, 2021, 25(2): 81-92.
[5]	周雪玲, 李梅霞, 车海涛. 多集分裂等式问题的逐次松弛投影算法[J]. 运筹学学报, 2021, 25(2): 93-103.
[6]	余山杉, 金苗苗, 罗文昌. 工件延误和可拒绝下的单机重新排序问题的近似方案[J]. 运筹学学报, 2021, 25(2): 104-114.
[7]	屈彪, 徐伟, 王新艳. 关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注[J]. 运筹学学报, 2021, 25(2): 144-148.
[8]	于海, 詹婉荣. 强收敛的球松弛CQ算法及其应用[J]. 运筹学学报, 2021, 25(1): 50-60.
[9]	屈德强, 尚有林, 詹悦, 吴丹. 全局优化问题的一个新的无参数填充函数[J]. 运筹学学报, 2021, 25(1): 89-95.
[10]	叶加青, 陈倩竹, 胡海平. 梯度Q-线性收敛的光滑凸极小化的一阶算法[J]. 运筹学学报, 2021, 25(1): 96-106.
[11]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[12]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[13]	郭晓玲, 庄远鑫, 刘轶凡. 地铁网络关键节点二次规划模型与求解算法研究[J]. 运筹学学报, 2020, 24(4): 51-62.
[14]	黄基诞, 郑斐峰, 徐寅峰, 刘明. 安装时间具有退化效应的MapReduce模型下的平行机调度[J]. 运筹学学报, 2020, 24(4): 93-106.
[15]	赵晨, 罗自炎, 修乃华. 稀疏优化理论与算法若干新进展[J]. 运筹学学报, 2020, 24(4): 1-24.

目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法

An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价