×
Krishnamoorthy, Mohan; Ernst, Andreas T.; Baatar, Davaatseren

Algorithms for large scale shift minimisation personnel task scheduling problems. (English) Zbl 1244.90094

Eur. J. Oper. Res. 219, No. 1, 34-48 (2012).
Summary: We introduce the Personnel Task Scheduling Problem (PTSP) and provide solution algorithms for a variant of this problem known as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). The PTSP is a problem in which a set of tasks with fixed start and finish times have to be allocated to a heterogenous workforce. Personnel work in shifts with fixed start and end times and have skills that enable them to perform some, but not all tasks. In other words, some personnel are qualified to only perform a subset of all tasks. The objective is to minimise the overall cost of personnel required to perform the given set of tasks. In this paper we introduce a special case in which the only cost incurred is due to the number of personnel (shifts) that are used. This variant of the PTSP is referred to as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). While our motivation is a real-life Personnel Task Scheduling Problem, the formulation may also be applied to machine shop scheduling. We review the existing literature, provide mathematical formulations, and develop a heuristic approach for the SMPTSP.

Cited in 18 Documents

MSC:

90B35 Deterministic scheduling theory in operations research

Keywords:

scheduling; Lagrangean relaxation; task scheduling; machine scheduling; personnel scheduling
PDF BibTeX XML Cite
\textit{M. Krishnamoorthy} et al., Eur. J. Oper. Res. 219, No. 1, 34--48 (2012; Zbl 1244.90094)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Dowling, D.; Krishnamoorthy, M.; Mackenzie, H.; Sier, D., Staff rostering at a large international airport, The annals of operations research, 72, 125-147, (1997) · Zbl 0895.90137
[2] Ernst, A.T.; Jiang, H.; Krishnamoorthy, M.; Owens, B.; Sier, D., An annotated bibliography of personnel scheduling and rostering, Annals OR, 127, 1-4, 21-144, (2004) · Zbl 1090.90078
[3] Ernst, A.T.; Jiang, H.; Krishnamoorthy, M.; Sier, D., Staff scheduling and rostering: A review of applications, methods and models, European journal of operational research, 153, 1, 3-27, (2004) · Zbl 1053.90034
[4] Krishnamoorthy, M.; Ernst, A.T., The personnel task scheduling problem, (), 343-368 · Zbl 0978.90048
[5] Valls, V.; Pérez, A.; Quintanilla, S., A graph colouring model for assigning a heterogenous workforce to a given schedule, European journal of operations research, 90, 285-302, (1996) · Zbl 0916.90158
[6] Gertsbakh, I.; Stern, H.I., Minimal resources for fixed and variable job schedules, Operations research, 26, 68-85, (1978) · Zbl 0371.90058
[7] Fischetti, M.; Martello, S.; Toth, P., Approximation algorithms for fixed job schedule problems, Operations research, 40, S1, S96-S108, (1992) · Zbl 0764.90044
[8] Gupta, U.I.; Lee, D.T.; Leung, Y.T., An optimal solution for the channel assignment problem, IEEE transactions on computing C, 28, 807-810, (1979) · Zbl 0422.68031
[9] Nakajima, K.; Hakimi, S.L.; Lenstra, J.K., Complexity results for scheduling tasks in fixed intervals on two types of machines, SIAM journal on computing, 11, 512-520, (1982) · Zbl 0486.68020
[10] Arkin, M.; Silverberg, B., Scheduling jobs with fixed start and end times, Discrete applied mathematics, 18, (1987) · Zbl 0636.90042
[11] Fischetti, M.; Martello, S.; Toth, P., The fixed job schedule problem with spread-time constraints, Operations research, 35, 6, 849-858, (1987) · Zbl 0638.90055
[12] Fischetti, M.; Martello, S.; Toth, P., The fixed job schedule problem with working-time constraints, Operations research, 37, 3, 395-403, (1989) · Zbl 0672.90074
[13] Kroon, L.G.; Salomon, M.; Wassenhowe, L.N.V., Exact and approximation algorithms for the tactical fixed interval scheduling problem, Operations research, 45, 4, 624-638, (1997) · Zbl 0887.90089
[14] Gondran, M.; Minoux, M., Graphs and algorithms, (1984), A Wiley-Interscience Publication, John Wiley New York · Zbl 1117.06010
[15] Kolen, A.W.; Lenstra, J.K.; Papadimitriou, C.H.; Spieksma, F.C., Interval scheduling: A survey, Naval research logistics, 54, 5, 530-543, (2007) · Zbl 1143.90337
[16] Barahona, F.; Anbil, R., The volume algorithm: producing primal solutions with a subgradient method, Mathematical programming, 87, 385-399, (2000) · Zbl 0961.90058
[17] Bastert, O.; Hummel, B.; de Vries, S., A generalized wedelin heuristic for integer programming, INFORMS journal on computing, 22, 93-107, (2010) · Zbl 1243.90133
[18] Wedelin, D., An algorithm for large scale 01 integer programming with application to airline crew scheduling, The annals of operations research, 57, 283-301, (1995) · Zbl 0831.90087
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.