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


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


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


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


  Florida Payday Loans can help you in trying times, but be sure to know the laws necessary for your loan application. But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.