Share This Article:

Deep Cutting Plane Inequalities for Stochastic Non-Preemptive Single Machine Scheduling Problem

Abstract Full-Text HTML Download Download as PDF (Size:271KB) PP. 69-76
DOI: 10.4236/ajor.2015.52006    2,544 Downloads   2,900 Views  


We study the classical single machine scheduling problem but with uncertainty. A robust optimization model is presented, and an effective deep cut is derived. Numerical experiments show effectiveness of the derived cut.

Cite this paper

Yang, F. and Chen, S. (2015) Deep Cutting Plane Inequalities for Stochastic Non-Preemptive Single Machine Scheduling Problem. American Journal of Operations Research, 5, 69-76. doi: 10.4236/ajor.2015.52006.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Hall, L., Shmoys, B., Wein, J. and Schulz, A. (1997) Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms. Mathematics of Operation Research, 22, 513-544.
[2] Yang, J. and Yu, G. (2002) On the Robust Single Machine Scheduling Problem. Journal of Combinational Optimization, 6, 17-33.
[3] Leung, J.Y.-T. (2004) Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/ CRC, US.
[4] Birge, J.R. and Franois, L. (1997) Introduction to Stochastic Programming. Springer, Berlin.
[5] Mastrolilli, M., Mutsanas, N. and Svensson, O. (2008) Approximating Single Machine Scheduling with Scenarios. Computer Science, 5171, 153-164.
[6] Rustem, B. and Howe, M. (2002) Algorithms for Worst-Case Design and Applications to Risk Management. The Princeton University Press, Princeton.
[7] Hamada, T. and Glazebrook, K.D. (1993) A Bayesian Sequential Single Machine Scheduling Problem to Minimize the Expected Weighted Sum of Flow Times of Jobs with Exponential Processing Times. Operation Research, 41, 924-934.
[8] Nemhauser, G.L. and Wolsey, L.A. (1988) Integer and Combinatorial Optimization. Wiley, New York.
[9] Soric, K. (2000) A Cutting Plane Algorithm for a Single Machine Scheduling Problems. European Journal of Operational Research, 127, 383-393.
[10] de Farias Jr., I.R., Zhao, H. and Zhao, M. (2010) A Family of Inequalities Valid for the Robust Single Machine Scheduling Polyhedron. Computers & Operations Research, 37, 1610-1614.
[11] Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of np-Completeness. Freeman.
[12] de Sousa, J.P. and Wolsey, L.A. (1992) A Time-Indexed Formulation of Non-Preemptive Single-Machine Scheduling Problems. Mathematical Programming, 54, 353-367.
[13] Queyranne, M. (1993) Structure of a Simple Scheduling Polyhedron. Mathematical Pragramming, 58, 263-285.
[14] Van den Akker, J.M., van Haesel, C.P.M. and Savelsbergh, M.W.P. (1993) Facet Inducing Inequalities for Single-Machine Scheduling Problems. COSOR-Memoranda.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.