MICRO-BOSS: A micro-opportunistic factory scheduler

摘要

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 used later to compactly complete each job schedule (i.e., to reduce work-in-process inventory within each job). 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 revise the current scheduling strategy dynamically 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 reduction in schedule costs.