article

Single machine scheduling with scenarios

Authors:

Monaldo Mastrolilli,

Nikolaus Mutsanas,

Ola SvenssonAuthors Info & Claims

Theoretical Computer Science, Volume 477

Pages 57 - 66

https://doi.org/10.1016/j.tcs.2012.12.006

Published: 01 March 2013 Publication History

Abstract

In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in the definition of the instance. We study the single machine scheduling problem with the objective of minimizing the weighted sum of completion times. We model uncertainty by replacing the vector of numerical values in the description of the instance by a set of possible vectors, called scenarios. The goal is to find a schedule of minimum value in the worst-case scenario. We first show that the general problem cannot be approximated within O(log^1^-^@en) for any @e>0, unless NP has quasi-polynomial algorithms. We then study more tractable special cases and obtain a linear program (LP)-based 2-approximation algorithm for the unweighted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6/5. We conclude by presenting a polynomial-time algorithm based on dynamic programming for the case when the number of scenarios and the values of the instance are bounded by some constant.

References

[1]

Aissi, H., Bazgan, C. and Vanderpooten, D., Approximating min¿max (regret) versions of some polynomial problems. In: COCOON, pp. 428-438.

Digital Library

[2]

Ambühl, C., Mastrolilli, M., Mutsanas, N. and Svensson, O., On the approximability of single machine scheduling with precedence constraints. Mathematics of Operations Research. v36 i4. 653-669.

Digital Library

[3]

Arora, S. and Lund, C., Hardness of approximations. In: Hochbaum, D.S. (Ed.), Approximation Algorithms for NP-Hard Problems, PWS.

Digital Library

[4]

Bansal, N. and Khot, S., Optimal Long-Code test with one free bit. In: Foundations of Computer Science, pp. 453-462.

Digital Library

[5]

Robust discrete optimization and network flows. Programming Series B. v98. 49-71.

[6]

Birge, J. and Louveaux, F., Introduction to Stochastic Programming. 1997. Springer.

[7]

Chekuri, C. and Motwani, R., Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Applied Mathematics. v98 i1¿2. 29-38.

Digital Library

[8]

Chudak, F.A. and Hochbaum, D.S., A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Operations Research Letters. v25. 199-204.

Digital Library

[9]

Dinur, I., Guruswami, V., Khot, S. and Regev, O., A new multilayered pcp and the hardness of hypergraph vertex cover. In: STOC¿03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM, New York, NY, USA. pp. 595-601.

Digital Library

[10]

Feige, U., Jain, K., Mahdian, M. and Mirrokni, V.S., Robust combinatorial optimization with exponential scenarios. In: IPCO, pp. 439-453.

Digital Library

[11]

Graham, R., Lawler, E., Lenstra, J.K. and Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey. In: Annals of Discrete Mathematics, vol. 5. North¿Holland. pp. 287-326.

[12]

Hall, L.A., Schulz, A.S., Shmoys, D.B. and Wein, J., Scheduling to minimize average completion time: off-line and on-line algorithms. Mathematics of Operations Research. v22. 513-544.

[13]

Kasperski, A. and Zieli'ski, P., On the existence of an fptas for minmax regret combinatorial optimization problems with interval data. Operations Research Letters. v35 i4. 525-532.

Digital Library

[14]

Khot, S., On the power of unique 2-prover 1-round games. In: Proceedings of the 34th annual ACM symposium on Theory of computing, pp. 767-775.

Digital Library

[15]

S. Khot, On the power of unique 2-prover 1-round games, in: IEEE Conference on Computational Complexity, 2002, p. 25.

Digital Library

[16]

S. Khot, O. Regev, Vertex cover might be hard to approximate to within 2¿¿, in: Proc. of 18th IEEE Annual Conference on Computational Complexity, CCC, 2003, pp. 379¿386.

[17]

Kouvelis, P. and Yu, G., Robust Discrete Optimization and Its Applications. 1997. Kluwer Academic Publishers.

[18]

