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

Fei Yang, Shengyuan Chen

Department of Mathematics and Statistics, York University, Toronto, Canada.

DOI: 10.4236/ajor.2015.52006                

Abstract

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.

Keywords

Single Machine Scheduling, Cut Generation, Robust Optimization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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. http://dx.doi.org/10.1287/moor.22.3.513
[2]	Yang, J. and Yu, G. (2002) On the Robust Single Machine Scheduling Problem. Journal of Combinational Optimization, 6, 17-33. http://dx.doi.org/10.1023/A:1013333232691
[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. http://dx.doi.org/10.1287/opre.41.5.924
[8]	Nemhauser, G.L. and Wolsey, L.A. (1988) Integer and Combinatorial Optimization. Wiley, New York. http://dx.doi.org/10.1002/9781118627372
[9]	Soric, K. (2000) A Cutting Plane Algorithm for a Single Machine Scheduling Problems. European Journal of Operational Research, 127, 383-393. http://dx.doi.org/10.1016/S0377-2217(99)00493-2
[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. http://dx.doi.org/10.1016/j.cor.2009.12.001
[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. http://dx.doi.org/10.1007/BF01586059
[13]	Queyranne, M. (1993) Structure of a Simple Scheduling Polyhedron. Mathematical Pragramming, 58, 263-285. http://dx.doi.org/10.1007/BF01581271
[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.