This paper presents a Genetic algorithm (GA) based procedure for finding an optimum job sequence for N jobs / M machines problem based on minimum elapsed time. The search space is so large that the Genetic algorithms outperform the conventional procedures in solving optimization problems. In this paper we propose a Bell shaped sequence for N jobs / M machines problem. The optimum sequence resemble a Bell shaped sequence (Normal or Gaussian distribution like curve). In the sense that the maximum total processing time of a job M machines lie in the middle of the sequence, next maximum lie in the right side (or left side) and the next maximum lie in the left side (or right) and so on and an example is illustrated. By including the Bell shaped sequence in the proposed GA procedure, the convergence of optimum sequence is faster since the final optimum sequence almost always resemble a Bell shaped sequence. Various test cases are discussed in Appendix.

Keywords:  Job sequencing, Genetic algorithms, Optimization, NP-hard, Two Job point crossover, Mutation, Mirror image, Bell shaped sequence, Normal distribution.

          The selection of the appropriate order in which waiting jobs may be served is called "Job sequencing". Although theoretically, it is possible to find the optimum sequence by testing each one, in practice, it is impossible to check each sequence because of the large number of computations involved. For example, if there are 4 jobs to be processed at each of the 5 machines the total number of theoretically possible different sequences will be (4!)⁵=7,962,62.Obviously, any technique to arrive at minimal elapsed time sequence at least approximately, will be quite valuable.

            Suppose there are N jobs(1,2,3,...,N) each of which has to be processed one at a time at each M machines(1,2,3,...,M). Assume that the processing time of each job on each machine is given. The problem is to find an optimum sequence so that the total elapsed time is minimal.

1. Only one job can be processed by a machine.

2. Once the operation is started, it must be performed till completion.

3. An operation can start only if the previously started operation gets completed.

4. There is only one machine in each type.

5. A job is processed as soon as possible as per the ordering requirements.

6. Only Static scheduling is considered. i.e., the processing time of all the jobs is known in prior.

7. The time taken to transfer jobs in between the machines are negligible.

        The time complexity of N jobs / M machines sequencing problem is NP-hard. GA is useful as a tool for stochastic search for finding solution for many difficult to solve problems. But simple GA is difficult to apply directly and successfully into many of these problems. Various non-standard implementations have been applied for particular problems in which GA is used as a Meta-heuristics approach. The length of the strings, genetic operators and their representations are not restricted. The performance of specific GA operators such as Mutation is very effective so that the search not to stuck at local optima.

        In N jobs / M machines problem, the job sequencing is represented as a string. We use two point crossover and mutation operators to produce an offspring. The mutation rate is 0.002.

5.Bell shaped sequence (Normal distribution)

        In the middle of the Bell shaped sequence, the highest total processing time job of M machines lies and the next highest may start from right and the next highest lie in left side etc. (or the sequence may start from left to right etc.,.) But each one is a reverse of the other. Hence we take one as Bell shaped sequence and the other as a reverse of the Bell shaped sequence (Mirror image). For example if 1,2,3,4,5 form a Bell shaped sequence assuming that the total processing time of job 3 of M machines is 30 hrs, job 4 is 25 hrs ,job 2 is 23 hrs, job 5 is 20 hrs and job 1 is 18 hrs. If we consider the sequence with job 3 of M machines in the middle and the job 4 in left, job 2 in right, job 5 in left and job 1 in right we get the sequence 5,4,3,2,1 which is the reverse of the original sequence 1,2,3,4,5.We have shown that by including these two sequences in our GA procedure (Bell shaped and Reverse Bell shaped sequences ) any one of them is optimum or very near to optimum.

The crossover probability is calculated as minimum elapse time / maximum elapse time of Y sequences. The purpose of using the crossover probability is to select the better individuals for crossover and mutation.

1. Generate X random sequences.

2. Include the Bell shaped and Reverse Bell shaped sequences with the X random sequences. The total sequences now are X+2.Let it be Y.

3. Find total elapse time for all of them.

4. Store the minimum elapsed time of each generation.

5. Find the crossover probability.

6. Take all sequences below the crossover probability of 0.9( in our case). Let it be T.

