MASTH-Minimum Auction Spanning Task Hierarchy
Abstract: As manufacturing grows more sophisticated and dynamic, methods of scheduling tasks to a limited pool of machines become especially relevant and important. The flexible job shop problem (FJSP) assigns machines with different capabilities and processing speeds to tasks while optimizing makespan or another objective. Because the FJSP’s search space grows combinatorially with the number of tasks and machines, methods such as mixed-integer linear programming (MILP), greedy heuristics, and Tabu search can struggle with either runtime or solution quality at larger scales. This project introduces Minimum Auction Spanning Task Hierarchy (MASTH), a metaheuristic that combats combinatorial growth by exploiting inherent similarities among tasks and machines. MASTH consists of deterministic assignment nodes that respond to stimuli by delegating and reassigning machines to open tasks. These nodes operate using only locally available information, allowing for MASTH to operate within a distributed system. Arranging these nodes hierarchically limits the number of machines considered for each task: rather than searching the full machine population, the hierarchy searches for machines that are nearby in its artificial space. If a hierarchy is well constructed (e.g., the distances between tasks in the hierarchy correlate to how apt a machine operating on one task is for another) the closest available machine is likely an adequate candidate for a task. MASTH offers assignment schedules significantly faster than MILP for larger scenarios and offers plans with makespans shorter than a Tabu search.
Advisor: Professor Kevin Leahy
Zoom link: https://wpi.zoom.us/j/99383275406.