Research ArticleOpen AccessGoogle Scholar indexed
Deep Cutting Plane Inequalities for Stochastic Non-Preemptive Single Machine Scheduling Problem
Department of Mathematics and Statistics, York University, Toronto, Canada
Department of Mathematics and Statistics, York University, Toronto, Canada
- 1 Department of Mathematics and Statistics, York University, Toronto, Canada
- 2 Department of Mathematics and Statistics, York University, Toronto, Canada
American Journal of Operations Research·Volume 05 (2015)·Pages 69–76·Published 28 February 2015·DOI10.4236/ajor.2015.52006
Copy link · social · email
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.
KeywordsSingle Machine SchedulingCut GenerationRobust Optimization
- 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
- 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
- Leung, J.Y.-T. (2004) Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/ CRC, US.
- Birge, J.R. and Franois, L. (1997) Introduction to Stochastic Programming. Springer, Berlin.
- Mastrolilli, M., Mutsanas, N. and Svensson, O. (2008) Approximating Single Machine Scheduling with Scenarios. Computer Science, 5171, 153-164.
- Rustem, B. and Howe, M. (2002) Algorithms for Worst-Case Design and Applications to Risk Management. The Princeton University Press, Princeton.
- 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
- Nemhauser, G.L. and Wolsey, L.A. (1988) Integer and Combinatorial Optimization. Wiley, New York. http://dx.doi.org/10.1002/9781118627372
- 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
- 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
- Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of np-Completeness. Freeman.
- 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
- Queyranne, M. (1993) Structure of a Simple Scheduling Polyhedron. Mathematical Pragramming, 58, 263-285. http://dx.doi.org/10.1007/BF01581271
- 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.