An Algorithm for an Optimal Staffing Problem in Open Shop Environment

Authors: Daniela I. Borissova, Ivan C. Mustakerov

Abstract:

The paper addresses a problem of optimal staffing in open shop environment. The problem is to determine the optimal number of operators serving a given number of machines to fulfill the number of independent operations while minimizing staff idle. Using a Gantt chart presentation of the problem it is modeled as twodimensional cutting stock problem. A mixed-integer programming model is used to get minimal job processing time (makespan) for fixed number of machines' operators. An algorithm for optimal openshop staffing is developed based on iterative solving of the formulated optimization task. The execution of the developed algorithm provides optimal number of machines' operators in the sense of minimum staff idle and optimal makespan for that number of operators. The proposed algorithm is tested numerically for a real life staffing problem. The testing results show the practical applicability for similar open shop staffing problems.

Keywords: Integer programming, open shop problem, optimal staffing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329761

References:

[1] R. W. Griffin. Principles of Management. Houghton Mifflin Company, 2007, 459 pages.
[2] I. Blochlinger. Modeling staff scheduling problems. A Tutorial. European Journal of Operational Research, vol. 158, pp. 533-542 2004.
[3] K. Miwa, S. Takakuwa. "Optimization and analysis of staffing problems at a retail store", in Proc. 2010 Winter Simulation Conf., 2010, pp. 1911- 1923.
[4] A. Malapert, H. Cambazard, N. Jussien, A. Langevin, L.-M. Rousseau, "An optimal constraint programming approach to the open-shop problem". NFORMS Journal on Computing, vol. 24, no. 2, pp. 228-244, 2012.
[5] J. B┼éażewicza, E. Peschb, M. Sternaa, F. Werner. Open shop scheduling problems with late work criteria. Discrete Applied Mathematics, vol. 134, no 1-3, 2004, pp. 1-24.
[6] S. Hasija, E. Pinker, R.A. Shumsky. Capacity estimation and optimal staffing for an email contact center. 2008, http://mba.tuck.dartmouth.edu/pages/faculty/robert.shumsky/contact_ center_estimation_july_2008.pdf
[7] D. Bai, L. Tang. Open shop scheduling problem to minimize makespan with release dates. Applied Mathematical Modelling, vol. 37, no 4, pp. 2008-2015, 2013.
[8] A. Lodi, S. Martello, M. Monaci. Two-dimensional packing problems: A survey. European Journal of Operational Research. vol. 141, no 2, pp. 241-252, 2002.
[9] S. Imahori, M. Yagiura, H. Nagamochi. Practical Algorithms for Twodimensional Packing. Mathematical engineering technical reports, METR 2006-19, 2006, http://www.keisu.t.utokyo. ac.jp/research/techrep/data/2006/METR06-19.pdf
[10] F. Vanderbeck. A nested decomposition approach to a three-stage, twodimensional cutting stock problem. Management Science, vol. 47, no 6, pp. 864-879, 2001.
[11] J. Puchinger, G. R. Raidl. Models and algorithms for three-stage twodimensional bin packing. European Journal of Operational Research, vol. 183, no 3, pp. 1304-1327, 2007.
[12] M. Hifi, R. M-Hallah. A hybrid algorithm for the two-dimensional layout problem: the cases of regular and irregular shapes. International Transactions in Operational Research, vol. 10, no 3, pp. 195-216, 2003.
[13] J. Kallrath, Y. Kochetov, A. Rudnev. "Strip packing problem for circles and rectangles". 4th ESICUP Meeting, Tokyo, 2007, p. 20.
[14] H. L. Gantt. Work, Wages and Profit. The Engineering Magazine, 1910; republished as Work, Wages and Profits, Easton, Pennsylvania, Hive Publishing Company, 1974, ISBN 0-87960-048-9.
[15] Lindo Systems ver. 12, http://www.lindo.com.