Article Preview
TopIntroduction
Scheduling is one of the most important issues in the design of production system (Pinedo & Chao, 1999); it has gained much attention in the recent years (Pinedo, 2012). The principle aim of scheduling is to plan the sequence of work so that production can be systematically arranged towards the end of completion of all products by due date. The proper scheduling of machines in an industry can reduce the production hours that contributes to produce goods much faster (Harjunkoski et al., 2014).
Scheduling problems in their static and deterministic forms are simple to describe and formulate, but are difficult to solve as it involves complex combinatorial optimization. For example, if there are m machines, each of which is required to perform n independent operations. The combination can be potentially exploded up to (n!)m operational sequences. The Job shop scheduling problem (JSSP) is an important concern in the manufacturing systems. It has been known as one of the worst combinatorial optimisation problems ever since the 1950s in production scheduling categorized into Non-deterministic Polynomial-time hard (NP-hard) (Graham, 1966; Lenstra et al., 1977; Wang et al., 2008; Asadzadeh & Zamanifar, 2010). This means that due to the combinatorial explosion, even a computer can take unacceptably large amount of time to seek a satisfied solution on even moderately large scheduling problem. Another potential issue of complexity is the assembly relationship. Job shop scheduling problem is comprised of a set of independent jobs or tasks (J), each of which consists of a sequence of operations (O). Each operation is performed on machine (M) without interruption during processing time. The main purpose of JSSP is usually to find the best machine schedule for tuning all jobs in order to optimize either single criterion or multiple scheduling objectives (measures of performance) such as the minimization of the makespan (Cmax) or the penalty costs of tardiness and/or earliness.
In manufacturing environments, the scheduling problems are very complex and cannot usually be solved in reasonable time using the conventional optimization techniques. The JSSP involves the optimization of many manufacturing parameters, such as minimizing the total tardiness time (Lei & Guo, 2011; Tasgetiren et al., 2011), the makespan (Seo & Kim, 2010; Noorul Haq et al., 2010; Yang & Yang, 2010; Low et al., 2010; Wang & Wang, 2012), the machine idle time (Khorshidian et al., 2011), and the average completion time (Sitters, 2010) etc. of these parameters, the makespan is commonly used. Numerous studies have addressed the problem of minimizing the job makespan (Rajendran & Ziegler, 2004; Allahverdi & Aydilek, 2010; Zhang et al., 2011; Mokhtari et al., 2011; Ben Chihaoui et al., 2011).
Various optimization approaches have been widely applied to solve the JSSP. Conventional methods based on mathematical model and/or full numerical search (for example, Branch and Bound and Lagrangian Relaxation) can guarantee the optimum solution. They have been successfully used to solve JSSP. However, these methods may highly consume computational time and resources even for solving a moderate-large size problem and therefore are impractical if the computational limitation is existing. Due to the complexity involved in JSSP, recent research has focused on metaheuristic approaches, such as genetic algorithms (GAs) (Sakawa & Kubota, 2000; Prakash et al., 2011; Zhang et al., 2011), particle swarm optimisation (PSO) (Lei, 2012a, b), ant colony optimisation (ACO) (Rossi & Dini, 2007; Xing et al., 2010) tabu search (TS) (Nowicki & Smutnicki, 2005) memetic algorithm (MA) (Lacomme et al., 2012 and Gao et al., 2011), and a differential evolution (DE) algorithm (Tasgetiren et al., 2006). However, the approximation optimization methods or metaheuristics (e.g. Tabu search and simulated annealing) usually conduct stochastic steps in their search process for solving a large size problem, these methods guarantee no optimum solution.