Production Scheduling and Rescheduling with Genetic Algorithms

A general model for job shop scheduling is described which applies to static, dynamic and non-deterministic production environments. Next, a Genetic Algorithm is presented which solves the job shop scheduling problem. This algorithm is tested in a dynamic environ- ment under different workload situations. Thereby, a highly efficient decoding procedure is proposed which strongly improves the quality of schedules. Finally, this technique is tested for scheduling and rescheduling in a non-deterministic environment. It is shown by experi- ment that conventional methods of production

control are clearly outperformed at reasonable runtime costs. Keywords Genetic algorithm, permutation representation, tunable decoding, job shop scheduling prob- lem, dynamic scheduling. 1 Introduction With the spread of automated manufacturing systems the optimization problem of assigning operations to a set of machines receives increasing attention (Parunak, 1992). From the viewpoint of combinatorial optimization the issue of finding an optimal production schedule is known to be NP-hard (Błazewicz et al., 1996). Therefore particular attention is paid to local search-based heuristics (Anderson et al., 1997) including Genetic Algorithms (GA). A good deal of previous research on GAs in scheduling concentrates on the static job shop prob- lem (Mattfeld, 1996). However, production is an activity of sustained pursuit and therefore production scheduling is actually a dynamic task. In a manufacturing system all jobs have release times which define their date of arrival at the shop floor. Job releases are typically unforeseen events and, consequently, neither the release times of jobs nor their specific processing requirements are known in advance. Therefore, scheduling is a non-deterministic problem dealing with an open time horizon. The control of the jobs in a manufacturing system is referred to as rescheduling because unforeseen events frequently require schedule revisions. In practice predominantly priority-rule based control is used (Baker, 1974). The temporal decomposition of the non-deterministic problem into a series of dynamic, but deterministic c#0D1999 by the Massachusetts Institute of Technology Evolutionary Computation 7(1): 1-17 C. Bierwirth and D. Mattfeld problems also opens this domain for optimization methods (Raman and Talbot, 1993). Since already small improvements of the schedule quality obtained by optimization often lead to considerable cost reductions, advanced optimization techniques are highly appreciated. The transfer of GA experiences to production control was first approached in Bierwirt et al. (1995) and has been taken up recently in Lin et al. (1997) by addressing the GA effectiveness. We think that the GA efficiency is of predominant importance. So far, however, the GA runtimes have hindered a thorough computational study as usually done for priority-rule based scheduling. This paper proposes an optimization method for the problem sketched above. In Sec- tion 2 we first review the static job shop problem. Next we extend the static scheduling problem to a dynamic one. In Section 3 we present a GA capable of solving the dynamic job shop problem. In Section 4 a highly efficient decoding procedure is presented and evaluated by experiment. In Section...

Website: mitpress.mit.edu | Filesize: -
No of Page(s): 17
Download Production Scheduling and Rescheduling with Genetic Algorithms.pdf