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

**Valentina Cacchiani**

Fixed job scheduling with resource constraints

**Coauthors: Alberto Caprara, Paolo Toth**

**Abstract:**

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"** [...]