NDLI: Models and algorithms for a staff scheduling problem

Content Provider	Springer Nature Link
Author	Caprara, Alberto Monaci, Michele Toth, Paolo
Copyright Year	2003
Abstract	We present mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. In these problems, the daily assignments to be performed are given and the durations (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. The main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. We decompose the problem into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. The first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. Practical experience shows that the best approach is based on the model in which variables are associated with feasible patterns and generated either by dynamic programming or by solving another ILP. The second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Although in general this procedure may not find a solution (even if one exists), we present sufficient conditions under which our approach is guaranteed to succeed. We also propose an iterative heuristic algorithm to handle the case in which no feasible solution is found in the second step. We present computational results on real life instances associated with an emergency call center. The proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months.
Starting Page	445
Ending Page	476
Page Count	32
File Format	PDF
ISSN	00255610
Journal	Mathematical Programming
Volume Number	98
Issue Number	1-3
e-ISSN	14364646
Language	English
Publisher	Springer-Verlag
Publisher Date	2003-04-10
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	staff scheduling integer linear programming column generation branch-and-bound maximum flow heuristic algorithms computational results
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A finite branch-and-bound algorithm for two-stage stochastic integer programs

Column generation for linear and integer programming (2012).

A linear integer programming bound for maximum-entropy sampling

Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference

An effective branch-and-bound algorithm for convex quadratic integer programming

Exact and heuristic methodologies for scheduling in hospitals: problems, formulations and algorithms

A Branch-and-Bound Algorithm for Solving the Multiprocessor Scheduling Problem with Improved Lower Bounding Techniques

Models and algorithms for configuring and testing prototype cars

Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference

Models and algorithms for a staff scheduling problem

Similar Documents

A finite branch-and-bound algorithm for two-stage stochastic integer programs

Column generation for linear and integer programming (2012).

A linear integer programming bound for maximum-entropy sampling

Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference

An effective branch-and-bound algorithm for convex quadratic integer programming

Exact and heuristic methodologies for scheduling in hospitals: problems, formulations and algorithms

A Branch-and-Bound Algorithm for Solving the Multiprocessor Scheduling Problem with Improved Lower Bounding Techniques

Models and algorithms for configuring and testing prototype cars

Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference

Models and algorithms for a staff scheduling problem