Dynamic job shop scheduling that considers random job arrivals and machine breakdowns is studied in this paper. Considering an event driven policy rescheduling, is triggered in response to dynamic events by variable neighborhood search (VNS). A trained artificial neural network (ANN) updates parameters of VNS at any rescheduling point. Also, a multi-objective performance measure is applied as objective function that consists of makespan and tardiness. The proposed method is compared with some common dispatching rules that have widely used in the literature for dynamic job shop scheduling problem. Results illustrate the high effectiveness and efficiency of the proposed method in a variety of shop floor conditions.
The job shop scheduling (JSS) problem has attracted many optimization methods because it still exists in most of manufacturing systems in various forms. JSS problem is well-known to be NP-hard and various methods like mathematical techniques, dispatching rules, artificial intelligence, artificial neural networks, neighborhood searches, fuzzy logic, and etc. are introduced to obtain an optimum (or a near to optimum) solution. But these methods are usually designed to address static JSS problem and real time events such as random job arrivals and machine breakdowns are ignored. Tacking into account these events, JSS problem shifts to a new kind of problem that is well-known as dynamic job shop scheduling (DJSS) problem. In DJSS problem, one or more conditions of the problem like number of jobs or number of operable machines are changed by any new event. Therefore the solution before the event is not good or even feasible longer. So in addition to scheduling problem, it is needed to deal with dynamic events in DJSS problems.
In DJSS problem, due to changes in problem condition during planning horizon, using a scheduling method with parameters set at their optimum value as used in most researches (Chryssolouris and Subramanian, 2001, Dominic et al., 2004, Qi et al., 2000 and Zhou et al., 2008) can reduce performance of the selected method. Preventing such this problem, Aydin and Oztemel (2000) used reinforcement learning agents to select proper rule for scheduling according to the shop floor conditions in real time. Shugang, Zhiming, and Xiaohong (2005) have used a heuristic obtained by training a neural network offline with the genetic algorithm. Sha and Liu, 2005a and Sha and Liu, 2005b presented a model that incorporates a data mining tool for mining the knowledge of job scheduling about due date assignment in a dynamic job shop environment to adjust an appropriate parameter according to the condition of the shop floor at the instant of job arrival. Zandieh and Adibi (2009) used artificial neural network (ANN) to estimate proper parameters of their scheduling method at any rescheduling point for minimizing mean flow time. ANN models have been studied since early 1980s with an objective of achieving human like performance in many fields of science and are intended for modeling the organizational principles of nervous system (Bose & Liang, 1996). In ANNs, a network of processing elements is designed and mathematics carry out information processing for problems whose solutions require knowledge that is difficult to describe. ANNs can be used to predict appropriate parameters of scheduling method at rescheduling point using a pattern extracted from learning sample. Compared with the traditional pattern recognition, ANN can provide an exact description for multidimensional and non-linear problems (Yating, Bin, Lei, & Wenbin, 2008).
In this study, to address multi-objective DJSS problem, variable neighborhood search (VNS) (Mladenovic & Hansen, 1997) is selected as a scheduling method at any rescheduling point because it brings together a lot of desirable properties for a metaheuristic such as simplicity, efficiency, effectiveness, generality, and etc. (Zandieh and Adibi, 2009 and Hansen et al., 2007). VNS is a new neighborhood search metaheuristic that has widely used to combinatorial optimization problems in recent years. In this paper, to enhance the efficiency and effectiveness of VNS, its parameters are updated at any rescheduling point by ANN (Zandieh & Adibi, 2009). Multi-objective performance measure that contains both makespan and total tardiness is also applied in the scheduling process.
The rest of the paper is organized as follows: in Section 2, the multi-objective job shop scheduling problem is defined in details. Variable neighborhood search algorithm is argued in Section 3. Artificial neural network is presented in Section 4. The dynamic job shop scheduling problem is defined in Section 5. Simulation study is presented in Section 6 and conclusion is located in Section 7.
In this research a scheduling method based on variable neighborhood search (VNS) is proposed for dynamic job shop scheduling problem with random job arrivals and machine breakdowns. Multi-objective performance measure that contains both makespan and total tardiness is also applied in the scheduling process. At any rescheduling point, using weights obtained from artificial neural network, proper parameters for VNS are calculated that significantly enhances the performance of the scheduling method. The proposed method was compared to some common dispatching rules using a simulated job shop under varied conditions. Results indicate that the performance of the proposed method is significantly better than those of the common dispatching rules.
