Scheduling in Flexible Manufacturing Systems: Genetic Algorithms Approach

Scheduling in Flexible Manufacturing Systems: Genetic Algorithms Approach

Fraj Naifar (Digital Research Center of Sfax, Tunisia), Mariem Gzara (University of Monastir, Tunisia) and Taicir Loukil Moalla (Tabuk University, Saudi Arabia)
DOI: 10.4018/978-1-5225-2944-6.ch001
OnDemand PDF Download:
List Price: $37.50


Flexible manufacturing systems have many advantages like adaptation to changes and reduction of lateness. But flexible machines are expensive. The scheduling is a central functionality in manufacturing systems. Optimizing the job routing through the system, while taking advantage from the flexibility of the machines, aims at improving the system's profitability. The introduction of the flexibility defines a variant of the scheduling problems known as flexible job shop scheduling. This variant is more difficult than the classical job shop since two sub-problems are to be solved the assignment and the routing. To guarantee the generation of efficient schedules in reasonable computation time, the metaheuristic approach is largely explored. Particularly, much research has addressed the resolution of the flexible job shop problem by genetic algorithms. This chapter presents the different adaptations of the genetic scheme to the flexible job shop problem. The solution encodings and the genetic operators are presented and illustrated by examples.
Chapter Preview


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 nj operations Oij, where Oij denotes the ith operation of the job j. The order of operations of each job is predefined and cannot be modified. A set of K machines M = {Mk, 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 Oij is associated a pool of machines mij. Given a machine mk from mij than the execution time of Oij on mk is eijk. A scheduling is a definition for each operation of a machine mk from its pool, a starting date sij and a completion time cij of Oij 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:

Key Terms in this Chapter

Metaheuristic: A top-level general strategy which can be adapted to search for feasible solutions in domains where the task is hard.

Job Shop Scheduling: The basic form of the problem of scheduling jobs with multiple (M) operations, over M machines, such that all of the first operations must be done on the first machine, all of the second operations on the second, etc.

Gantt Chart: The Gantt-Chart is a convenient way of visually representing a solution of the scheduling problem.

Flexible Machine: A machine that can execute different types of operations.

Genetic Algorithm: A genetic algorithm is a metaheuristic inspired by the process of natural selection to solve optimization problems.

Scheduling: Scheduling is the process of arranging, controlling and optimizing work and workloads in a production process or manufacturing process.

Complete Chapter List

Search this Book: