Identical parallel machine scheduling problems: structural patterns, bounding techniques and solution procedures

The work is about fundamental parallel machine scheduling problems which occur in manufacturing systems where a set of jobs with individual processing times has to be assigned to a set of machines with respect to several workload objective functions like makespan minimization, machine covering or workload balancing. In the first chapter of the work an up-to-date survey on the most relevant literature for these problems is given, since the last review dealing with these problems has been published almost 20 years ago. We also give an insight into the relevant literature contributed by the Artificial Intelligence community, where the problem is known as number partitioning. The core of the work is a universally valid characterization of optimal makespan and machine-covering solutions where schedules are evaluated independently from the processing times of the jobs. Based on these novel structural insights we derive several strong dominance criteria. Implemented in a branch-and-bound algorithm these criteria have proved to be effective in limiting the solution space, particularly in the case of small ratios of the number of jobs to the number of machines. Further, we provide a counter-example to a central result by Ho et al. (2009) who proved that a schedule which minimizes the normalized sum of squared workload deviations is necessarily a makespan-optimal one. We explain why their proof is incorrect and present computational results revealing the difference between workload balancing and makespan minimization. The last chapter of the work is about the minimum cardinality bin covering problem which is a dual problem of machine-covering with respect to bounding techniques. We discuss reduction criteria, derive several lower bound arguments and propose construction heuristics as well as a subset sum-based improvement algorithm. Moreover, we present a tailored branch-and-bound method which is able to solve instances with up to 20 bins