Skip to main content
Log in

Lawler’s minmax cost algorithm: optimality conditions and uncertainty

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

The well-known \(O(n^2)\) minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of possible values is known. For this problem we derive an \(O(n^2)\) algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique.

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

Access this article

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

  • Aissi, H., Aloulou, M. A., & Kovalyov, M. Y. (2011). Minimizing the number of late jobs on a single machine under due date uncertainty. Journal of Scheduling, 14, 351–360.

  • Aloulou, M. A., & Della Croce, F. (2008). Complexity of single machine scheduling problems under scenario-based uncertainty. Operations Research Letters, 36, 338–342.

    Article  Google Scholar 

  • Averbakh, I. (2000). Minmax regret solutions for minimax optimization problems with uncertainty. Operations Research Letters, 27, 57–65.

    Article  Google Scholar 

  • Kasperski, A. (2005). Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion. Operations Research Letters, 33, 431–436.

    Article  Google Scholar 

  • Kasperski, A., & Zieliński, P. (2013). Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion. Operations Research Letters, 41, 639–643.

    Article  Google Scholar 

  • Kouvelis, P., & Yu, G. (1997). Robust discrete optimization and its applications. Dordrecht: Kluwer Academic Publishers.

    Book  Google Scholar 

  • Lawler, E. L. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19(5), 544–546.

    Article  Google Scholar 

  • Lin, Y., & Wang, X. (2007). Necessary and sufficient conditions of optimality for some classical scheduling problems. European Journal of Operational Research, 176, 809–818.

    Article  Google Scholar 

  • Moore, J. M. (1968). A \(n\) job, one machine scheduling algorithm for minimizing the number of late jobs. Management Science, 15, 102–109.

    Article  Google Scholar 

  • Savage, L. J. (1954). The foundations of statistics. New York: Wiley.

    Google Scholar 

  • Wald, A. (1950). Statistical decision functions. New York: Wiley.

    Google Scholar 

  • Yager, R. R. (1988). On ordered weighted averaging aggregation operators in multicriteria decision making. IEEE Transaction on Systems, Man, and Cybernetics, 18, 183–190.

    Article  Google Scholar 

Download references

Acknowledgments

Financial support has been provided in part by the joint BRFFR-PICS Project (PICS 5379, BRFFR \(\varPhi 10 \varPhi \Pi -001\)). The research of the first two authors have been partially supported by the LabEx PERSYVAL-Lab (ANR–11-LABX-0025). We are grateful to referees for their substantial and helpful comments.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Gerd Finke.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Brauner, N., Finke, G., Shafransky, Y. et al. Lawler’s minmax cost algorithm: optimality conditions and uncertainty. J Sched 19, 401–408 (2016). https://doi.org/10.1007/s10951-014-0413-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-014-0413-x

Keywords

Navigation