Friday, 10:30 - 10:55 h, Room: H 2033


Valentina Cacchiani
Fixed job scheduling with resource constraints

Coauthors: Alberto Caprara, Paolo Toth


We study the following general scheduling problem: a set of fixed jobs having start time, end time and weight must be scheduled on a set of machines having a capacity, a cost and capable of executing at most one job at a time. Each job must be executed by a set of machines such that their overall capacity satisfies the job weight. In addition, a setup time must be respected between the execution of two jobs on the same machine, that depends on the two jobs. The goal is to determine the minimum cost schedule. We also study some variants of the problem, one of them having application in Train Unit Assignment. All the considered scheduling problems are NP-hard. We provide a heuristic algorithm based on the optimal solution of the restricted problem associated with a peak period, i.e., with a subset of simultaneous jobs that must be executed on distinct machines. The heuristic algorithm is tested on real-world instances of the Train Unit Assignment and on realistic instances for all the variants and the general case. The results obtained are compared with results in the literature, showing the effectiveness of the new algorithm in providing good solutions in short computing time.


Talk 1 of the invited session Fri.1.H 2033
"Integer programming approaches to job scheduling" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.