English

运筹学学报 >

2019 , Vol. 23 >Issue 4: 95 - 104

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.04.008

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

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

收稿日期: 2017-09-11

  网络出版日期: 2019-12-04

基金资助

国家自然科学基金（Nos.11626120，11901255），江西省教育厅科技项目（No.GJJ150447）

收起

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

Expand
  • 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 date: 2017-09-11

  Online published: 2019-12-04

Fold

摘要

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

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

本文引用格式

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

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(n3) to improve the worst-case ratio from 3/2 to 5/4.

Key words： scheduling; delivery time; maintenance; algorithm; worst-case ratio

参考文献

[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.
Options
文章导航

/

〈 〉