AJOR  Vol.5 No.2 , March 2015
Deep Cutting Plane Inequalities for Stochastic Non-Preemptive Single Machine Scheduling Problem
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.
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.

[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.