V. Cacchiani, P. Toth
Motivated by an application in railway systems, we study the following Fixed Job Schedule Problem. A set of fixed jobs, each with given start and end times, must be scheduled on a set of non-identical machines, each having a cost, and capable of executing one job at a time. Each job has a demand of resource, and each machine has a maximum resource capacity. Each job must be executed by a set of machines such that their overall capacity satisfies the job demand. In addition, a setup time must be respected between the execution of two jobs on the same machine. The goal is to determine the minimum cost schedule.
In the railway context, fixed jobs correspond to timetabled train trips characterized by a demand of passenger seats, and machines to train-units that can possibly be combined to provide more available seats.
In this work, we study two problem variants corresponding to two extreme cases: in the first one, exactly one machine is assigned to each job, while in the second one there is no limit on the number of machines assigned to each job. For these variants, we propose a heuristic algorithm, and test it on realistic instances of the train-unit assignment problem.
Keywords: Fixed job scheduling, Lower bound, Heuristic, Train-Unit Assignment
Scheduled
TB1 Scheduling 1
June 10, 2021 11:15 AM
1 - GB Dantzig