Lawler, E.L., Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics. v2. 75-90.

[19]

Margot, F., Queyranne, M. and Wang, Y., Decompositions, network flows and a precedence constrained single machine scheduling problem. Operations Research. v51 i6. 981-992.

Digital Library

[20]

Potts, C.N., An algorithm for the single machine sequencing problem with precedence constraints. Mathematical Programming Study. v13. 78-87.

[21]

A.S. Schulz, Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, in: Proceedings of the 5th Conference on Integer Programming and Combinatorial Optimization, IPCO, 1996, pp. 301¿315.

Digital Library

[22]

Schuurman, P. and Woeginger, G.J., Polynomial time approximation algorithms for machine scheduling: ten open problems. Journal of Scheduling. v2 i5. 203-213.

[23]

Smith, W.E., Various optimizers for single-stage production. Naval Research Logistics Quarterly. v3. 59-66.

Cited By

Bosman Tvan Ee MErgen EImreh CMarchetti-Spaccamela ASkutella MStougie L(2023)Total Completion Time Scheduling Under ScenariosApproximation and Online Algorithms 10.1007/978-3-031-49815-2_8(104-118)Online publication date: 7-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-49815-2_8
Bougeret MJansen KPoss MRohwedder L(2021)Approximation Results for Makespan Minimization with Budgeted UncertaintyTheory of Computing Systems10.1007/s00224-020-10024-765:6(903-915)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00224-020-10024-7
Hermelin DManoussakis GPinedo MShabtay DYedidsion L(2020)Parameterized Multi-Scenario Single-Machine Scheduling ProblemsAlgorithmica10.1007/s00453-020-00702-w82:9(2644-2667)Online publication date: 28-Mar-2020
https://dl.acm.org/doi/10.1007/s00453-020-00702-w
Show More Cited By

Single machine scheduling with scenarios
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Approximation Algorithms for Scheduling with Reservations

We study the problem of non-preemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations, where m is constant. This setting is practically relevant because for various reasons, some ...
Conditional hardness of precedence constrained scheduling on identical machines
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

Already in 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. Till this date it has remained ...
Approximation algorithms for minimizing the total weighted tardiness on a single machine

Given a single machine and a set of jobs with due dates, the classical NP-hard problem of scheduling to minimize total tardiness is a well-understood one. Lawler gave a fully polynomial-time approximation scheme (FPTAS) for it some 20 years ago. If the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 477, Issue

March, 2013

122 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2013.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 March 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bosman Tvan Ee MErgen EImreh CMarchetti-Spaccamela ASkutella MStougie L(2023)Total Completion Time Scheduling Under ScenariosApproximation and Online Algorithms 10.1007/978-3-031-49815-2_8(104-118)Online publication date: 7-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-49815-2_8
Bougeret MJansen KPoss MRohwedder L(2021)Approximation Results for Makespan Minimization with Budgeted UncertaintyTheory of Computing Systems10.1007/s00224-020-10024-765:6(903-915)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00224-020-10024-7
Hermelin DManoussakis GPinedo MShabtay DYedidsion L(2020)Parameterized Multi-Scenario Single-Machine Scheduling ProblemsAlgorithmica10.1007/s00453-020-00702-w82:9(2644-2667)Online publication date: 28-Mar-2020
https://dl.acm.org/doi/10.1007/s00453-020-00702-w
Kasperski AZieliński P(2019)Risk-averse single machine scheduling: complexity and approximationJournal of Scheduling10.1007/s10951-019-00599-622:5(567-580)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10951-019-00599-6
Kasperski AZieliński P(2016)Single machine scheduling problems with uncertain parameters and the OWA criterionJournal of Scheduling10.1007/s10951-015-0444-y19:2(177-190)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s10951-015-0444-y
Kasperski AKurpisz AZieliński P(2015)Approximability of the robust representatives selection problemOperations Research Letters10.1016/j.orl.2014.10.00743:1(16-19)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.orl.2014.10.007

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents