# Genetic algorithm and local search to solve Job-Shop Scheduling problems.

INTRODUCTIONNowadays, the goal of many companies and factories production is to improve profitability and competitiveness. These improvements can be made with a good optimization of resource allocation by effective scheduling. [1]Effective production scheduling mechanisms have the ability to increase productivity and machine utilization. Job shop scheduling problem (JSSP) is very important representation of typical scheduling and plays an important role in the fields of production management and combinatorial optimization. It has been demonstrated that this problem is usually NP-hard in the strong sense[2]. As proof of the difficulty of this problem the 10x10 problem formulated by Muth& Thompson in 1963 [3]remained unsolved for twenty years[4].

Due to this difficulty, and growth of problem size the focus of the researcher has turned to approximation algorithms such as heuristics and meta-heuristics (genetic algorithms, simulated annealing, and Tabu search) instead of exact methods which has become inapplicable in practice[5].In spite of this, the problem is difficult and cannot be solved efficiently by applying any single technique, so a great deal of research has focused on hybrid methods[6].For JSSP, hybrid GA and local search methods have been used, where the effectiveness of local search increases the performance of GA in locating optimal or near optimal solutions[7].

The problem investigated within this paper is a static (JSSP), where all jobs are available at time zero and all information about the system is pre-defined without any unexpected events such as machine breakdown. It can be defined as follows :

There are set n jobs J = {0, 1, ..., n, n+1} to be scheduled on set m machines M = {1, ..., m}. Each job j consists of a sequence of nj operations Oij (i = 1, ..., nj) that must schedule on a predetermined machine in a given order and a predefined processing time [8].The objective is to identify an operating job sequence for each machine taking into account the precedence constraints and time to optimally determine a feasible schedule that minimizes the makespan (Cmax) (i.e. the cumulative time to complete all the operations on all machines), where the supposed constraints on static scheduling are listed as follows:

1) Every machine can process one operation at a time.

2) Each job visits each machine once and only once.

3) Each job should be processed across the machines in a pre-defined order for one time.

4) No machine can halt a job and start another one before finishing the previous one.

5) No pre-emption is allowed between operations.

As a schedule can be represented by a vector of finish times (F1, ,Fm, ..., Fn+1), the objective function will be:

Minimize Fn+1 (Cmax)

Where Fj represents the finish time of the operation j

Instance for (JSSP) Fig 1. [9] presented A Schedule of Gantt Chart for 3X3 problem it employs only 3 jobs (J1,J2, J3) and 3 machines(M1, M2, M3) [8].

Methodology:

This paper, has proposed a hybrid genetic local search algorithm to solve (JSSP); the suggested algorithm functions can be divided into two stages. In the first stage, GA is applied to identify an initial population (best solutions). While in the second stage, a local search (TS) techniques with its short memory modifies the neighbourhood structure around each solution to intensify the research as the search progresses as shown in Fig.

2. The performance of the algorithm could possibly be evaluated through an experimental analysis with a set of benchmark problems.

First stage:

Initialize Genetic algorithms (GA) proposed by[9],which begin with an initial population consisting of individual chromosomes(a set of solutions),where each individual contains a phenotype (job sequence for each machine) and a genotype (machine schedule) artificial chromosome. The chromosome is represented by using job-based representation, where a chromosome is symbolized by a binary string, and each bit stands for the order of a job pair (u,v) for a particular machine m. This representation gives flexibility while applying the genetic operators, which are two-point crossover and mutation. Solutions are then evaluated according to value fitness (makespan),and so on GA improves the whole population through successive generations. The process of GA is presented in Algorithm 1.

The Input: AnXmscheduling problem instance P (t);

The Output: A set of best schedules for instance P (t);

1. Initialize P (t) as a random population P (t = 0);

2. Evaluate P'(t);

3. Reproduce P (t + 1) from P'(t) by selection;

4. Recombine P (t) to yield P'(t) by crossover and mutation;

5. Set t [left arrow] t + 1;

Repeat from 2 to 5 until some termination condition is met;

6. Output the best individual in P (t);

Second stage:

Within this stage a Local search is implemented by the Tabu Search algorithm on the good initial solutions generated by genetic operations in order to avoid recycling in the search. After defining a neighbourhood structure of each point in the search space Tabu search uses a local or neighbourhood search procedure iteratively, moving forward from a solution to another one in its neighbourhood. During this movement, Tabu search with short memory (Tabu list), which prevents the search process from turning back to solutions visited in previous steps, modifies the neighbourhood structure of each solution by using a simple hill climbing based on makespan estimation, i.e. a chromosome is replaced by its first neighbour whose estimated makespan is better than the actual makespan of the chromosome as the search progresses. It iterates over a number of steps, where in each iteration, the neighbourhood of the current solution has been produced and one of the neighbours is chosen for the next iteration. The local search finishes either after a number of iterations or when no neighbour satisfies the accepted criterion. Then it moves to the following solution of the perfect set to start with it again.This process presented below in Algorithm 2.

Algorithm 2: The local search algorithm

Input: C initial best solutions generate by GA for instance P (t);

Output: A best schedule evaluated for instance P (t);

For all set of best solutions ido

1. Evaluate schedule C (i);

2. Generate the NS neighbourhood of the current solution;

If there is a better solution then

3. Replace the current solution with and return to 1;

4. Update the Tabu list;

else

5. Replace the current solution with best solution among the examined;

6. update the Tabu list;

If iterations threshold is not reached then go to 2; return the best schedule evaluated so far;

