An Algorithm for an Optimal Staffing Problem in Open Shop Environment

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.

Authors:

• Daniela I. Borissova
• Ivan C. Mustakerov

Keywords:

• Integer programming
• open shop problem
• optimal staffing.

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.