Introduction

The scope and the purpose of this paper are to present a survey of job shop scheduling problems (JSSs) using artificial intelligence (AI) solution techniques which covers the AI strategies for different objective function of job shop scheduling problem. Numerous approaches have been investigated and classifications of these techniques are given.

The remainder of the study is as follows: JSS problem is defined in detail in section “Job shop scheduling problem”, history and structure of AI mentioned in section “Brief history of AI”. In section “AI strategies for job shop problem” provides a detailed classification according to the survey. In section “Analysis and discussions”, some conclusions and future research road maps are given. Selected time period is between 1997 and 2012. Articles are selected mainly from Science Direct and EBSCO data bases.

Job shop scheduling problem

Job shop scheduling problem (JSS) consists of a finite jobs set, J\(_{i }(\)i = 1,2,...,n) to be processed on a finite machine set M\(_{k }(\)k = 1,2,...,m) (Geyik and Cedimoglu 2004). According to its production routine, each job is processed on machines with a given processing time, and each machine can process only one operation for each job (Chen et al. 2012). JSS can be thought of as the allocation of resources over a specified time to perform a predetermined collection of tasks (Surekha and Sumathi 2011). In other words, the production scheduling problem allocates limited resources to tasks over time and determines the sequence of operations so that the constraints of the system are met and the performance criteria are optimized (Akyol and Bayhan 2007).

The job shop scheduling problem is one of the most important and complicated problems which has been known as an NP-hard and very challenging combinatorial optimization problem since 1950s (Lenstra et al. 1977; Zhang et al. 2013) in machine scheduling. The high complexity of the problem makes it hard to find the optimal solution within reasonable time in most cases (Asadzadeh and Zamanifar 2010).

JSS can be applied to the manufacturing processes and affects really the production time and the cost of production for a plant (Lin et al. 2010). Solving JSS enables a manufacturer’s ability to be more competitive. Therefore, AI techniques are developed to solve JSS problem.

Brief history of AI

The field of artificial intelligence (AI) research was founded at a conference on the campus of Dartmouth College in the summer of 1956 (Crevier 1993) and AI is the generic name given to the field of computer science dedicated to the development of programs that attempt to replicate human intelligence (Fonseca and Navaresse 2002). If too many tasks are allocated to the system, the human does not have opportunities to build up a mental model of the system. As a result, exceptions which the system is not able to handle cannot be solved by the human either (Wiers 1997). So AI can be described as “the study and design of intelligent agents” (Russell and Norvig 2003).

By the use of AI techniques, researchers were able to develop clever methods to solve NP hard problems such as JSS. Solution quality obtained by AI techniques is much better than Branch-and-Bound based heuristic solutions for JSS and solution time is much shorter.

Some early milestones include work in problems solving which included basic work in learning, knowledge representation, and inference as well as demonstration programs in language understanding, translation, theorem proving, associative memory, and knowledge-based systems (Buchanan 2005).

The artificial intelligence (AI) research community has been very active in the area of planning and scheduling since the 1960s (Spyropoulos 2000) and early history of AI is summarized by Russell and Norvig (2003) as; (1) McCulloch and Pitts: Boolean circuit model of brain (1943). (2) Turing’s “Computing Machinery and Intelligence” (1950). (3) Look, Ma, no hands! (1952–1969). (4) Early AI programs, including Samuel’s checkers program, Newell and Simon’s Logic Theorist, Gelernter’s Geometry Engine (1950s). (5)Dartmouth meeting: “Artificial Intelligence” adopted (1956). (6) Robinson’s complete algorithm for logical reasoning (1965). (7) AI discovers computational complexity. Neural network research almost disappears (1966–1974). (8) Early development of knowledge-based systems (1969–1979). (9) Expert systems industry booms (1980–1988). (10) Expert systems industry busts: “AI Winter” (1988–1993). (11) Neural networks return to popularity (1985–1995). (12) Resurgence of probabilistic and decision-theoretic method Rapid increase in technical depth of mainstream AI “Nouvelle AI”: ALife, GAs, soft computing (1988).

After this time period, Meta heuristic techniques are used to find near optimal solution for scheduling problems.

AI strategies for job shop problem

In this survey, recent studies on job shop scheduling problems are summarized based on problem objective function and used AI techniques to solve JSS. Table 1 list the well-known objective functions of JSS.

Table 1 Well known objective functions (Ross and Corne 2005)
Full size table

Genetic algorithm (GA)

The term of genetic algorithm was first used by Holland (1975) and take place in literature universally, early studies and applications of GA are displayed in some books such as those by Davis (1991) and Chambers (2001). Work on genetic algorithms (GA) for solving the JSS including the FSP has a history of almost four decades (Davis 1985; Liepins and Hilliard 1987; Cleveland and Smith 1989) and (Nakano and Yamada 1991). Recent studies of GA on Job shop scheduling problem are listed in Table 2.

