Optimal Scheduling by Genetic Algorithms

Abstract:

Scheduling problems are among the most difficult combinatorial optimization problems, where classic approaches based on exhaustive enumeration had only limited success. This research involves establishing an ultimate framework for scheduling using Genetic Algorithms (GAs).

  

Figure 1: A 6$\times$ 6 jobshop scheduling problem

Optimal scheduling by GAs

We first proposed a binary-coding GA and then GT-GA with more straightforward encoding using active schedules[1]. Subsequently, Multi-Step Crossover Fusion (MSXF) was proposed as a new crossover operator that has a built-in local search mechanism, and successfully applied to jobshop and flowshop scheduling problems[2,3,5,4].

MSXF is defined in a problem-independent manner using a neighborhood structure and a distance measure, both of which are very common for most problems. Let the parent solutions be p₁ and p₂, and let the distance between any two individuals xand y be d(x,y). A short term local search is carried out starting from p₁ and using p₂ as a reference point as follows. First x is set to p₁. All members in N(x) are sorted in ascending order of d(y, p₂) so that $y{\in}N(x)$ with a higher rank has a smaller distance d(y,p₂). One of the members $y{\in}N(x)$ is selected with a probability proportional to the rank. Then y is probabilistically accepted according to the Metropolis criterion (Figure 2).

  

Figure 2: Multi-step crossover fusion

In contrast with the stochastic local search and conventional GA crossover, MSXF carries out a short term navigated local search starting from one of the parents, while the other is regarded as a reference point to which the search direction is navigated (Figure 3). Stochastic local search is a fine-grained search around p₁, whereas MSXF performs more coarse-grained search but in more wider area between p₁ and p₂ (Figure 4).

  

Figure 3: Conventional crossover and MSXF

  

Figure 4: Stochastic local search and MSXF

We found that the landscape of some scheduling problems exhibits so-called big valley structure (Figure 5) under which MSXF-GA is shown to work well[3].

  

Figure 5: Big valley structure of problem landscape

CAST

Recently our optimal scheduling techniques have been applied to NTT's scheduling tasks, which contributed to the development of the CAST (Communicator Allocation SupporT) system developed by NTT Communication Ware Corporation (Figure 6)[6]. Starting from Spring 1998, the CAST system will be introduced nationwide to 100 NTT branches.

  

Figure 6: A near optimal allocation

Future research

Future research will be to extend our methods to other types of scheduling problems and analyze the landscape of the problem search space to seek for a more powerful method.

Contact: Takeshi Yamada, Email: yamada@cslab.kecl.ntt.co.jp

Bibliography

1

Yamada, T. and Nakano, R.: Chapter 7: Job Shop Scheduling, in A.M.S. Zalzala and P.J.Fleming (Ed.) Genetic Algorithms in Engineering Systems,
The Institution of Electrical Engineers, London, UK, 1997.

2

Yamada,T. and Nakano, R.: Scheduling by Genetic Local Search with Multi-Step Crossover, Proc. of Int. Conf. on Parallel Problem Solving from Nature (PPSN'96), pp. 960-969 (1996).

3

Yamada, T. and Reeves, C.R.: Permutation flowshop scheduling by genetic local search, Proc. of the 2nd IEE/IEEE Int. Conf. on Genetic ALgorithms in Engineering Systems (GALESIA '97), pp. 232-238, 1997.

4

Reeves, C.R. and Yamada, T. : Genetic Algorithms, Path Relinking and the Flowshop Sequencing Problem, Evolutionary Computation, MIT press, (to appear).

5

Yamada, T. and Reeves, C.R.: Solving the Csum Permutation Flowshop Scheduling Problem by Genetic Local Search, Proc. of 1998 IEEE Int. Conf. on Evolutionary Computation (ICEC'98), pp. 230-234, 1998.

6

Yoshimura, K. and Nakano, R.: Genetic Algorithm for Information Operator Scheduling, Ibid., pp. 277-282, 1998.

Nakano Group NTT CS labs.