Robust Machine Scheduling Based on Group of Permutable Jobs

This chapter presents the “group of permutable jobs” structure to represent set of solutions to disjunctive scheduling problems machine scheduling . Traditionally, solutions to disjunctive scheduling problems are represented by assigning sequence of jobs to each machine. The group of permutable jobs structure assigns an ordered partition of jobs to each machine, i.e. a group sequence. The permutation of jobs inside a group must be all feasible with respect to the problem constraints. Such a structure provides more flexibility to the end user and, in particular, allows a better reaction to unexpected events. The chapter considers the robust scheduling framework where uncertainty is modeled via a discrete set of scenarios, each scenario specifying the problem parameters values. The chapter reviews the models and algorithms that have been proposed in the literature for evaluating a group sequence with respect to scheduling objectives for a fixed scenario as well as the recoverable robust optimization methods that have been proposed for generating robust group sequence against scenario sets scenario set . The methods based on group sequences are compared with standard robust scheduling approaches based on job sequences. Finally, methods for exploiting group sequences in an industrial context are discussed and an experiment for human decision making in a real manufacturing system based on groups is reported.