Table 2 Genetic algorithm
Full size table

Beam search (BS)

Beam search is a heuristic method which explores a graph by expanding the most promising node in a limited set. This search technique was primarily used in artificial intelligence for the speech recognition problem (Lowerre 1976). Ow and Morton (1988) and Scheduling (1995) provide detail explanation of Beam Search method. One application of beam search is solving JSS problem is given in Table 3.

Table 3 Beam search
Full size table

Tabu search (TS)

Tabu search is a heuristic method which is originally proposed by Glover (1986). Tabu Search is a neighborhood search method which employs “intelligent” search and flexible memory technique to avoid being trapped at local optimum. Tabu search enhances the performance of these techniques by using memory structures that describe the visited solutions or user-provided sets of rules (Glover 1989). Recent studies of TS are listed in Table 4.

Table 4 Tabu search
Full size table

Agent based systems (ABS)

An intelligent agent receives messages from the environment via its perception mechanism. These messages are then evaluated by the cognition system and appropriate actions are produced and implemented by the action module (Aydın and Oztemel 2000). The word “agent” is first used in John H. Miller’s 1991 paper “Artificial Adaptive Agents in Economic Theory” (Holland and Miller 1991) which is based on an earlier conference presentation of the same authors. Recent studies of ABS are listed in Table 5.

Table 5 Agent based systems
Full size table

Ant colony optimization (ACO)

The work of Goss, Aron, Deneubourg and Pasteels on the collective behavior of Argentine ants, provided the idea of Ant colony optimization algorithms (Goss et al. 1989). First ACO proposed by Dorigo (1992) in his PhD thesis to search for an optimal path in a graph depends on the behavior of ants seeking a path between their colony and source food (Colorni et al. 1991; Dorigo 1992). Recent studies of ACO on JSS are listed in Table  6.

Table 6 Ant colony algorithm
Full size table

Neural network (NN), artificial neural network (ANN)

Artificial neural systems or neural networks are physically cellular systems which can acquire, store and utilize experimental knowledge (Zurada 1992) artificial neural networks (ANNs) have been successfully applied to solve a variety of problems (Sabuncuoglu and Gurgun 1996). For detail information about application of neural network refer to the Zhang and Huang (1995). Recent studies of NN on JSS are listed in Table 7.

Table 7 Neural network
Full size table

Particle swarm algorithm (PSO)

Particle swarm optimization (PSO) is developed by Kennedy and Eberhart (Kennedy and Eberhart 1995). The position of one particle corresponds to a solution of the problem. Like a bird that fies to the food, in PSO, one particle moves its position to a better solution according to the best particle’s experience and its own experience (Lin et al. 2010). Recent studies of PSO method on job shop scheduling problem are listed in Table 8.

Table 8 Particle swarm algorithm
Full size table

Variable neighborhood search (VNS)

Variable neighborhood search (VNS) proposed by Mladenovi’c and Hansen in (1997) as a metaheuristic method for solving combinatorial optimization, and global optimization problems. For detail information about method and applications refer to Hansen et al. (2008). Recent studies of VNS method on JSS problem are listed in Table 9.

Table 9 Variable neighborhood search
Full size table

Fuzzy logic (FL)

The concept of fuzzy logic (FL) was conceived by Lotfi A. Zadeh, introduced the paper on fuzzy sets (Yen and Langari 1999) and presented not as a control methodology but a way of processing data by allowing partial set membership rather than crisp set membership or non-membership. Fuzzy logic is an analysis method purposefully developed to incorporate uncertainty into a decision model (Zadeh 1965). Fuzzy logic allows for including imperfect information no matter the cause. Recent studies of FL method on Job shop scheduling problem are listed in Table 10.

Table 10 Fuzzy logic
Full size table

Bee colony optimization (BCO)

The bees algorithm is a population-based search algorithm and first study is done by Pham et al. (2005) which performs with random search and a kind of neighbor search method to solve combinatorial optimization problems. Karaboga (2005) studied a new optimization algorithm based on the intelligent behavior of honey bee swarm. From the simulation results, it is concluded that the proposed algorithm can be used for solving unimodal and multi-modal numerical optimization problems. Recent studies of BCO on JSS are listed in Table 11.

Table 11 Bee colony optimization (BCO)
Full size table

Analysis and discussions

Scheduling is one of the most critical issues for manufacturing systems. Due to its NP-hard nature, developing an optimal schedule is very costly and impractical. Therefore many different heuristics are developed for this problem. Among the heuristic approaches, AI techniques provide very good schedules. In this survey, solving AI techniques of different objective function of Job Shop Scheduling problems are summarized covering the last 15 years to put on a road map.

