Scheduling problems related with due date measures in parallel-machine shops

Abstract

This dissertation focuses on scheduling problems in parallel-machine shops with the objective of minimizing total tardiness. A parallel-machine shop consists of multiple machines that can process the same set of jobs independently. Generally, processors/machines at parallel-machine shops can be classified into three types according to the processing time of a job: identical processors, uniform processors and unrelated processors. We consider three different problems for parallel-machine scheduling, and develop algorithms for the problems. First, we consider an identical parallel-machine scheduling problem with the objective of minimizing total tardiness of jobs. Identical parallel machines can process the same set of jobs and the processing times of a job are the same on all the machines. We develop dominance properties, upper bounds and lower bounds on the total tardiness of a given set of jobs, and suggest a branch and bound algorithm that is developed using these properties and bounds. Secondly, we consider a scheduling problem in unrelated parallel-machine shops, which processing times of a job on different machines are arbitrarily different. The objective of the problem is to minimize total tardiness of a given set of jobs. In the problem considered here, we identify several optimal solution properties and develop dominance properties, lower bounds and upper bounds. To obtain an optimal solution, we devise a branch and bound algorithm using those properties and bounds with a new branching scheme developed in this research. Finally, we focus on the problem of scheduling jobs on identical parallel machines considering a job splitting property. In this problem, it is assumed that a job can be split into a discrete number of sub-jobs and they are processed on parallel machines independently. Here, a sub-job is a set or a batch of (identical) unit-jobs of a job that are processed on a machine consecutively. For the problem with the objective of minimizing total...