Automatic Generation of Dispatching Rules for Large Job Shops by Means of Genetic Algorithms

Abstract

Generating optimized large-scale production plans is an important open problem where even small improvements result in signi cant savings. Application scenarios in the semiconductor industry comprise thousands of machines and hundred thousands of job operations and are therefore among the most challenging scheduling problems regarding their size. In this paper we present a novel approach for automatically creating composite dispatching rules, i.e. heuristics for job sequencing, for makespan optimization in such large-scale job shops. The approach builds on the combination of event-based simulation and genetic algorithms. We introduce a new set of benchmark instances with proven optima that comprise up to 100000 operations to be scheduled on up to 1000 machines. With respect to this large-scale benchmark, we present the results of an experiment comparing well-known dispatching rules with automatically created composite dispatching rules produced by our system. It is shown that the proposed system is able to come up with highly e ective dispatching rules such that makespan reductions of up to 38% can be achieved, and in fact, often near optimal or even optimal schedules can be produced.

Keywords

• job shop scheduling
• optimization
• dispatching rules
• sim- ulation
• large-scale

-

The scheduling of jobs [ 2 ] is an important task in almost all production systems in order to optimize various objectives such as resource consumption, makespan (time to nish all products), tardiness (lateness of products), or ow time. Driven by the demands of the semiconductor industry, our general aim is the design of practically applicable algorithms for job shop scheduling problems for domains comprising thousands of machines and hundred thousands of job operations.

In real world domains like semiconductor manufacturing, common problem instances for a weekly workload are of the order of 104 operations on 102 machines in the back-end, i.e. where the products are made ready for shipping, and 105 operations on 103 machines in the front-end, i.e. where the chips are actually produced. To the best of our knowledge, the size of such large-scale job shop scheduling problem instances go beyond existing benchmarks. For example, the well-known benchmark targeting on makespan optimization from [ 11 ] comprises up to 50 jobs and 20 machines, which results in 1000 job operations in total. The famous Taillard benchmark [ 24 ] contains job shop instances of sizes up to 100 jobs on 20 machines which results in 2000 job operations. When focusing on tardiness optimization, somewhat bigger instances can be found. For example, the benchmark described in [ 29 ] comprises up to 20000 job operations. In this paper we introduce a benchmark comprising instances with up to 100000 operations to be scheduled on up to 1000 machines.

Many approaches have been used to solve scheduling problems. Aiming at optimal solutions, constraint based approaches (e.g. [ 1, 22 ]), branch and bound (e.g. [ 4 ]), branch and cut (e.g. [ 23 ]) or mixed integer programming (e.g. [ 18 ]) have a long and successful history. Another declarative solving approach that was tried with so far limited success is answer set programming [ 12, 13 ]. However, hybridized approaches between answer set- and constraint programming (see e.g. [ 27, 25 ]) show some potential for dealing even with large-scale scheduling instances [ 26, 8 ]. Calculating optimal schedules is typically far out of reach for large-scale domains. For near optimum solutions, current state of the art approaches are based on tabu and large neighborhood search (e.g. [ 28, 3, 10 ]), simulated annealing or genetic algorithms (e.g. [ 21 ]). Such local search methods have shown to be e ective whilst exhibiting low memory consumption. Though, for the successful application of local search methods on large-scale production environments the quality of the initial schedule that is iteratively optimized by some local search methodology is most important. Starting with, for example, a random schedule that is 200% o the optimum would not be su cient since it would take much too long to reach a near optimum schedule that is acceptable. Note that because of the highly dynamic production regimes and the often occurring changes (e.g. machine break down) in nowadays production environments rescheduling is needed every few minutes. Yet, if starting with a schedule of good quality, local search methods can be applied to squeeze out the still remaining potential of the production environment.

One widely employed state-of-the-art technique for dealing with large and complex scheduling problems in nowadays manufacturing environments is the application of dispatching rules (e.g. [ 15, 17, 19 ]). Dispatching rules are greedy heuristics for step-wise deciding which is the operation to be processed next by a machine. One big advantage of dispatching rules is that they can be computed typically in linear time. There are basically four ways for using dispatching rules: 1. Dispatching rules are directly applied by operator sta for steering the production process. As soon as a machine becomes idle, the operator decides which of the runnable operations in the dispatch list of the machine is to be loaded next. 2. Schedules are built by doing simulations based on di erent dispatching rules.

A schedule, which is found to be good enough, is then carried out. 3. An initial schedule of good quality is created by means of dispatching rules and iteratively optimized by local search methods. The optimized schedule is then carried out. 4. In a search framework dispatching rules can be used as search heuristics.

Hence, a deep understanding of dispatching rules is crucial for many di erent scheduling approaches and scenarios. Furthermore, the fully automatic generation of e ective dispatching rules is a highly important open question. In this paper we focus on the automatic creation of dispatching rules for the optimization of the makespan (i.e. minimization of time needed for accomplishing all operations) in very large job shops.

The job shop scheduling problem (JSP) is among the most famous N P-hard [ 14 ] combinatorial problems and can be de ned as follows: { Given is a set M = fmachine1; : : : ; machinemg of machines and a set J = fjob1; : : : ; jobj g of jobs. { Each job j 2 J consists of a sequence of operations Oj = fj1; : : : ; jlj g whereby jlj is the last operation of job j.

Practically, jobs can be interpreted as products and operations can be interpreted as their production steps. With respect to a job j and its operation ji, the operation ji+1 is called successor and the operation ji 1 is called predecessor. { Each operation o has an operation length lengtho 2 N. { Each operation o is assigned to a machine machineo 2 M by which it is processed. { A (consistent and complete) schedule consists of a starting time starto for each operation o such that:

An operation's successor starts after the operation has been nished, i.e. with respect to a job j and the operations ji and ji+1:

startji+1 startji + lengthji Operations processed by the same machine are non-overlapping, i.e. with respect to two operations o1 6= o2 with machineo1 = machineo2: starto1 6= starto2 starto1 < starto2 ! starto1 + lengtho1 starto2 { Makespan, i.e. the time period needed for processing all operations, is minimized. I.e.:

j2mJ;oa2xOjfstarto + lengthog ! min

The JSP is a special case of scheduling in manufacturing lines, in particular wafer fab scheduling in the semiconductor domain (see Figure 1). The exible JSP is a direct generalization of the JSP. In the exible JSP for an operation type there can be many machines. Yet, for the exible JSP it still holds that a machine can only perform one operation type. Allowing also that a machine can perform various operation types, as it is possible to change the setup of machines, leads to the exible JSP with sequence dependent setup times. Wafer fab scheduling introduces further concepts and constraints. For example, in wafer fabs it is common to have di erent types of machines. 'Single' machines only allow to perform one operation at a time. In ( exible) JSPs there are only 'single' machines. In wafer fabs there are also other types of machines, for example, batch machines that allow to perform a set of operations of the same type at the same time.

From the theoretical point of view, wafer fab scheduling is not more complex than the classic JSP. To see this, it is convenient to look at the decision problem versions of the optimization problems. The corresponding decision problems are about answering the question whether a solution below a certain makespan is existing. Having an oracle in N P to guess a solution it is obviously possible to check correctness of the solution in polynomial time. Thus, the corresponding decision problems are both in N P1. Consequently, coping with the complexity of the JSP is the key for coping with large-scale wafer fab scheduling.

In the following, we present a novel approach for fully automatic generation of composite dispatching rules. Composite dispatching rules are based on underlying basic dispatching rules, like for example 'shortest-job rst', and thus can be seen as hyper-heuristics [ 5 ]. The approach uses genetic algorithms, but in contrast to the approaches like [ 20 ] where genetic algorithms are used to directly nd good schedules, in our approach the genetic algorithm is used to nd a good dispatching rule, that in turn is used to produce the schedule. The proposed 1 We can easily de ne an optimization procedure on top of the decision problems that calculates the optimal makespan by applying binary search that has only logarithmic complexity. approach is conceptually similar to our previous work in [ 9 ], where we propose a genetic algorithm for learning hyper-heuristics for con guration problems.

After discussing the architecture of the proposed approach, we report on the design and the results of a large-scale job shop experiment in which we investigated the performance of our prototype system. The novel benchmark incorporates job shop problem instances that have proven optimal makespans and comprise up to 100000 operations to be scheduled on up to 1000 machines. Furthermore, they di er in the average number of operations per job, which has a big impact on the practical hardness of the problem instances. For all cases, we can show that the proposed approach outperforms any tested basic dispatching rule known from literature, and in fact, often (near-) optimal solutions can be found even for extremely large job shop problems. 2

Architecture

The event-based simulation engine implements a simulation model in which each machine possesses one queue. Initially, only the starting operations, i.e. those without predecessors, are enqueued. After nishing an operation on a machine, the successor operation is enqueued on its machine. As soon as a machine becomes idle and its queue is not empty the next operation to be run is selected among the operations in the queue. This selection is based on a priority value calculated by a (composite) dispatching rule.

Basic Dispatching Rules

Composite dispatching rules in our system basically constitute weighted combinations of 12 basic rules. These basic dispatching rules are: 1. shortest processing time (SPT): Prefer the operation with the shortest processing time. 2. longest processing time (LPT): Prefer the operation with the longest processing time. 3. shortest job rst (SJF): Prefer the operation of which the job possesses the shortest total processing time. 4. longest job rst (LJF): Prefer the operation of which the job possesses the longest total processing time. 5. least total work remaining (LTWR): Prefer the operation for which the sum of the operation length and successor operations' lengths is the least. 6. most total work remaining (MTWR): Prefer the operation for which the sum of the operation length and successor operations' lengths is the most. 7. relative least total work remaining (RLTWR): As LTWR but normalized by total job length. 8. relative most total work remaining (RMTWR): As MTWR but normalized by total job length. 9. shortest waiting time (SWT): Prefer the operation that was enqueued as the last. 10. longest waiting time (LWT): Prefer the operation that was enqueued as the rst. 11. urgency next (UN): Prefer the operation of which the successor operation's machine becomes idle as the rst (based on the current queues). 12. urgency any (UA): Prefer the operation of which one of the successor operation's machine becomes idle as the rst (based on the current queues).

SPT, LPT, SJF, LJF, LTWR, MTWR, SWT and LWT are well known (see, e.g. [ 16 ]). RLTWR and RMTWR are variants of LTWR and MTWR respectively. In RLTWR and RMTWR the total work remaining (TWR) is divided by the total job length. Hence, TWR is interpreted as the share of the remaining processing time of the operation's job relative to the total processing time of the job.

Also UN and UA are rule variants based on the well known WINQ rule [ 6, 7 ]. WINQ selects the operation of which the next successor operation will go on to the machine that has currently the least workload in the queue. The idea is to prevent idle times because of empty queues. UN follows the same idea but also takes into account the currently running operation of the successor's machine. Thus, with respect to some operation, UN calculates the nearest time point when the successor operation's machine can become idle.

UA is a generalization of UN calculating the earliest time point when one of the successor machines can become idle. I.e. whereas UN only considers the machine of the direct successor operation, UA takes all machines of the direct and indirect successor operations into account.

In order to purposefully combine the basic dispatching rules, every dispatching rule is implemented by a function that returns normalized priority values between 0 and 1. The semantic is: the higher the priority value the earlier an operation is processed by a machine. 2.3

Genetic Algorithm

For producing the di erent weight combinations the composite dispatching rules are based on, our system uses a genetic algorithm implemented with the Java Jenetics2 library. The algorithm operates on genomes consisting of only a single chromosome that is composed of 12 integer genes. Each gene represents the weight for a basic dispatching rule and, thus, each genome represents the set of weights for a composite dispatching rule. The tness value for a genome is determined by testing the resulting composite dispatching rule within the simulation engine with respect to some input problem instance. Hence, the simulation engine produces a schedule on the basis of the dispatching rule and the corresponding makespan represents the tness value. 3

Experimental Setup

The goal of the experiment is to show the e ectiveness of genetic algorithms in nding good composite dispatching rules for very large job shops. Hereby, we compare the composite dispatching rules generated by our system to each basic dispatching rule run on its own. 3.1

Algorithmic Con guration

The used genetic algorithm for producing the weights for the composite rules can be considered more or less standard. We use a 6-point crossover operator and a mutation rate of 10%. Genes (i.e. the weights) are restricted to integers between 0 and 10 (inclusive). The population size is set to 100 and the o spring fraction is 60%. For selecting genomes for recombination a tournament selector (tournament size = 10) is used. In the experiment we allowed a maximum of 100 generations. 3.2

Problem Instances

The problem instances used for the experiments described herein are on the one hand patterned on real world production scheduling problems, in particular in terms of size. On the other hand, the instances have known optimal makespans.

The creation process is as follows: First produce an optimal solution without (idle) holes for (1) a given number of job operations to be scheduled, (2) the 2 jenetics.io number of machines and (3) the desired optimal makespan. This is done by randomly partitioning the machines' time continuum into the prede ned number of partitions. Each partition corresponds to the processing period of one operation. Consequently, the optimal makespan, average operation length (avg(length)), number of operations (#ops) and number of machines (#machines) relate conforming to makespan = #ops avg(opLength) . Based on such a partitioning, suc#machines cessor relations are randomly generated. Each partition has maximally one successor and/or predecessor such that the successor's starting time is greater than the predecessors nishing time. Figure 3 shows the principle.

We applied two di erent procedures for generating random successor relations based on a pre-calculated solution:

The two di erent generating approaches result in benchmark instances that are di erent in nature: (1) produces many jobs consisting of a small number of operations. We refer to this set of instances as the 'short-jobs' benchmark instances. In contrary, (2) produces fewer jobs but with a larger number of operations per job. We refer to this set of instances as the 'long-jobs' benchmark instances. Table 1 and 2 show the statistics for the long-jobs benchmark instances. Table 3 and 4 show the statistics for the short-jobs benchmark instances. All instances have a minimal makespan of 600000. This roughly constitutes one week in seconds, which is a common planning horizon in semiconductor manufacturing.

RESULTS AND DISCUSSION

CONCLUSIONS

In this paper we present an approach based on event-based simulation and genetic algorithms for automatically generating composite dispatching rules for job shop scheduling problems. Hereby, we focus on very large job shops like found in semiconductor industry where exact methods are totally out of reach. We furthermmore report on an experiment investigating the e cacy of the proposed approach for makespan optimization of very large job shop problem instances. To this end, we describe a new benchmark incorporating problem instances with proven optima that comprise up to 100000 operations to be scheduled on up to 1000 machines. To the best of our knowledge, these instances are bigger than any benchmark instances found in literature so far. Summarizing, we can state that for many problem instances we could nd highly e ective composite dispatching rules resulting in near optimum schedules. #ma-#ops- le best basic generated reduction 100-10000-1 1040217 (MTWR) 853879 18% 100-10000-2 1033087 (MTWR) 754355 27% 100-10000-3 1073028 (RMTWR) 1000130 7% avg 1048777 869455 17% 1000-10000-1 600000 (LJF) 1000-10000-2 600000 (LJF) 1000-10000-3 893222 (UA) avg 697741 100-100000-1 1077736 (RMTWR) 1013399 100-100000-2 1040606 (UA) 1006303 100-100000-3 1072846 (RMTWR) 1013414 avg 1063729 1011039 600000 600000 600000 600000 0% 0% 33% 11% 6% 3% 6% 5%

References

1. Bartk , R. , Salido , M. , Rossi , F. : New trends in constraint satisfaction, planning, and scheduling: a survey . The Knowledge Engineering Review 25 ( 3 ), 249 { 279 ( 2010 ). https://doi.org/10.1017/S0269888910000202

2. Blazewicz , J. , Ecker , K. , Pesch , E. , Schmidt , G. , Weglarz , J.: Handbook on Scheduling: Models and Methods for Advanced Planning (International Handbooks on Information Systems) . Springer-Verlag New York, Inc., Secaucus, NJ, USA ( 2007 )

3. Boejko , W. , Gnatowski , A. , Pempera , J. , Wodecki , M.: Parallel tabu search for the cyclic job shop scheduling problem . Computers and Industrial Engineering 113 , 512 { 524 ( 2017 )

4. Brucker , P. , Jurisch , B. , Sievers , B. : A branch and bound algorithm for the job-shop scheduling problem . Discrete Applied Mathematics 49 ( 1 ), 107 { 127 ( 1994 )

5. Burke , E.K. , Gendreau , M. , Hyde , M. , Kendall , G. , Ochoa , G. , Ozcan, E., Qu , R.: Hyper-heuristics: a survey of the state of the art . J. of the Operational Research Society 64 ( 12 ), 1695 { 1724 ( 2013 )

6. Conway , R.W.: An experimental investigation of priority assignment in a job shop . RM-3789 -PR ( 1964 )

7. Conway , R.W.: Priority dispatching and work-in-process inventory in a job shop . Journal of Industrial Engineering 16 , 228{ 237 ( 1965 )

8. Da Col , G. , Teppan , E.C. : Declarative decomposition and dispatching for largescale job-shop scheduling . In: Joint German/Austrian Conference on Arti cial Intelligence (Kunstliche Intelligenz) . pp. 134 { 140 . Springer, Cham ( 2016 )

9. Da Col , G. , Teppan , E.C. : Learning constraint satisfaction heuristics for con guration problems . In: 19th International Con guration Workshop . pp. 8 { 11 ( 2017 )

10. Danna , E. , Perron , L. : Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs . In: Rossi, F . (ed.) Principles and Practice of Constraint Programming { CP 2003 . pp. 817 { 821 . Springer Berlin Heidelberg ( 2003 )

11. Demirkol , E. , Mehta , S. , Uzsoy , R.: Benchmarks for shop scheduling problems . European Journal of Operational Research 109 ( 1 ), 137 { 141 ( 1998 )

12. Falkner , A. , Friedrich , G. , Schekotihin , K. , Taupe , R. , Teppan , E.C. : Industrial applications of answer set programming . KI-Kunstliche Intelligenz pp. 1 { 12 ( 2018 )

13. Friedrich , G. , Fruhstuck, M. , Mersheeva , V. , Ryabokon , A. , Sander , M. , Starzacher , A. , Teppan , E.: Representing production scheduling with constraint answer set programming . In: Operations Research Proceedings 2014 , pp. 159 { 165 . Springer, Cham ( 2016 )

14. Garey , M.R. , Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness . W. H. Freeman & Co., New York, NY, USA ( 1990 )

15. Hildebrandt , T. , Goswami , D. , Freitag , M. : Large-scale simulation-based optimization of semiconductor dispatching rules . In: Proceedings of the 2014 Winter Simulation Conference . pp. 2580 { 2590 . WSC '14, IEEE Press, Piscataway, NJ, USA ( 2014 )

16. K. Kaban , A. , Othman , Z. , Rohmah , D. : Comparison of dispatching rules in jobshop scheduling problems using simulation: A case study . Int. J. of Simulation Modelling 11 , 129 { 140 (09 2012 )

17. Kaban , A.K. , Othman , Z. , Rohmah , D.S. : Comparison of dispatching rules in jobshop scheduling problem using simulation: a case study . Int. Journal of Simulation Modelling 11 ( 3 ), 129 { 140 ( 2012 )

18. Ku , W.Y., Beck , J.C. : Mixed integer programming models for job shop scheduling: A computational analysis . Computers and Operations Research 73 , 165 { 173 ( 2016 )

19. Panwalkar , S.S. , Iskander , W.: A survey of scheduling rules . Oper. Res . 25 ( 1 ), 45 {61 (Feb 1977 )

20. Pezzella , F. , Morganti , G. , Ciaschetti , G.: A genetic algorithm for the exible jobshop scheduling problem . Computers and Operations Research 35 ( 10 ), 3202 { 3212 ( 2008 )

21. Sadegheih , A. : Scheduling problem using genetic algorithm, simulated annealing and the e ects of parameter values on ga performance . Applied Mathematical Modelling 30 ( 2 ), 147 { 154 ( 2006 )

22. Sadeh , N.M. , Fox , M.S. : Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem . Arti cial Intelligence 86 , 1 { 41 ( 1996 )

23. Stecco , G. , Cordeau , J.F. , Moretti , E.: A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times . Comput. Oper. Res . 35 ( 8 ), 2635 { 2655 ( 2008 )

24. Taillard , E.: Benchmarks for basic scheduling problems . European Journal of Operational Research 64 ( 2 ), 278 { 285 ( 1993 ), project Management anf Scheduling

25. Teppan , E.C. : Solving the partner units con guration problem with heuristic constraint answer set programming . In: Con guration Workshop . pp. 61 { 68 ( 2016 )

26. Teppan , E.C. , Friedrich , G.: Heuristic constraint answer set programming for manufacturing problems . In: Advances in Hybridization of Intelligent Methods , pp. 119 { 147 . Springer ( 2018 )

27. Teppan , E.C. , Friedrich , G.: Heuristic constraint answer set programming . In: ECAI . pp. 1692 { 1693 ( 2016 )

28. Watson , J.P. , Beck , J.C. , Howe , A.E. , Whitley , L.D.: Problem di culty for tabu search in job-shop scheduling . Artif. Intell . 143 ( 2 ), 189 {217 (Feb 2003 )

29. Zhang , R. , Wu , C. : A hybrid approach to large-scale job shop scheduling . Applied Intelligence 32 ( 1 ), 47 {59 (Feb 2010 )