## Invited Session Fri.1.H 2033

#### Friday, 10:30 - 12:00 h, Room: H 2033

**Cluster 11: Integer & mixed-integer programming** [...]

### Integer programming approaches to job scheduling

**Chair: Jeff Linderoth**

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

**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.

**Friday, 11:00 - 11:25 h, Room: H 2033, Talk 2**

**Riley Martin Clement**

A big-bucket time-indexed formulation for nonpreemptive single machine scheduling problems

**Coauthors: Natashia Lesley Boland, Hamish Alfred Waterer**

**Abstract:**

Nonpreemptive single machine scheduling problems require a set of jobs to be scheduled on a single machine such that each job is processed exactly once without interruption and the machine processes at most one job at a time. The classical time-indexed (TI) formulation of this problem discretizes a planning horizon into periods of unit length. We

present a big-bucket time-indexed (TIBB) formulation in which the length of each period is no larger than the processing time of the shortest job. The two models are equivalent in the case that this job has unit processing time. When the minimum processing time is larger than the greatest common divisor of the problem input data the TIBB model has fewer periods than the TI model. We show how to adapt facet-defining inequalities for the TI model to the TIBB model and describe conditions under which they are facet-defining. Computational experiments compare the performance of the TIBB model to the TI model for both weighted completion time and weighted tardiness instances described in the literature.

**Friday, 11:30 - 11:55 h, Room: H 2033, Talk 3**

**Hamish Waterer**

Maintenance scheduling in critical infrastructure networks

**Coauthors: Natashia Boland, Thomas Kalinowski, Zheng Lanbo**

**Abstract:**

Many infrastructure systems critical to modern life take the form of a

flow in a network over time. For example, utilities such as water,

sewerage and electricity all flow over networks. Products are

manufactured and transported via supply chain networks. Such networks

need regular, planned maintenance in order to continue to function. A

maintenance job causes arc outages for its duration, potentially

reducing the capacity of the network for that period. The coordinated

timing of maintenance jobs can have a major impact on the network

capacity lost to maintenance. This issue drives an annual maintenance

scheduling process at the Hunter Valley Coal Chain, which supplies the

world's largest coal export operation at the port of Newcastle,

Australia, and has motivated this work. Here we describe the

background to the problem, how we model it, and our solution approach.

The results on instances derived from real-world data will be

presented