Abstract
We propose two exact methods to solve an integrated employee-timetable and job-shop-scheduling problem. The problem is to find a minimum cost employee-timetable, where employees have different competences and work during shifts, so that the production, that corresponds to a job-shop with resource availability constraints, can be achieved. We introduce two new exact procedures: (1) a decomposition and cut generation approach and (2) a hybridization of a cut generation process with a branch and bound strategy. We also propose initial cuts that strongly improve these methods as well as a standard MIP approach. The computational performances of those methods on benchmark instances are compared to that of other methods from the literature.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
In our implementation, those variables are not created. Variables x eks are thus created if and only if the employee e can work on machine k (k∈K e ) and is available on shift s (s∈S e ).
\(\mathit {gap}=\min (1, \frac{|\mathit{value}-\varTheta ^{*}|}{\varTheta ^{*}} )\) if a solution value has been found, 1 otherwise.
References
Alfares, H. K., & Bailey, J. E. (1997). Integrated project task and manpower scheduling. IIE Transactions, 29, 711–717.
Aggoune, R. (2002). Ordonnancement d’ateliers sous contraintes de disponibilité des machines. PhD thesis, Université de Metz.
Aggoune, R. (2004a). Minimizing the makespan for the flow shop scheduling problem with availability constraints. European Journal of Operational Research, 153, 534–543.
Aggoune, R. (2004b). Une procédure par séparation et évaluation pour l’ordonnancement d’un job-shop sous contraintes de disponibilité. In Proceedings of 5e conférence Francophone de MOdélisation et SIMulation, MOSIM’04, Nantes, France.
Artigues, C., Gendreau, M., Rousseau, L.-M., & Vergnaud, A. (2009). Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound. Computers & Operations Research, 36, 2330–2340.
Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(4), 238–252.
Blazewicz, J., Finke, G., Haupt, R., & Schmidt, G. (1988). New trends in machine scheduling. European Journal of Operational Research, 37(3), 303–317.
Carlier, J. (1975). Ordonnancement à contraintes disjonctives. Thèse de 3ème cycle. PhD thesis, Paris VI.
Carlier, J. (1982). The one-machine sequencing problem. European Journal of Operational Research, 11, 42–47.
Chen, Z.-L. (2004). Simultaneous job scheduling and resource allocation on parallel machines. Annals of Operations Research, 129, 135–153.
Carlier, J., & Pinson, É. (1989). An algorithm for solving the job-shop problem. Management Science, 35, 164–176.
Carlier, J., & Pinson, É. (1990). A practical use of Jackson’s preemptive schedule for solving the job-shop problem. Annals of Operations Research, 26, 169–287.
Carlier, J., & Pinson, É. (1994). Adjustement of heads and tails for the job-shop problem. European Journal of Operational Research, 78(2), 146–161.
Carlier, J., Péridy, L., Pinson, É., & Rivreau, D. (2004). Elimination rules for job-shop scheduling problem: overview and extensions. In Handbook of scheduling: algorithms, models and performance analysis. Boca Raton: CRC Press (Chap. 4).
Daniels, R. L., & Mazzola, J. B. (1994). Flow shop scheduling with resource flexibility. Operations Research, 42, 504–522.
Ernst, A. T., Houyuan, J., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: a review of applications, methods and models. European Journal of Operational Research, 153, 3–27.
Gharbi, A., & Haouari, M. (2005). Optimal parallel machines scheduling with availability constraints. Discrete Applied Mathematics, 148, 63–87.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman.
Guyon, O., Lemaire, P., Pinson, É., & Rivreau, D. (2010). Cut generation for an integrated employee timetabling and production scheduling problem. European Journal of Operational Research, 201(2), 557–567.
Hooker, J. N., & Ottosson, G. (2003). Logic based Benders decomposition. Mathematical Programming Series A, 96, 33–60.
Hooker, J. N. (2005). A hybrid method for planning and scheduling. Constraints, 10, 385–401.
Hooker, J. N. (2007). Planning and scheduling by logic-based benders decomposition. Operations Research, 55, 588–602.
Lee, C.-Y. (1996). Machine scheduling with an availability constraint. Journal of Global Optimization, 9, 395–416.
Leung, J. Y.-T. (2004). Handbook of scheduling: algorithms, models and performance analysis. Boca Raton: CRC Press.
Liao, L.-W., & Sheen, G.-J. (2008). Parallel machine scheduling with machine availability and eligibility constraints. European Journal of Operational Research, 184, 458–467.
Mauguière, P., Billaut, J.-C., & Bouquard, J.-L. (2005). New single machine and job-shop scheduling problems with availability constraints. Journal of Scheduling, 8, 211–231.
Ma, Y., Chu, C., & Zuo, C. (2010). A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 58(2), 199–211.
Martin, P., & Shmoys, D. B. (1996). A new approach to computing optimal schedules for the job-shop scheduling problem. In Proceedings of the 5th international IPCO conference (pp. 389–403).
Pinedo, M. (2004). Scheduling: theory, algorithms and systems (2nd ed.). New York: Prentice Hall.
Rivreau, D. (1999). Problèmes d’ordonnancement disjonctifs: règles d’élimination et bornes inférieures. PhD thesis, Université de Technologie de Compiègne.
Rinnooy Kan, A. H. G. (1976). Machine scheduling problems: classification, complexity and computation. Norwell: Kluwer Academic.
Roy, B., & Sussman, B. (1964). Les problèmes d’ordonnancement avec contraintes disjonctives.
Savelsbergh, M. W. P. (1994). Preprocessing and probing techniques for mixed integer programming problems. INFORMS Journal on Computing, 6(4), 445–454.
Schmidt, G. (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121, 1–15.
Soumis, F., Pesant, G., & Rousseau, L.-M. (2005). Gestion de production et ressources humaines. In Gestion des horaires et affectation du personnel. Montreal: Presses Internationales Polytechnique (Chap. 4).
Sanlaville, É., & Schmidt, G. (1998). Machine scheduling with availability constraints. Acta Informatica, 35, 795–811.
Wang, G., Sun, H., & Chu, C. (2005). Preemptive scheduling with availability constraints to minimize total weighted completion times. Annals of Operations Research, 133, 183–192.
Zribi, N. (2005). Ordonnancement des job-shops flexibles sous contraintes de disponibilité des machines. PhD thesis, Université des sciences et technologies de Lille.
Acknowledgements
The authors wish to thank Christian Artigues for kindly giving us access to his code and test problems. Thanks are also due to the anonymous referees who provided useful comments and suggestions that led to improvements in the paper.
Author information
Authors and Affiliations
Corresponding author
Computing environment
Computing environment
All experiments have been carried out on a standard PC (Intel(R) Core(TM) i3 CPU M 370 @ 2.40 GHz, 2.39 GHz, 3.42 Go RAM) running MS Windows XP. Our own procedures are implemented in Java. The software of Artigues et al. (2009) is the original one, kindly provided by the authors, and is written in C++. Mixed integer and/or continuous linear programs have been solved with Ilog Cplex 12.2; for constraint based scheduling, we used Ilog Solver 6.7 and Scheduler 6.7.
Rights and permissions
About this article
Cite this article
Guyon, O., Lemaire, P., Pinson, É. et al. Solving an integrated job-shop problem with human resource constraints. Ann Oper Res 213, 147–171 (2014). https://doi.org/10.1007/s10479-012-1132-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-012-1132-3