7. Perform two point crossover and mutation of T sequences.

8. These newly generated sequences form the next generation population.

9. Take the new population and repeat the above steps (2 to 8) for G generations.

10. Compare the stored minimum elapse time sequences of the G generations and take the least.

The time complexity of the proposed GA procedure is based on the population of G generations and computation of each sequence’s total elapsed time.

         Johnson’s algorithm[6] can be applied to N jobs/ Two machines sequencing problems and few cases of N jobs/Three machines. But there is no general solution available for N jobs/Three machines and N jobs/M machines problems[7]. The above-mentioned GA procedure can be applied to the N jobs/Three machines and N jobs/M machines problems. We have shown test cases involving N jobs/Three machines and N jobs/M machines in appendix.

        In this paper we discussed Bell Shaped sequence, Reverse Bell shaped sequence (Mirror image), and a new GA procedure for finding optimum solution for N jobs / M machines problem. A variation to this procedure is that depending upon the problem the population size in each generation may dynamically vary.

References:

1.David E.Goldberg, Genetic Algorithms in Search Optimization & Machine learning, Second Reprint, Pearson Education Asia pte. Ltd., 2000.

2. Gen M., and Cheng, R., "Genetic Algorithms and Engineering Design" John Wiley & Sons Inc., 2000.

3. D.T.Pham and D.Karaboga,"Intelligent optimization Techniques", Berlin: Springer- Verlag 2000.

4. John J.Grefenstette,"Genetic algorithms",IEEE Expert- October 1993.

5.Frederick. Hillier and Gerald J.Lieberman,"Introduction to Operations Research", International Editions 1995.

6. Billy E.Gillett,"Introduction to Operations Research", A Computer –oriented algorithmic approach, Tata

McGraw-Hill publishing company Ltd., New Delhi- 1982.

7. Prem Kumar Gupta and D.S.Hira,"Operation Research- An Introduction", S.Chand & Company Ltd., New Delhi-1983.

In the below test cases, the processing time is in hours.

Case 1

Let the number of machines is 2 and number of jobs is 5

The processing time of jobs in machine 1 is {5,1,9,3,10}

The processing times of jobs in machine 2 is {2,6,7,8,4}

The optimal sequence is 2,4,3,5,1

Total Elapsed time of the optimal sequence = 30

The bell shaped sequence is 2,4,3,5,1

Total Elapsed time of the bell shaped sequence is 30.

This agrees with the optimum sequence.

The Reversed bell shaped sequence = 1,5,3,4,2

Total Elapsed time of the Reversed bell shaped sequence = 45

Case 2:

Let the number of machines is 2 and the number of jobs is 9 .

The processing time of jobs in machine 1 is {2,5,4,9,6,8,7,5,4}

Processing times of jobs in machine 2 is {6,8,7,4,3,9,3,8,11}

The optimal sequence is 1,9,3,2,8,6,4,5,7

The total Elapsed time of the optimal sequence = 61

The bell shaped sequence is 1,5,3,2,6,9,4,8,7

The total Elapsed time of the bell shaped sequence is 62

The Reversed bell shaped sequence is 7,8,4,9,6,2,3,5,1

The total Elapsed time of the Reversed bell shaped sequence = 62

Both of the sequences almost agree with optimum sequence.

Case 3:

Let the number of machines is 2 and the number of jobs is 6

The processing times of jobs in machine 1 is {1,4,6,3,5,2}

The processing times of jobs in machine 2 is {3,6,8,8,1,5}

The optimal sequence is 1,6,4,2,3,5

Total Elapsed time of the optimal sequence = 32.

The bell shaped sequence is 1,6,4,3,2,5

The total Elapsed time of the bell shaped sequence is 32.

This agrees with the optimum sequence.

The Reversed bell shaped sequence is 5,2,3,4,6,1

The total Elapsed time of the Reversed bell shaped sequence is 39

Case 4:

Let the number of machines is 3 and number of jobs is 6.

The processing times of jobs in machine 1 is {3,12,5,2,9,11}

The processing times of jobs in machine 2 is {8,6,4,6,3,1}

