The Intelligent Approaches For Job-Shop Scheduling Problems

The job-shop scheduling problem (JSSP) is a very important practical problem in both fields of production management and combinatorial optimization, and it is also one of the most general and difficult issues in traditional scheduling problems. Improving scheduling methods can increase production benefit and the resource utilization efficiency to improve the competitive ability. Because the JSSP is among the worst members of class of NP-complete problems there remains much room for improvement in current techniques and exploitation of new efficient methods. So far, there have been many research methods to deal with JSSP, such as branch-and-bound method and some heuristic procedures based on priority rules, but the difficulty and complexity of general JSSP makes it very hard for the conventional search-based methods to find an optimal solution in reasonable time. New techniques emerging from the field of artificial intelligence have been introduced to address these problems in recent years, such as simulated annealing (SA), tabu search (TS), artificial neural network (ANN) and genetic algorithm (GA), and so on. There have been already lots of computational techniques inspired by biological systems. For example, artificial neural network is a simplified model of human brain, and genetic algorithm is inspired by the human evolution. In this paper, we use another type of biological system-social system, more specifically, the collective behaviors of simple individuals interacting with their environment and each other. Someone called it as swarm intelligence. There are two popular swarm inspired methods in computational intelligence areas: Ant colony optimization (ACO) and particle swarm optimization (PSO). ACO was inspired by the behaviors of ants and has many successful applications in discrete optimization problems. The particle swarm concept originated as a simulation of simplified social system. The original intent was to graphically simulate the choreography of a bird block or fish school. However, it was found that the particle swarm model could be used as an optimizer. JSSP is one of the most general and difficult discrete problems. At present, there are no many attempts in proposing the two algorithms for the JSSP. In this paper, we use the improved algorithms of these two algorithms to resolve it. One of the algorithms is an improved ant colony optimization named as Meet Max-Min Ant System, and the other is an immune particle swarm optimization, which combines a discrete particle swarm optimization with an artificial immune system. In the Meet Max-Min Ant System, two ants complete the process of searching once together. Owing to the characteristics of the JSSP, there are lots of non-feasible solutions in the searching space, which doesnot satisfy the required constraints. So in this algorithm we use a list scheduler algorithm to restrict the set of operations that the ant is allowed to walk to in the next step. The used scheduler algorithm is proposed by Giffler and Thompson. The list scheduler algorithm generates an ordered list of all the operations of a problem instance in a step-by-step manner from to left. In every step a subset of the yet unscheduled operations is generated, which guarantees the partial schedule feasible when scheduled at the current point. Then, according to some criteria, one of these operations is chosen and appended at the end of the list of the already scheduled operations. In the Meet Max-Min Ant System, there are two important parameters: the transition probabilities p ( oj |s,t) and the pheromone value τoi ,oj. The pheromone value updates constantly in the process of searching roads of ants. In this paper, we use the pheromone model PHsuc, which is introduced by Colorni et al. for an Ant System to tackle the Job Shop scheduling problem and learns of a predecessor relation in s, where s is the ordered list of operations scheduled so far. In the model, we have a pheromone value τoi ,oj on every pair of operations, where oi ∈O and oj ∈O, we havepheromone values τv source ,oj and τo j ,vsink for all oj ∈O. The transition probabilities p ( oj |s,t) are determined as follows: ?????????????∈=∈>?=∈=∑∑∑∈∈∈otherwiseoJtnoJtstooJtjto Jovovjtio Joooojto Jvovok tjkikk tikijk tsourceksourcej0,,,,,1,[1],,1sinsin,,,,,,ττττττ where Jt is the set of operations allowed to be scheduled next. Our algorithm is impletmented in the hyper-cube framework. The updating rule of the pheromone is as follows: ?????←+∑? ∑?i jij= =oiojoiojkrrrklτo ,o τo,o1ρf (s l)1f(s)*δ(s,τ,)τ, where ρis the evaporation rateρ>0, and for i,j=1,…,n and where ( ,, )=1oi ojδs rτif s[ l ]=oi and s[ l + 1]=oj for l ∈[1 ,K ,n?1] and ( ,, )=0oi ojδs rτotherwise. In the same way the pheromone update is done for all pheromones τv source ,oj and τo j ,vsink, for j=1,…,n, δ( vsource ,oj)=1 if s[ 1 ]=oj and δ( vsource ,oj)=0 otherwise; δ( oj ,vsin k)=1if s[ n]=ojand δ( oj ,vsin k)=0 otherwise. In the immune particle swarm optimization, we use also the list scheduling algorithm to ensure the feasibility of solutions. In the follow, we will describe the important concept used in thisalgorithm. The distance between two particles is defined by the following equation: dis( Xi ? Xj)=k?[α? |f(Xi)?f(Xj)|/100+β?(D?S(Xi,Xj))/D] where f(Xi) and f(Xj) are the fitness values of the particles Xi and Xj respectively, D is the dimension of particles,k is a positice inter called acceleration coefficients, αandβare two positive weights (α+β=1), S(Xi,Xj) is called the similarity measure between particle Xi and Xj, and defined as follow: ∑== DkSXi Xjsk1( ,)() where ??s ( k)= ???10 ,,xxik ik =≠xxjkjk The particle adjusts the velocity and location by the following equations: v id = int[ wvid+c1γ1dis(pid?xid)+c2γ2dis(pgd?xgd)] x id = xid⊕vid Because it tends to get into a local optimal solution by PSO, we optimize it using the immune algorithm. In this algorithm, we use two kind of immune mechanism: vaccination and immune selection. The former can improve the fitness, and the latter can prevent the population degeneration. Vaccination makes the getted individual have a larger fitness by a larger probability by modifying the gene of certain loca. In the immune system for JSSP, there are two operations: antibody introduction and gene shift. If there is no improvement of the highest affinity degree for a certain number of generations, the two operations are performed. In the performance of each operation, we evaluate it, to endure that the fitness of the produced individuals is better than the original. The performance of the two kinds of algorithms is examined...