Evolving dispatching rules for dynamic Job shop scheduling with uncertain processing times

摘要

Dynamic Job shop scheduling (DJSS) is a complex and hard problem in real-world manufacturing systems. In practice, the parameters of a job shop like processing times, due dates, etc. are uncertain. But most of the current research on scheduling consider only deterministic scenarios. In a typical dynamic job shop, once the information about a job becomes available it is considered unchanged. In this work, we consider genetic programming based dispatching rules to generate schedules in an uncertain environment where the process time of an operation is not known exactly until it is finished. Our primary goal is to investigate methods to incorporate the uncertainty information into the dispatching rules. We develop two training approaches, namely ex-post and ex-ante to evolve the dispatching rules to generate good schedules under uncertainty. Both these methods consider different ways of incorporating the uncertainty parameters into the genetic programs during evolution. We test our methods under different scenarios and the results compare well against the existing approaches. We also test the generalization capability of our methods across different levels of uncertainty and observe that the proposed methods perform well. In particular, we observe that the proposed ex-ante training approach outperformed other methods.