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


TB1 Scheduling 1
June 10, 2021  11:15 AM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.