AUTHORS: Pattarapong Pakpoom, Peerayuth Charnsethikul

Download as PDF

ABSTRACT: We study cyclic personnel scheduling with double shift requirement under demand uncertainty. The problem is formulated as a two-stage stochastic integer program with integer recourse. Solving it with commercial software CPLEX takes extended period of time. We explore an exact approach based on Benders decomposition technique and compare its performance to a heuristics approach based on genetic algorithm and a mip approach , solving the original problem by a commercial mip solver. A special solution method allow us to obtain optimal solutions to subproblems efficiently. This method are applicable to both exact and heuristic approaches which significantly accelerate overall solution process. Numerical results illustrate that the proposed approach, exact approach based on Benders decomposition technique, outperform the heuristics approach based on genetic algorithm and the CPLEX mip solver in all 16 instances

KEYWORDS: - Stochastic programming; Benders decomposition; Personnel scheduling; Genetic algorithm

REFERENCES:

[

[1] N.E. Mastorakis, Unstable Ordinary differential equations: Solution via genetic algorithms and the method of Nelder-Mead, Proc. WSEAS Int. Conf. Sys. Thorem. Sci. Comp, 2006, pp. 1–6.

[2] N.E. Mastorakis, Solving non-linear equations via genetic algorithms, Proc. WSEAS Int. Conf. Evol. Comp., 2005, pp. 24–28.

[3] J.F. Bard and H.W. Purnomo, Cyclic preference scheduling of nurses using a Lagrangian-based heuristic, J. Sche. 10(1), 2007, pp. 5–23.

[4] J.F. Bard, D.P. Morton and Y.M. Wang, Workforce planning at USPS mail processing and distribution centers using stochastic optimization, Anal. Oper. Res. 155(1), 2007, pp. 51–78.

[5] F.F. Easton and N. Mansour, A distributed genetic algorithm for deterministic and stochastic labor scheduling problems, Eu. J. Oper. Res. 118(3), 1999, pp. 505–523.

[6] P. Punnakitikashem, J.M. Rosenberber, and D.F. Buckley-Behan, A stochastic programming approach for integrated nurse staffing and assignment, IIE Tran. 45(10), 2013, pp. 1059–1076.

[7] M. Bodur and J.R. Luedtke, Mixed-integer rounding enhanced benders decomposition for multiclass service-system staffing and scheduling with arrival rate uncertainty, Man. Sci. 63(7), 2016, pp. 2073–2091.

[8] H. Huang, W. Lin, Z. Lin, Z. Hao and A. Lim, An evolutionary algorithm based on constraint set partitioning for nurse rostering problems, Neur. Comp. App. 25(3- 4)2014, pp. 703–715.

[9] K. Kim and S. Mehrotra, A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management, Oper. Res. 63(6), 2015, pp. 1431–1451.

[10] A. Parisio and C.N Jones, A two-stage stochastic programming approach to employee scheduling in retail outlets with uncertain demand, Omeg, 53, 2015, pp. 97–103.

[11] M.I. Restrepo, L. Lozano and A.L. Medaglia, Constrained network-based column generation for the multi-activity shift scheduling problem, Int. J. Pro. Econ 140(1), 2012, pp. 466–472.

[12] M.I. Restrepo, B. Gendron and L.M. Rousseau, A two-stage stochastic programming approach for multi-activity tour scheduling, Eu. J. Oper. Res. 262(2), 2017, pp. 620–635.

[13] J.E. Baker, Adaptive selection methods for genetic algorithms, Proc. Int. Con. Gen. Alg., Hillsdale, New–Jersey, 1985, pp. 101–111.

[14] L. Davis, Handbook of genetic algorithms, CUMINCAD, 1991.

[15] C.L. Huntley and D.E. Brown, A parallel heuristic for quadratic assignment problems, Comp. Oper. Res. Elsevier, 18(3), 1991, pp. 275–289.

[16] P.B. Garrett, Abstract algebra, CRC Press,2007.

[17] J.F. Benders, Partitioning procedures for solving mixed-variables programming problems, Num Math. Springer, 4(1), 1962, pp. 238–252.

[18] IBM ILOG, CPLEX Release 12.6.3.0, 2016.

[19] GAMS Development Corporation, General Algebraic Modeling System (GAMS) Release 24.7.4, Washington, DC, 2016.