Although there are hundreds of articles related to scheduling, we limit the coverage of this survey to only AI approaches to JSS and used the key words: Genetic Algorithm, Beam Search, Tabu Search, Agent Based Systems, Ant Colony Algorithm, Neural Network, Particle Swarm Algorithm, Variable Neighborhood Search, Fuzzy Logic, and Bee Colony Optimization combined with Job Shop Scheduling. These key words resulted in a couple of hundred articles and we further select 62 of them to complete the survey.

The search for articles resulted in a large number of articles that uses branch and bound methods in their algorithms. Even though some of them are state-of-the-art algorithms, they are not included in this survey because branch-and-bound is not an AI technique. On the other hand, there exist a few articles that use branch-and-bound method in the context of Beam Search.

Findings from the survey are:

  1. 1.

    After 2000s, while Neural Network techniques are used shown a decrease in literature. Genetic Algorithm, Agent Based Systems and Ant Colony optimization have shown an increase as can be seen in Fig. 1.

  2. 2.

    Most of researchers are focused on minimization of makespan problem and second tier problem is Multi objective problems. Percentage of objective functions of each article is shown in Fig. 2.

  3. 3.

    Most of researchers are focused on Algorithm development. A few articles focus on solving real life industrial problem. Percentage of article types is as seen in Fig. 3.

  4. 4.

    None of research shows that which technique is superior to others for this problem.

  5. 5.

    In specific parts, some models are superior to others like;

    1. a.

      Wu et al. (1991, 1993) compared the performance of genetic algorithms and local search heuristics to generate robust schedules. The results showed the performance of genetic algorithms in generating schedules with much better makespan and stability than local search heuristics.

    2. b.

      Bierwirth and Mattfeld (1999) reported in their experimental results that the capabilities of genetic algorithms vanish with an increasing problem size, and they are not efficient to find a near-optimal solution in a reasonable time.

    3. c.

      Cheung and Zhou (2001) compared the performance of a hybrid genetic algorithm, based on a genetic algorithm and heuristic rules, for the problem of \(\hbox {J}_\mathrm{m}|\hbox {S}_\mathrm{ij}|\hbox {C}_\mathrm{max}\) (m machine JSS problem with respect to sequence dependent setup times in order to minimize makespan). They showed by computational analysis that their hybrid algorithm is superior to earlier methods proposed for the same problem.

    4. d.

      Xing et al. (2010) compared the performance of KBACO (Knowledge based ant colony opt.) for optimal makespan outperforms these eight published algorithms; 1. Temporal Decomposition, 2. Controlled Genetic Algorithm (CGA), 3. Approach by Localization (AL) 4. AL+CGA, 5. PSO+SA, 6. Tabu Search, 7. GENACE.

    5. e.

      Yazdani et al. (2010) compared the performance of solving FJSP to minimize makespan. The results demonstrated that variable neighborhood search algorithm is better than other algorithms in the past research.

    6. f.

      Zhang (2011) compared the performance of an artificial bee colony algorithm based on criticality information for solving job shop scheduling problems. ABC obtains better result than PSO for nine instances.

    7. g.

      Lei (2012b) compared the performance of solving minimizing makespan for scheduling stochastic job shop with random breakdown. Proposed GA is tested on 22 benchmark problems and is compared with simulated annealing (Kirkpatrick et al. 1983) and similar particle swarm optimization algorithm (Lian et al. 2006). The comparative results show the promising advantage of GA on stochastic scheduling.

    8. h.

      Lei (2012a) compared the performance of co-evolutionary genetic algorithms which has better performance than decomposition integration genetic algorithm (DIGA), PEGA and particle swarm optimization and simulated annealing (PSO+SA).

Fig. 1
figure 1

percentages of AI strategy studies (1997-2012).

Full size image
Fig. 2
figure 2

percentages of objective function (1997-2012).

Full size image
Fig. 3
figure 3

percentages of article types (1997-2012).

Full size image

Conclusions

Job shop scheduling problems are difficult problems to be solved due to their NP-Hard nature. Researchers and practitioners try to develop efficient solutions for these problems during the last couple of decades. With the recent advancement in computing techniques, artificial intelligence techniques becomes a powerful solution approaches to many combinatorial optimization problems including JSS.

In this survey, a range of AI based solution methods are surveyed. Since these methods are not optimization methods, none of the AI techniques guarantees the optimal solution. However, based on solution approaches as mentioned in section “Analysis and discussions”, the efficiency of AI techniques to some problems is identified.

Surveyed articles show that most of the works are focused on testing the develop algorithm on benchmark or generated problems.