Multi-contextual ant colony optimization of intermediate dynamic job shop problems

Myopic scheduling uses information without correct context. Because job shops with dynamic job arrival are NP-hard, real-world planners often resort to myopic dispatching rules that produce schedules with unsatisfactory makespans and mean flow times. If metaheuristic scheduling does not use context properly, it can produce unsatisfactory schedules. This study proposes a new theory of context-dependent and multi-contextual scheduling functions in dynamic job shops. Three multi-contextual ant colony (MCAC) scheduling methods, SPT_MIT_JWT, MRT_MIT, and LRT_MIT_JWT, were designed to combine several context-dependent functions so that each ant had an independent, artificially intelligent model of what might happen in the future. These three MCACs scheduled 27 dynamic job shops. Each job shop had three parameters (number of operations per job, processing time per operation, and utilization level) at one of three levels. The results were compared to schedules from dispatching rules. Schedules from MRT_MIT had the best makespans for all 27 combinations of factors. For five cases in which utilization and operations per job were both high, schedules from longest processing time had the best mean flow time; in the other 22 cases, either SPT_MIT_JWT or LRT_MIT_JWT produced the schedule with the best mean flow time. These results indicate that the new theory can be used to design multi-contextual methods that produce effective schedules.