Abstract
The job shop scheduling problem (JSSP) is generally defined as decision-making problems with the aim of optimizing one or more scheduling criteria. Many different approaches, such as simulated annealing (Wu et al., 2005), tabu search (Pezzella & Merelli, 2000), genetic algorithm (Watanabe, Ida, & Gen, 2005), ant colony optimization (Huang & Liao, 2007), neural networks (Wang, Qiao, &Wang, 2001), evolutionary algorithm (Tanev, Uozumi, & Morotome, 2004) and other heuristic approach (Chen & Luh, 2003; Huang & Yin, 2004; Jansen, Mastrolilli, & Solis-Oba, 2005; Tarantilis & Kiranoudis, 2002), have been successfully applied to JSSP. Flexible job shop scheduling problem (FJSSP) is an extension of the classical JSSP which allows an operation to be processed by any machine from a given set. It is more complex than JSSP because of the addition need to determine the assignment of operations to machines. Bruker and Schlie (1990) were among the first to address this problem.
TopIntroduction
The job shop scheduling problem (JSSP) is generally defined as decision-making problems with the aim of optimizing one or more scheduling criteria. Many different approaches, such as simulated annealing (Wu et al., 2005), tabu search (Pezzella & Merelli, 2000), genetic algorithm (Watanabe, Ida, & Gen, 2005), ant colony optimization (Huang & Liao, 2007), neural networks (Wang, Qiao, &Wang, 2001), evolutionary algorithm (Tanev, Uozumi, & Morotome, 2004) and other heuristic approach (Chen & Luh, 2003; Huang & Yin, 2004; Jansen, Mastrolilli, & Solis-Oba, 2005; Tarantilis & Kiranoudis, 2002), have been successfully applied to JSSP.
Flexible job shop scheduling problem (FJSSP) is an extension of the classical JSSP which allows an operation to be processed by any machine from a given set. It is more complex than JSSP because of the addition need to determine the assignment of operations to machines. Bruker and Schlie (1990) were among the first to address this problem. The flexible job shop scheduling problem may be formulated as follows.
- 1.
There is a set of n jobs that plan to process on m machines;
- 2.
The set machine is noted M, M = {M1, M2, ..., Mm};
- 3.
Each job j consists of a sequence of nj operations Oj1, Oj2, ..., Ojnj;
- 4.
The execution of each operation i of a job j (noted Oji) requires one machine out of a set of given machines called Mji ⊆ M.
The problem is thus to both determine an assignment and a sequence of the operations on all machines that minimize following criteria.
- 1.
Maximal completion time of machines;
- 2.
Total workload of the machines;
- 3.
Critical machine workload.
The weighted sum of the above three objective values is taken as the objective function.
F(c) = 0.5*F
1(c) + 0.2*F
2(c) + 0.3*F
3(c)
(1)Where F(c) denotes the total evaluation value of the schedule c; F1(c) denotes the maximal completion time of machines (makespan) of the schedule c; F2(c) denotes the total workload of the machines of the schedule c; F3(c)denotes the critical machine workload of the schedule c.
TopBackground
For solving the realistic case with more than two jobs, two types of approaches have been used: hierarchical approaches and integrated approaches (Xia & Wu, 2005).
In hierarchical approaches, assignment of operations to machines and the sequencing of operations on the machines are treated separately. Kacem, Hammadi, and Borne (2002a; 2002b) proposed a genetic algorithm controlled by the assigned model for the FJSSP. Xia and Wu (2005) present an effective hybrid optimization approach, which makes use of particle swarm optimization to assign operations on machines and simulated annealing algorithm to schedule operations, for the multi-objective FJSSP.
Integrated approaches were used by considering assignment and scheduling at the same time. The integrated approach which had been presented by Dauzere-Peres and Paulli (1997) was defined a neighborhood structure for the FJSSP where there is no distinction between reassigning and resequencing an operation, and the tabu search procedure is proposed based on the neighborhood structure. Mastrolilli and Gambardella (2002) improved Dauzere-Peres’ tabu search techniques and presented two neighborhood functions. Most researchers were interested in applying tabu search techniques and genetic algorithms to FJSSP in the past (Xia & Wu, 2005).
Key Terms in this Chapter
Multi-Objective Optimization: In the world around us it is rare for any problem to concern only a single value or objective. Generally, multiple objectives or parameters have to be met or optimized before any ‘master’ or ‘holistic’ solution is considered adequate. Most realistic optimization problems, particularly those in design, require the simultaneous optimization of more than one objective function.
Flexible Job Shop Scheduling Problem: It is an extension of the classical job shop scheduling problem which allows an operation to be processed by any machine from a given set. The problem is to assign each operation to a machine and to order the operations on the machines, such that the maximal completion time (makespan) of all operations is minimized.
Ant Colony Optimization: ACO studies artificial systems that take inspiration from the behavior of real ant colonies and which are used to solve discrete optimization problems. ACO is a population-based approach to the solution of combinatorial optimization problems. The basic ACO idea is that a large number of simple artificial agents are able to build good solutions to hard combinatorial optimization problems via low-level based communications.
Job Shop Scheduling Problem: An instance of the job-shop scheduling problem consists of a set of n jobs and m machines. Each job consists of a sequence of n activities so there are nm activities in total. Each activity has a duration and requires a single machine for its entire duration. The activities within a single job all require a different machine. An activity must be scheduled before every activity following it in its job. Two activities cannot be scheduled at the same time if they both require the same machine. The objective is to find a schedule that minimizes the overall completion time of all the activities.
Operation Assignment Machine Knowledge (OAMK): It is the accumulative knowledge of assigning the giving operation to a more appropriate machine. It was achieved from the near-optimal solution of FJSSP of each iterative.
Operation Assignment Position Knowledge (OAPK): It is the accumulative knowledge of the more appropriate operation processing sequence at a giving machine. It is achieved from the near-optimal solution of FJSSP of each iterative.
Combinatorial Optimization Problems: One can argue that combinatorial optimization and Integer programming are synonymous terms. This is because the majority (if not all) of the combinatorial optimization problems are integer programming problems, usually involving binary variables.