Family sequencing and cooperation

This paper analyzes a single-machine scheduling problem with family setup times both from an optimization and a cost allocation perspective. In a family sequencing situation jobs are processed on a single machine, there is an initial processing order on the jobs, and every job within a family has an identical cost function that depends linearly on its completion time. Moreover, a job does not require a setup when preceded by another job from the same family while a family specific setup time is required when a job follows a member of some other family.

Explicitly taking into account admissibility restrictions due to the presence of the initial order, we show that for any subgroup of jobs there is an optimal order, such that all jobs of the same family are processed consecutively. To analyze the allocation problem of the maximal cost savings, we define and analyze a so-called corresponding cooperative family sequencing game. Using nonstandard techniques we prove that each family sequencing game has a non-empty core by showing that a particular marginal vector belongs to the core. Finally, we specifically analyze the case in which the initial order is family ordered.