A dynamic programming based algorithm for the crew scheduling problem

A dynamic programming based algorithm for the crew scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor19991644
Country: United Kingdom
Volume: 25
Issue: 7/8
Start Page Number: 567
End Page Number: 582
Publication Date: Jul 1998
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: dynamic
Abstract:

In this paper we consider the crew scheduling problem, that is the problem of assigning K crews to tasks with fixed start and finish times such that each crew does not exceed a limit on the total time it can spend working. This problem is formulated as a problem of finding K time limit constrained vertex disjoint paths which visit all vertices on a network. A lower bound for the problem is found via dynamic programming. This lower bound is improved via a Lagrangean based penalty procedure and subgradient optimisation. Computational results are given for a number of randomly generated problems involving between 50 and 500 tasks.

Reviews

Required fields are marked *. Your email address will not be published.