Three essays in parallel machine scheduling

This research consists of three essays in parallel machine scheduling. The first two essays focus on the parallel multipurpose machine scheduling problem, while the last focuses on the parallel identical machine scheduling problem. In the first essay, a branch and bound procedure for assigning jobs to parallel multipurpose machines is developed and tested. Multipurpose machines can process some of the jobs, but not necessarily all of them. All the machines that can process a particular job require the same amount of time to complete it. This algorithm uses the particular structure of the multipurpose machine problem to improve the lower and upper bound at any node rather than solving the linear programming relaxation problem at every node. This enables the algorithm to outperform the prior algorithm written to solve the parallel multipurpose machine problem.; The second essay focuses on developing theoretical techniques to exploit the specific structure of the problem in order to gain greater efficiency. This is important if we are to solve more challenging problems occurring in real world scenarios. This essay has two sections. The first section focuses on decomposing the problem into smaller subproblems that can each be solved efficiently. In the second section, we develop multiple improved lower bounds for the problem, and also develop a heuristic that can be used when these lower bounds are superior to the linear programming relaxation lower bound. Under certain conditions, both the decomposition and the lower bounding techniques substantially reduce the computational time of the original branch and bound procedure, as well as the time required if we solve the problem with Integer Programming software.; In the third essay, we optimize a bi-criteria problem of minimizing a weighted function of the makespan and the cost of assigning jobs to the machines for the identical parallel machine problem. In this problem, each machine is able to process every job, and the amount of time required to complete the job is the same regardless of which machine processes it. The cost of assigning a job to the machine depends on the machine and the processing time of the job. We develop a procedure to estimate the lower and upper bound on the values of the makespan in the optimal solution. We also estimate the maximum number of machines with non-zero assignments in the optimal solution. By developing these problem specific constraints, the computation time of the integer programming software was substantially reduced.