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.
Published in Chapter:
Simulation Model of Ant Colony Optimization for the FJSSP
Li-Ning Xing (National University of Defense Technology, China), Ying-Wu Chen (National University of Defense Technology, China), and Ke-Wei Yang (National University of Defense Technology, China)
Copyright: © 2009
|Pages: 7
DOI: 10.4018/978-1-60566-026-4.ch551
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.