“Arc-Flow models for some scheduling problems”
Venerdì 20 Dicembre 2024, ore 9:00 - Aula 2AB45 - Andrea Grosso (Università di Torino)
Abstract
Some scheduling problems are presented, for which it is possible to develop a graph representation and efficient solution approaches through arc-flow models. (1) In the minimization of total flowtime problems with ‘parallel batching’ processing, jobs to be processed on a machine are grouped into batches of limited capacity, and jobs within the same batch are processed simultaneously. The goal is to determine the grouping and sequencing of batches that minimizes the ‘average’ completion time. (2) In the problem of minimizing makespan on parallel machines with a common server, a set of jobs must be assigned for processing on parallel machines in order to minimize the overall completion time of the entire set of jobs. A complicating factor is the presence of a single agent (the ‘server’) required to set up each job for processing on the machine to which it is assigned. Jobs must therefore be scheduled in such a way that allows for this setup by the server. Again, the problem can be tackled by representing it as a suitable arc-flow based model.