The processing times of jobs in machine 3 is {13,14,9,12,8,13}

The optimal sequence is 4,3,1,6,2,5

The Total Elapsed time of the optimal sequence = 77

The bell shaped sequence is 5,1,2,6,4,3

The total Elapsed time of the bell shaped sequence is 81

The Reversed bell shaped sequence is 3,4,6,2,1,5

The total Elapsed time of the Reversed bell shaped sequence is 78 which almost agrees with the optimum sequence.

Case 5:

Let the number of machines is 3 and number of jobs is 5

The processing time of jobs in machine 1 is {5,7,6,9,5}

The processing time of jobs in machine 2 is {2,1,4,5,3}

The processing time of jobs in machine 3 is {3,7,5,6,7}

The optimal sequence is 5,2,4,3,1.

The total Elapsed time of the optimal sequence = 40

The bell shaped sequence is 5,2,4,3,1

The total Elapsed time of the bell shaped sequence is 40

This agrees with the optimum sequence.

The Reversed bell shaped sequence =1,3,4,2,5

The total Elapsed time of the Reversed bell

Shaped sequence is 45

Case 6:

Let the number of machines is 3 and the number of jobs is 7

The processing time of jobs in machine 1 is {5,7,3,4,6,7,12}

The processing time of jobs in machine 2 is {2,6,7,5,9,5,8}

The processing time of jobs in machine 3 is {10,12,11,13,12,10,11}

The optimal sequence is 1,4,3,6,2,5,7

The total Elapsed time of the optimal sequence is 86

The bell shaped sequence is 1,6,2,7,5,4,3

Total Elapsed time of the bell shaped sequence = 86

This agrees with the optimal sequence.

The Reversed bell shaped sequence is 3,4,5,7,2,6,1

The total Elapsed time of the Reversed bell shaped sequence is 89

Case 7:

Let the number of machines is 5 and number of jobs is 4

The processing time of jobs in machine 1 is {7,6,5,8}

The processing time of jobs in machine 2 is {5,6,4,3}

The processing time of jobs in machine 3 is {2,4,5,3}

The processing times of jobs in machine 4 is {3,5,6,2}

Processing times of jobs in machine 5: {9,10,8,6}

The optimal sequence is 1,3,2,4

The total Elapsed time of the optimal sequence is 51

The bell shaped sequence is 4,3,2,1

The total Elapsed time of the bell shaped sequence is 55

The Reversed bell shaped sequence = 1,2,3,4

The total Elapsed time of the Reversed bell shaped sequence is 52 which agrees with the optimum sequence.

Case 8:

Let the number of machines is 4 and number of jobs is 4

The processing times of jobs in machine 1 is {24,61,22,21}

The processing time of jobs in machine 2 is {7,9,8,6}

The Processing time of jobs in machine 3 is {7,5,6,8}

The Processing times of jobs in machine 4 is {29,15,14,32}

The optimal sequence is 4,1,2,3

The total Elapsed time of the optimal sequence is 125

The bell shaped sequence is 3,1,4,2

The total Elapsed time of the bell shaped sequence is 136

The Reversed bell shaped sequence is 2,4,1,3

The Total Elapsed time of the Reversed bell shaped sequence is 126. This almost agrees with the optimal sequence.

Case 9:

Let the number of machines is 3 and number of jobs is 9

The processing times of jobs in machine 1 is {4,9,5,10,6,12,8,3,8}

The processing times of jobs in machine 2 is {6,4,8,9,4,6,2,6,4}

The processing times of jobs in machine 3 is {10,12,9,11,14,15,10,14,12}

The optimal sequence is 8,1,5,7,9,3,2,6,4

The total Elapsed time of the optimal sequence is 116

The bell shaped sequence is 1,3,5,2,6,4,9,8,7

The total Elapsed time of the bell shaped sequence is 117

The Reversed bell shaped sequence = 7,8,9,4,6,2,5,3,1

The total Elapsed time of the Reversed bell shaped sequence = 117

Both sequences almost agree with the elapsed time of optimal sequence.

Technical College - Bourgas,

All rights reserved, © March, 2000