Abstract

Heap models in the max-plus algebra are interesting dynamical systems that can be used to model a variety of tetris-like systems, such as batch flow shops for manufacturing models. Each heap in the model can be identified with a single product to manufacture. The objective is to manufacture a group of products in such an order so as to minimize the total manufacturing time. Because this scheduling problem reduces to a variation of the Traveling Salesman Problem (known to be NP-complete), the optimal solution is computationally infeasible for many real-world systems. Thus, a feasible approximation method is needed. This work builds on and expands the existing heap model in order to more effectively solve the scheduling problems. Specifically, this work:1. Further characterizes the admissible products to these systems.2. Further characterizes sets of admissible products. 3. Presents a novel algorithm, the asynchronous $t$-step approximation, to approximate these systems.4. Proves error bounds for the system approximation, and show why these error bounds are better than the existing approximation.

Degree

College and Department

Physical and Mathematical Sciences; Computer Science

Rights

http://lib.byu.edu/about/copyright/