Skip to main content
SpringerLink
Log in

Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the makespan when every job has a positive tail. We propose a polynomial approximation algorithm with a worst-case performance ratio of 3/2 for this problem. We show that this bound is tight. We present a dynamic programming algorithm and we show that the problem has an FPTAS (Fully Polynomial Time Approximation Algorithm) by exploiting the well-known approach of Ibarra and Kim (J. ACM 22:463–468, 1975). Such an FPTAS is strongly polynomial. The obtained results outperform the previous polynomial approximation algorithms for this problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Belouadah H, Posner ME, Potts CN (1992) Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Appl Math 36:213–231

    Article  MATH  MathSciNet  Google Scholar 

  • Carlier J (1982) The one-machine sequencing problem. Eur J Oper Res 11:42–47

    Article  MATH  MathSciNet  Google Scholar 

  • Chen WJ (2006) Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. J Oper Res Soc 57:410–415

    Article  MATH  Google Scholar 

  • Dessouky MI, Margenthaler CR (1972) The one-machine sequencing problem with early starts and due dates. AIIE Trans 4(3):214–222

    Google Scholar 

  • Gens GV, Levner EV (1981) Fast approximation algorithms for job sequencing with deadlines. Discrete Appl Math 3:313–318

    Article  MATH  Google Scholar 

  • Gharbi A, Haouari M (2005) Optimal parallel machines scheduling with availability constraints. Discrete Appl Math 148:63–87

    Article  MATH  MathSciNet  Google Scholar 

  • Hall LA, Shmoys DB (1992) Jackson’s rule for single machine scheduling: making a good heuristic better. Math Oper Res 17:22–35

    Article  MATH  MathSciNet  Google Scholar 

  • He Y, Zhong W, Gu H (2006) Improved algorithms for two single machine scheduling problems. Theor Comput Sci 363:257–265

    Article  MATH  MathSciNet  Google Scholar 

  • Ibarra O, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J ACM 22:463–468

    Article  MATH  MathSciNet  Google Scholar 

  • Kacem I (2007a) Approximation algorithm for the weighted flowtime minimization on a single machine with a fixed non-availability interval. Comput Ind Eng, doi:10.1016/j.cie.2007.08.005

  • Kacem I (2007b) Fully polynomial approximation schemes for the weighted flowtime minimization under unavailability constraint. Technical Report, University of Technology of Troyes, France (submitted)

  • Kacem I, Haouari M (2005) Analyse au pire cas de l’algorithme de Schrage appliqué au problème de minimisation du makespan sur une seule machine avec une contrainte d’indisponibilité. Res Report ISTIT-OSI-2006-02. University of Technology of Troyes, France

  • Kacem I, Chu C (2006) Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period. Eur J Oper Res, doi:10.1016/j.ejor.2006.06.062

  • Kacem I, Chu C (2007) Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint. Int J Prod Econ, doi:10.1016/j.ijpe.2007.01.013

  • Kacem I, Chu C, Souissi A (2008) Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times. Comput Oper Res 35(3), 827–844

    Article  MATH  MathSciNet  Google Scholar 

  • Kovalyov MY, Kubiak W (1999) A fully polynomial approximation scheme for weighted earliness-tardiness problem. Oper Res 47:757–761

    Article  MATH  MathSciNet  Google Scholar 

  • Kubzin MA, Strusevich VA (2006) Planning machine maintenance in two machine shop scheduling. Oper Res 54:789–800

    Article  MATH  Google Scholar 

  • Lee CY (1996) Machine scheduling with an availability constraints. J Glob Optim 9:363–384

    Article  Google Scholar 

  • Lee CY (2004) Machine scheduling with an availability constraint. In: Leung JYT (ed) Handbook of scheduling: algorithms, models, and performance analysis, USA, Fl, Boca Raton, chap 22

    Google Scholar 

  • Mauguière Ph, Billaut J-C, Bouquard J-L (2005) New single machine and job-shop scheduling problems with availability constraints. J Sched 8:211–231

    Article  MATH  MathSciNet  Google Scholar 

  • Potts CN (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper Res 28:1436–1441

    Article  MATH  MathSciNet  Google Scholar 

  • Qi X (2007) A note on worst-case performance of heuristics for maintenance scheduling problems. Discrete Appl Math 155:416–422

    Article  MATH  MathSciNet  Google Scholar 

  • Qi X, Chen T, Tu F (1999) Scheduling the maintenance on a single machine. J Oper Res Soc 50:1071–1078

    Article  MATH  Google Scholar 

  • Sahni S (1976) Algorithms for scheduling independent tasks. J ACM 23:116–127

    Article  MATH  MathSciNet  Google Scholar 

  • Schmidt G (2000) Scheduling with limited machine availability. Eur J Oper Res 121:1–15

    Article  MATH  Google Scholar 

  • Wang G, Sun H, Chu C (2005) Preemptive scheduling with availability constraints to minimize total weighted completion times. Ann Oper Res 133:183–192

    Article  MATH  MathSciNet  Google Scholar 

  • Webster S (1995) Weighted flow time bounds for scheduling identical processors. Eur J Oper Res 80: 103–111

    Article  MATH  Google Scholar 

  • Woeginger GJ (2005) A comment on scheduling two machines with capacity constraints. Discrete Optim 2:269–272

    Article  MATH  MathSciNet  Google Scholar 

  • Yuan JJ, Shi L, Ou JW (2007) Single machine scheduling with forbidden intervals and job delivery times (submitted to APJOR)

Download references

Author information

Authors and Affiliations

  1. Université de Technologie de Troyes, ICD-LOSI, CNRS FRE 2848, 12 rue Marie Curie, B.P. 2060, 10010, Troyes cedex, France

    Imed Kacem

Authors
  1. Imed Kacem
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Imed Kacem.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kacem, I. Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval. J Comb Optim 17, 117–133 (2009). https://doi.org/10.1007/s10878-007-9102-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-007-9102-4

Keywords

Search

Navigation