2015 | OriginalPaper | Chapter
A Triplet-Based Exact Method for the Shift Minimisation Personnel Task Scheduling Problem
Authors : Davaatseren Baatar, Mohan Krishnamoorthy, Andreas T. Ernst
Published in: Algorithms - ESA 2015
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we describe a new approach for solving the shift minimisation personnel task scheduling problem. This variant of fixed job scheduling problems arises when tasks with fixed start and end times have to be assigned to personnel with shift time constraints. We present definitions, formulations and briefly discuss complexity results for the variant that focuses on minimising the number of machines (or workers) that are required to schedule all jobs. We first develop some mathematical properties of the problem and subsequently, the necessary and sufficient conditions for feasibility. These properties are used to develop a new branch and bound scheme, which is used in conjunction with two column generation based approaches and a heuristic algorithm to create an efficient solution procedure. We present extensive computational results for large instances and thereby, empirically demonstrate the effectiveness of our new approach.