Performance Of Heuristicmethod Over Traditional Method For Solvingthe Job Sequencing Problem

Performance Of Heuristicmethod Over Traditional Method For Solvingthe Job Sequencing Problem

K. Mallikarjuna, Rajashekarpatil, Naveen Kumar H. M, Hanumanthappa S.

Department of Mechanical Engineering,Ballari Institute of Technology and Management, Bellary

Abstract

This project deals with an industrial job sequencing problem that arises in metal goods production group. The sequencing problem can be seen as a multi-mode job shop with assembly. Jobs have additional constraints such as sequence-dependent setup times. The aim of the decision-makers is to minimize the maximum lateness. This project introduces a TABU SEARCH algorithm which is a heuristic method and to be compared with a traditional optimization method such as Johnson algorithm to solve the bench mark problems and also be match the existing results with obtained results with the support of sensitive analysis.

Key words: job sequencing, lateness tabusearch

,Johnson Algorithm

1. INTRODUCTION

   Sequencing models deals with the situations in which the effectiveness measure (time, cost, etc) is a function of the order or sequence of performing a series of jobs(tasks). The selection of the appropriate order in which jobs may be done or waiting customers may be served is called sequence.[1].In sequencing problems there are two or more customers to be served (or jobs to be done) and one or more facilities (machines) are available for this purpose. Sequencing problems have been most commonly encountered in production shops where different products are to be processed over various

   combinations of machines[2]. The job-shop scheduling problem is one of the most studied problems in combinatorial optimization and a large number of papers and books deal with the numerous procedures that have been proposed to solve it, including several tabu search implementations. Although a large number of variants are found in the literature (and even more in the real world), the "classical" problem can be stated as follows. We first assume that n jobs must be scheduled on m machines.[3].

2. LITERATURE REVIEW:

   In this paper we survey the existing results for the sequencing problems in which job processing times are additional decision variables, paying special attention to the computational complexity aspects, and optimization and approximation algorithms. A second aim of the paper is an analysis of other sequencing problems of this type, not investigated in the literature.[4]

   Tabu Search (TS) was developed by Fred Glover in 1988. It was initiated as an alternative local search algorithm addressing combinatorial optimization problems in many fields like scheduling, computer channel balancing, cluster analysis, space planning etc. (Glover, 1989). However, popularization and dissemination of TS goes back to the works of Hertz and de Werra (1987, 1989, 1991). This section consists of three parts: general definitions, TS related

   definitions, and definitions related to other meta- heuristics[5],[6],[7].

   The paper deals with the sequencing problems in which job processing times, along with a processing order, are decision variables having their own associated linearly varying costs. The existing results in this area are surveyed and some new results are provided. In the paper, an attention is focussed on the computational complexity aspects, polynomial algorithms and the worst-case analysis of approximation Johnson algorithms[8],[9],[10].

3. PROBLEM DESCRIPTION:

   1. Definition:

      Suppose there are n jobs (1,2.3.n) each of which has to be processed one at a time at each of m machines (A,B,C.). The order of processing each job through machines is given (For ex, job1 is processed through machines A,C,B in this order).The time that each job must required on each machine is known. The problem is to find a sequence among (n!)m no of all possible sequence (or combination

      ),(or order) for processing the jobs so that total elapsed time for all jobs will be minimum.

      Mathematically,

      Let Ai = Time for job i on machine A, Bi = Time for job i on machine B,

      T = Time from start of first job to completion of the last job .

      Then , the problem is to determine for each machine a sequence of jobs i1,i2,i3.in, where (i1,i2,i3..in) is the permutation of the integers which will minimize T.

   2. Terminology and Notations

      1. Number Of Machines: It means the service facilities through which a jobmust pass before it is completed. Notation mi

         where, i=1,2,3.

      2. Processing Order: It refers to the order in which various machines are required for completing the job.Notation-t

      3. Processing Time: It means the time required by each job on each machine.

         The notation Tij will denote to the processing time required for ith job by jth machine (i=1,2,3,n; j=1,2,3n) .

      4. Idle Time On A Machine: This is the time for which a machine remains idle during the total elapsed time. The notation Xij shall be used to denote the idle

         time of machine j between the end of the (i-1)th job

         and the start of the ith job.

      5. Total Elapsed Time: This is the time between starting the first job and completing the last job. This also include idle time ,if exist it will be denoted by the symbol K.

      6. No Passing Rule: This rule means that passing is not allowed, i.e, same order of jobs are maintained over each machine. If each of the n jobs is to be processed through two machines A and B in order A,B then this rule means that each job will go to machine A first and then to B.

4. QADRATIC ASSIGNMENT FORMULATION:

   It deals with the nonlinear programming problem of minimizing the quadratic objective function subject to a set of linear inequality constraints.

   Min Z = Kn,mSubject to Kn,m- Pn,m 0

   Km-1,n-1 0

   tmi,nj 0

   1. Johnson Algorithm:

      Johnson algorithm is a traditional optimization technique.It has some limitations for solving job sequencing or scheduling problems

   2. Tabusearch :

      Tabu search is a heuraustic method for solving job sequencing problems. We can solve any job sequencing problem by using tabu search method . It gives more optimal results than traditional method

      .TabuSearch was developed by Fred Glover in 1988.

      . It was initiated as an alternative local search algorithm addressing combinatorial optimization problems in many fields like scheduling, computer channel balancing, cluster analysis, space planning etc. (Glover, 1989). However, popularization and dissemination of TS goes back to the works of Hertz and de Werra (1987, 1989, 1991). This section consists of three parts: general definitions, TS related

      definitions, and definition related to other meta- heuristics.

5. CASE STUDY:

   A production system with the summary and processing times of each machines are shown in below tables. The processing time of job on each machine given in the table 1 and table 2. According to this table both proposed algorithms(Johnson algorithm and Tabu search) optimum sequence, total elapsed time and idle time on each machine are shown in the table 3 and table 4.

   Table 1

   	A	B	C	D	E
   M\C1	11	13	9	16	16
   M\C2	4	3	5	2	6
   M\C3	6	7	5	8	4
   M\C4	15	8	13	9	11

   Table 2.

   	m\c1	m\c2	m\c3	m\c4	m\c5	m\c6
   Job a	20	10	9	4	12	27
   Job b	19	8	11	8	10	21
   Job c	13	7	10	7	9	17
   Job d	22	6	5	6	10	14

6. RESULTS AND DISCUSSIONS

   In this present work the optimum sequences, total elapsed time and idle time on each machine of both proposed algorithms. These results are shown in the table 3 and table 4. The major advantage of using non-traditional algorithms is that even though the number of possible sequences is very high, an optimal solution can be obtained within a fraction of seconds while compiling on a standard PC. By the graph it is observed that elapsed and idle times are minimum for Tabu search compared with Johnson algorithm..

7. GRAPHS

   Comprision of idle time for jobshop scheduling problem

   IDLE TIME

   IDLE TIME

   80

   60

   40

   20 J A

   0

   T S

   1 2 3 4

   NUMBER OF MACHINES

   Fig;1 comparison of idle times

   Comprision of idle time for jobshop scheduling problem

   Table 3:idle time of proposed algorithms

   150

   IDLE TIME(min

   IDLE TIME(min

   100

   50

   Instants	Idle time
   	Johnson algorithm	Tabu search
   1	M1:18, M2:63 M3:53, M4:27	M1:17, M2:62 M3:44, M4:26
   2	M1: 56M 2: 99 M 3: 95M 4: 105 M 5: 89M 6: 51	M1: 52M 2: 97 M 3: 93M 4: 103 M 5: 87M 6: 49

   Instants	Idle time
   	Johnson algorithm	Tabu search
   1	M1:18, M2:63 M3:53, M4:27	M1:17, M2:62 M3:44, M4:26
   2	M1: 56M 2: 99 M 3: 95M 4: 105 M 5: 89M 6: 51	M1: 52M 2: 97 M 3: 93M 4: 103 M 5: 87M 6: 49

   0

   J A

   1 2 3 4 5 6 T S

   NUMBER OF MACHINES

   Instants	Elapsed time
   	Johnson algorithm	Tabu search
   1	83	82
   2	130	129

   Instants	Elapsed time
   	Johnson algorithm	Tabu search
   1	83	82
   2	130	129

   Table 4: Elapsed time of proposed algorithms

   Fig;2 comparison of idle times

   COMPARISION OF ELAPSED TIME FOR JOB SHOP SCHEDULING

   150

   100

   50

   0

   J A

   T S

   COMPARISION OF ELAPSED TIME FOR JOB SHOP SCHEDULING

   150

   100

   50

   0

   J A

   T S

   1 2

   INSTANCES

   1 2

   INSTANCES

   Elapsed time (min)

   Elapsed time (min)

   Fig;3 comparison of elapsed times

8. CONCLUSION:

The above discussion is evident that the non- traditional method is more effective than the traditional method because, in non-traditional method there is only one sequence for given job sequence problem, but it is not possible to conclude that as a feasible sequence for given job sequencing problem. Where as in non-traditional method there are (n!)m number of sequence for given problem and can choose optimal sequence in the (n!)m sequence and conclude that as a feasible sequence for given job sequencing problem. Also it is concluded that traditional method i.e, Johnson algorithm procedure for job sequencing problem is a failure algorithm because if given conditions are fail to satisfied. Whereas non-traditional method i.e, tabu search procedure for job sequencing problem is a success method because we can solve any given job

sequencing problem irrespective of conditions.

References:

1. From Text book of OPERATION RESEARCH , S.D.SHAMA,

2. From text book of OPERATION RESEARCH , DR.PREM KUMAR.

3. Amberg, A.; Domschke, W. & Voss S. (1999). Multiple Center Capacitated Arc RoutingProblems: A Tabu Search Algorithm Using Capacitated Trees, European Journal ofOperational Research, 124, 2000, 360-376,

0377-2217

1. F. Glover, Tabu search: Part II, ORSA Journal on Computing 2 (1990) 4}32.

2. F. Glover, M. Laguna, Tabu Search, Kluwer Publishers, Boston, 1997.

3. Bard, J. F. (1988). A Heuristic for minimizing the number of tool switches on a flexible machine. IIE Transactions, 20(4), 382391.

4. Crama, Y., Kolen, A. W. J., Oerlemans, A. G., &Spieksma, F. C. R. (1994). Minimizing the number of tool switches on a flexible machine. International Journal of Flexible Manufacturing Systems, 6, 3354.

5. J.W. Barnes, J.B. Chambers, Solving the job shop scheduling problem with tabu search, IIE Transactions 27 (1995) 257}263