David West and Dr. Sean Warnick, Computer Science

Many industrial companies, especially ones that produce chemicals, use a batch manufacturing process to make their product. In a batch manufacturing process, a sequence of machines take “batches” of material and progressively perform actions until the final product is produced. One goal of managers of these companies is to schedule these batches on the machines such that the production line is most efficiently utilized. To solve for this exactly is computationally hard in the average case. My project was to formulate a new mathematical model that would allow for computationally tractable optimizations to this problem.

As I had precious little previous experience formulating mathematical models, Dr. Sean Warnick’s assistance was invaluable. I proposed several approaches to the problem before an approach which attempted merely to minimize “dead space” or machine non-utilization was selected. Dead space occurs primarily when one product is switched off the assembly line to make room for another product. Finding the optimal sequence of switching minimizes dead space. To model this, each machine was viewed as a simple finite-state automata, which is a mathematical entity that changes state based on its current state and current input and a defined set of transition rules. These automata were organized into a dynamic system, or set of automata, that comprised the state of the entire system. This dynamic system revealed patterns within the batch scheduling system that allowed it to converted into a simpler graph traversal problem and solved using integer programming techniques.

During the course of my research, I was offered a summer internship at Amazon.com, which I accepted. This took time away from the project. Fortunately, Dr. Warnick hired a talented fellow research assistant, Sam Weyerman, who continued the research and organized it into a scientific paper . This paper, titled “Sub-Optimal Scheduling of a Multi-Product Batch Manufacturing System using an Integer Programming Solution,” outlines the mathematics behind the project and demonstrates an example batch manufacturing system to which the model is successfully applied. It was submitted to and published in the 2005 American Control Conference held in Portland, Oregon . The reader of this ORCA final report is strongly encouraged to look at the paper for further information about the results of the research.

I want to thank ORCA for their generous funding of my research and the university donors that make ORCA possible. This experience was extremely valuable to me and has provided a great deal of direction for my academic future.