Scheduling in Flexible Manufacturing Systems: Genetic Algorithms Approach

Introduction

Flexible manufacturing systems are characterized by multipurpose operations and flexible job routing. A multipurpose operation can be processed at least by one machine, with possibility of variable performances. In ordinary systems, the route of every job is fixed and every operation of a job is allocated to a unique machine. In flexible manufacturing, an operation can be allocated to a suitable machine from a set of alternatives which are identical or similar in functionalities. One can distinguish two types of flexible manufacturing systems: totally flexibility where every operation can be processed by every machine and partially flexible systems where a pool of machines is associated to each operation (Figure 1).

A fabrication order can evolve in the system through different paths. It can visit the same machine more than once. The flexibility has demonstrated its efficiency for system performance by reducing latencies and work in progress. Flexible machines allow rapid adaptation to changs and re-routing flexibility in presence of breakdowns or bottlenecks. Flexible manufacturing systems have a high development cost since flexible machines are more expensive than the mono-purpose ones. The scheduling functionality is a central key of profitability in flexible manufacturing systems. The allocation in space (machines) and in time of parts processing have to be optimized to take advantage from machine flexibility.

Figure 1.

Flexible manufacturing systems

The use of flexible machines defines a generalization of the scheduling problem known as the flexible job shop problem (FJSP). This problem has attracted many researches. Due to the combinatorial number of possible schedules and the strongly NP-hard nature of FJSP (Garey et al., 1976), exact methods that can guarantee solution optimality will not return results in a reasonable amount of time. Indeed, a significant attention has been paid in the literature to techniques of achieving efficient approximation algorithms which offer a good compromise between computation time and solutions qualities including genetic algorithms, tabu search, simulated annealing among other heuristics and metaheuristics.

Actually, much research literature addressed the genetic algorithm approach to solve the FJSP because of their ability to perform global search and provide good solutions in a short computation time. Otherwise, crossover and mutation operators in a genetic process can easily combine affectation schemes and adopt different sequencing strategies to conduct an effective parallel and sampled search to intelligently locate promising area in the solution space. The objective of this chapter is to present how the genetic resolution scheme was adapted to solve the flexible job shop problems. The solution encoding and the genetic operators, crossover and mutation, are described and illustrated with examples.

Flexible Job Shop Scheduling

The FJSP can be described as follows. There are n independent jobs (no precedence constraints among operations of different jobs) J = {1, …, j, …, n}, each job j is composed of a predefined sequence of n_j operations O_ij, where O_ij denotes the i^th operation of the job j. The order of operations of each job is predefined and cannot be modified. A set of K machines M = {M_k, 1 ≤ k ≤ m} is available. At any time, each machine can process at most one operation. One job can visit at least one machine at a time. An operation can be allocated to a machine from a set of alternatives with variables performances to be processed without interruption. Hence, to each operation O_ij is associated a pool of machines m_ij. Given a machine m_k from m_ij than the execution time of O_ij on m_k is e_ijk. A scheduling is a definition for each operation of a machine m_k from its pool, a starting date s_ij and a completion time c_ij of O_ij on that machine. The objective on the FJSP is to both determine an assignment and a sequence of the operations on the machines so that some criteria have to be optimized. The widely used criterion in the literature is the maximum completion time (makespan) to be minimized.

The following notations are used: