Approximations with Improving Error Bounds for Makespan Minimization in Batch Manufacturing Approximations with Improving Error Bounds for Makespan Minimization in Batch Manufacturing

by Weyerman, Whitney Samuel

Multipurpose batch manufacturing systems allow a suite of job types to be processed with a fixed set of machines. These types of systems are commonly found in chemical processing, as well as in computer systems and the service industry. In this thesis we consider the problem of sequencing jobs entering the manufacturing system in order to minimize makespan, or total time to complete processing of the jobs. We formulate this problem as a dynamic programming problem and illustrate the computational difficulty of solving this problem. We give a method for simulation of the system by representing each machine in the system as a finite state automata. This allows one to calculate the makespan given a manufacturing system and a sequence.

Due to the complexity of the system, we offer an approximation to the problem. We show that the approximation strategy allows refinement. This progressive refinement of the approximation results in a sequence of approximations that approach the true problem. As the approximation is refined, the computational complexity of the approximated problem grows.

For a simplified system, we show that the approximation has bounded error. Furthermore, we show that the error bound of the approximation sequence improves as the approximation approaches the true problem. This presents a trade-off between computational complexity and accuracy of the solution. A decision maker using this sequence of approximations can quickly determine a level of approximation based on the amount of computational power available and the accuracy needed in a solution.