中文

Operations Research Transactions >

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

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

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

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.008

References

[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
Outlines

/

〈 〉