RESULTS AND DISCUSSION

The implementation of the algorithm is evaluated on a number of benchmarks on the job-shop scheduling problem instances from literature. The size of the benchmark instances varies from 10 to 20 jobs and from 5 to 20 machines. Taking into consideration (FT10 , FT20) offered by Fisher and Thompson[3],three problems (ABZ5-7) generated by Adams, Balas&Zawack [10]; ten 10 x 10 problems (ORB01-10) generated by Applegate and Cook[11] and 15problems of different sizes (LA01-15) generated by Lawrence[12].From the computer outputs, it could be observed that the suggested algorithm produced excellent solutions for all instances analysed. Generally, in most of the examples, it come back to the optimal solutions. In the small number of other examples the solutions were very near to the optimum. Additionally, the suggested algorithm gave excellent results or at least equal solutions to those returned by the simple genetic algorithm that constitutes the first stage of the suggested algorithm. This means that the second stage greatly improves the research process.

Summary:

Due to the fact that job-shop scheduling problems (JSSP) NP-hard combinatorial optimization problems and most single techniques cannot solve this problem efficiently, the literature has focused on hybrid methods[13].Therefore, this paper proposesaneffective andextremely easy method, to implement the hybrid algorithm based on genetic algorithm and local search method to solve (JSSP) which provides better solutions for most problems within a reasonable computational time period. The implementation for suggested algorithm being in two distinct phases. Firstly, to get a set of best solutions implement conventional genetic algorithm (GA), using binary and job-based representation, two-point crossover, bit-flip mutation and elitist strategy selection. To improve some of these solutions, in second phase, local search techniques Tabu search (TS) procedure is applied for each solution to hopefully find optimal solutions between them. The proposed algorithm gives better results for most of the benchmark problems compared with JSSP taken from the literature using the two algorithms separately. It can be confirmed that a combination of local search and genetic algorithms is an encouraging approach to improve the resolution of job-shop scheduling problems.

ARTICLE INFO

Article history:

Received 12 October 2014

Received in revised form 26 December 2014

Accepted 1 January 2015

Available online 17 February 2015

REFERENCES

[1] R.H., E.V. and Azab, 2012. "Sequence-based MILP Modeling for Flexible Job Shop Scheduling," Proceedings of IIE Conference & Expo, vol. May 19-23. Orlando, Florida, USA.

[2] Zobolas, G., C. Tarantilis and G. Ioannou, 2008. "Exact heuristic and meta- heuristic algorithms for solving shop scheduling problems.," Metaheuristics Sched. Ind. Manuf. Appl., 128: 1-40.

[3] Muth, J.F. and G. Thompson, 1963. Industrial Scheduling. NJ: Prentice Hall, Englewood Cliffs.

[4] Ombuki, B.M. and M. Ventresca, 2004. "Local Search Genetic Algorithms for the Job Shop Scheduling Problem," Appl. Intell., 21: 99-109.

[5] Ponnambalam, S.G., P. Aravindan and S.V. Rajesh, 2000. "A Tabu Search Algorithm for Job Shop Scheduling," Int. J. Adv. Manuf. Technol., 16: 765-771.

[6] Vazquez, M. and D. Whitley, 2000. "A comparison of genetic algorithms for the static job shop scheduling problem," in Parallel Problem Solving from Nature PPSN VI, pp: 303-312.

[7] Sin, O.C., N.H. Moin and M. Omar, 2012. "Multi Parents Extended Precedence Preservative Crossover For Job Shop Scheduling Problems" Multi Parents Ext. Preced. Preserv. Crossover Job Shop Sched. Probl., pp: 170-181.

[8] Kebabla, M. and L.H. Mouss, 2012. "A local search genetic algorithm for the job shop scheduling problem," Rev. des Sci. la Technol. - RST-, 3(1): 60-68.

[9] Yamada, T. and R. Nakano, 1997. "Genetic algorithms in engineering systems," IEE Control Eng. Ser., 55: 134-160.

[10] Adams, J., E. Balas and D. Zawack, 1988. "The Shifting Bottleneck Procedure for Job Shop Scheduling," Manage. Sci., 34: 391-401.

[11] Applegate, D. and W. Cook, 1991. "A Computational Study of Job-shop Scheduling," ORSA J. Comput., 2: 149-156.

[12] Lawrence, J.J. and R. Yeh, 1994. "The influence of Mexican culture on the use of Japanese manufacturing techniques in Mexico,"Manag. Int. Rev., 34(1): 49-66.

[13] Jain, A.S. and S. Meeran, 1999. "Deterministic job shop scheduling: Past, present, Future," Eur. J. Oper. Res., 113: 390-434.

Inaam Jabbar Kadhim, Shahrul Nizam and Sabira Khatun

School of Computer and Communication Engineering, Universiti Malaysia Perlis

Corresponding Author: Inaam Jabbar Kadhim, School of Computer and Communication Engineering, Universiti Malaysia Perlis

E-mail: prog.inaam@gmail.com

Printer friendly Cite/link Email Feedback | |

Author: | Kadhim, Inaam Jabbar; Nizam, Shahrul; Khatun, Sabira |
---|---|

Publication: | Advances in Environmental Biology |

Article Type: | Report |

Date: | Feb 1, 2015 |

Words: | 1808 |

Previous Article: | Service quality, customer satisfactions and restaurants' performance appraisal in hotel industry. |

Next Article: | An evaluation of snorkeling satisfaction at Pulau Payar Marine Park, Kedah, Malaysia. |

Topics: |