Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
A Triplet-Based Exact Method for the Shift Minimisation Personnel Task Scheduling Problem
verfasst von : Davaatseren Baatar, Mohan Krishnamoorthy, Andreas T. Ernst
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.