MICRO-BOSS: A Micro-Opportunistic Factory Scheduler

Abstract

Recent research in factory scheduling has demonstrated the benefits of building schedules by first optimizing the sequencing of bottleneck machines, namely machines whose utilizations are expected to be particularly high. Within this approach, two scheduling perspectives are generally adopted: a resource-centered perspective is used to help maximize the utilization of bottleneck machines and a job-centered perspective is later used to compactly complete each job schedule (i.e., reduce work-in-process inventory). Because new secondary bottlenecks may arise during the construction of the schedule, recent scheduling systems have been designed with an ability to switch back and forth between their resource-centered scheduling perspective and their job-centered scheduling perspective. This ability to dynamically revise the current scheduling strategy has been termed opportunistic scheduling. However, because these schedulers require scheduling large resource subproblems or large job subproblems before revising their scheduling strategy, we refer to them as macro-opportunistic schedulers. Instead, this paper describes MICRO-BOSS, a so-called micro-opportunistic scheduler that can revise its scheduling strategy each time an operation is scheduled. Experimental results suggest that the extra flexibility of a micro-opportunistic approach to scheduling often translates into important reductions in schedule costs.