Scheduling to Minimize Tardiness on Parallel Machines with Family Setups

Abstract

The scheduling of jobs to minimize some function of job tardinesses is a common and difficult problem. Here we consider the scheduling of jobs in a particular factory to minimize the sum of job tardinesses. Jobs have different processing times and due dates, and belong to families according to the mould that each job requires. There are multiple identical machines but the number of moulds available for each job family is limited. On a given machine, setups are not required between jobs of the same family but are required between jobs of different families to load and prepare the incoming mould, and such setups use the machine and incoming mould for a setup period. We first consider some simple formulations that fail to model the problem, before considering two full formulations — a time-indexed job-based integer programme (IP) model and a time-indexed batch-based IP model; each can be solved for problem instances of sizes appropriate for the factory we are studying. We explore a column generating method for solving the batch-based model and compare its performance to the job-based model for randomly generated test problem instances. We apply the two models to sets of data from the factory and discuss their applicability to the data instances we have access to.