International Journal of Research and Innovations in Science and Technology

ISSN (Online): 2394-3858

Volume 2 : Issue 1 : 2015 ISSN (Print) : 2394-3866
International Journal of Research and Innovations in Science & Technology,
©SAINTGITS College of Engineering, INDIA
www.journals.saintgits.org
Research paper,

Job Shop Scheduling With Heuristic Algorithms

Lokesh Kumar sahu 1*, Dr.SridharK2,
1
M.Tech.Scholar, Dept.of Mechanical Engg. CSIT, Drug
2
Professor in Mansa Polytechnic College as a Mechanical Engg. Bhilai
* [email protected]

Copyright © 2015 Lokesh Kumar sahu and SridharK.This is an open access article distributed under the Creative Commons Attribution License, which permits
unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract
Job shop scheduling is atypical procedure compared with the scheduling procedure of mass production system. In this
paper palmer’s heuristic algorithm, CDS heuristic algorithm and NEH algorithm are presented the arrive the solution for
a job scheduling problem. The relevant data is collected from a medium scale manufacturing unit job order. The results
obtained from the heuristic algorithm are compared with lekin software.

Keywords: Job shop scheduling, Make span time, CDS heuristic algorithm, NEH heuristic algorithm, Palmer’s heuristic algorithm,
lekin Software.

1. Introduction
Scheduling is widely defined as the manufacturing process of assigning a set of jobs to resources over a period of time.
Job sequence and scheduling problem has a large application in the manufacturing system. Which minimize the total
flow time by selecting the most suitable sequence and give the optimal solution.And many researchers followed the
same direction: Firstly focus on Modrak and V.(2009) To compare the various heuristics algorithms based on the
output value of the make span . The heuristics has palmer, CDS and NEH algorithms. Chia and Lee (2009) [7] to
minimize the various completion time in a flow shop problem.Hejazi and Saghfian (2005) [2] A heuristic method with
the objective of minimizing the total time to complete the schedule. Kalczynski, P.J (2007) [1] It is used NEH heuristic
for minimizing the make span in permutation flow shop problem. Modrak,V.(2010) [3] flow shop scheduling
algorithms to minimize completion time for n-jobs in m-machine problem. Kamburowski, P.J (2008) [10] An improved
NEH heuristic to minimize make span in permutation flow shops. In this paper we have used A heuristic algorithms is
to be developed to minimize the maximum completion make span time. The result obtained is to be compared with
lekin software.

2. Literature Review
The main objective of this research paper is to minimize the total make-span time. In flow shop scheduling problem;
most of the Research Work has been done in this field. Jao Vitor Moccelin;Marcelo seido Nangano(2011)[4] Heuristic
for flow shop sequencing with separated and sequence independent setup time The main purpose of this paper is to
minimize the total time by using flow shop scheduling problem. Pavol Semančo and Vladimír Modrák (2012)[9] The
objective of this algorithms is to minimize the make span time by using heuristic algorithm, with NEH, Palmer’s
Slope Index, CDS and Gupta’s algorithm. Md. Sanowar Hossain, Ashraful Alam Nayon, Priyanka (2014)[5] In this
paper the author used, CDS heuristic, NEH algorithm ,Palmer’s heuristic, to solve the flow shop scheduling Problem, to
minimize the make span time. Amar Malik, Ashwani K. Dhingra (2013)[8] A Comparative Analysis of Heuristics for
Make span minimising in Flow Shop Scheduling. This algorithm is also used to minimize the make span time by using
heuristic, and tested for the problems upto 10 jobs with 3, 4 and 5Machines respectively. Shariar Farahmand Rad,Ruben
Ruiz,Naser Boroojerdian(2006)[6] A heuristic method for minimizing make span time in permutation flow shop
problem.

39
International Journal of Research and Innovations in Science and Technology
Volume 2 : Issue 1 : 2015

3. Methodology
In Job Shop Scheduling Problem; there are number of optimization techniques used. The techniques are:

a) Mathematical programming- Integer programming, Goal programming, Dynamic programming, Liner

programming, Branch and bound method, Genetic method, mixed integer liner programming, Surrogate
duality, Transportation, Network.
b) Enumerate procedure: Lagrangian relaxation.
c) Efficient methods
d) Constructive methods: priority dispatch rules, composite dispatching rules.
e) Insertion algorithms: bottleneck based heuristics, shifting bottleneck procedure.
f) Evolutionary programs: Genetic algorithm, particle swarm optimization.
g) Local search techniques: ant colony optimization, adaptive search, tabu search, simulated annealing, problem
space method.
h) Iterative methods: Artificial intelligence techniques.
i) Artificial neural network: Hopfield networks and back error propagation.
j) Heuristics algorithms (NEH ,CDS, Palmers)
k) Beam search
l) Hybrid techniques.
In this paper, use heuristics algorithms such as NEH, CDS, and Palmers to give the optimal solution.

4. Heuristic algorithms
4.1 Palmer’s algorithm

Implement this method to find out a weight age sum of each jobs.
Step 1:- Consider a job scheduling problem for 5 machines and 10 jobs.
Step 2:- Assign weights to each machine.
Weight (M1) = -4, Weight (M2) = -2, Weight (M3) = 0, Weight (M4) = +2, Weight (M5) = +4.
Step 3:- Evaluate the weight of each job, by multiplying the weights with the processing times.
Step 4:- Sort the jobs in decreasing order of their weights.
Step 5:- Formulate a sequence based on the sorting done in Step 4.
Step 6:- Calculate the Make Span time followed by the above steps.

Example
Consider 10 jobs, 5-machines problem

Table 1 10 jobs, 5-machines problem

Job-m/c M1 M2 M3 M4 M5
J1 16 4 4 14 12
J2 14 3 4 14 10
J3 18 5 5 15 13
J4 4 2 2 12 3
J5 4 2 2 12 2
J6 3 1 2 12 1
J7 2 2 2 11 2
J8 5 3 4 12 4
J9 6 4 3 12 3
J10 7 2 4 14 5
-4 -2 0 +2 +4

Calculate the weight of each job

J1= (16*4)+(4*4)+(4*0)+(14*2)+(12*4)=4
Same procedure follows and find out
J2 = 6, J3 = 0, J4 = 16, J5 = 12, J6 = 14, J7 = 18, J8 = 14, J9 =4, J10 = 12.
In decreasing order sequence:
J7 - J4 - J6 - J8 - J5 - J10 - J2 - J1 - J9 - J3.
Make-span time associated with this sequence is- 147 hours

40
International Journal of Research and Innovations in Science and Technology
Volume 2 : Issue 1 : 2015

Table 2 Calculate the make span time above sequence

Job/Machine M1 M2 M3 M4 M5
J7 2 4 6 17 19
J4 6 8 10 29 32
J6 9 10 12 41 42
J8 14 17 21 53 57
J5 18 20 23 65 67
J10 25 27 31 79 83
J2 39 42 46 93 103
J1 55 59 63 107 119
J9 61 65 68 119 122
J3 679 84 89 134 147

4.2 CDS (Campbell Dudek Smith) Algorithm

CDS algorithm uses the Johnson’s algorithm at its each iteration so as to reach a better optimal solution.
For m Machine: M1, M2, M3…... M (m) & n Jobs
Step 1:- We create (M-1) Sequence

Table 3 (M-1) Sequence

S1 M1 M(m)
S2 M1+M2 M(m-1)+M(m)
S3 M1+M2+M3 M(m-2)+M(m-1)+M(m)
…… M1+M2+M3+…… ……………….
…… M1+M2+M3+…… ……………….
S(m-1) M1+M2+M3+……M(m-1) M2+M3+…..+M(m)

Step 2:- Apply Extension of Johnson’ Algorithm to each of the above (m-1) sequences.
Step 3:- Take the best possible Make Span out of them.
Step 4:- CDS evaluates (m-1) sequences.

Consider 10 jobs 5 machine problem

Step1: (m-1) sequence; consider 5 machine problems so create a 4 sequence

S1 sequence shown in Table 5

Table 4 4 sequence
S1 M1 M5
S2 M1+M2 M4+M5
S3 M1+M2+M3 M3+M4+M5
S4 M1+M2+M3+M4 M2+M3+M4+M5

Table 5 S1 sequence
Job-m/c M1 M2 M3 M4 M5
J7 2 4 6 17 19
J3 20 25 30 45 58
J1 36 40 44 59 71
J2 48 51 55 63 73
J8 53 56 60 75 79
J9 59 63 67 87 90
J4 63 65 69 99 102
J10 70 72 76 113 117
J5 74 76 78 125 127
J6 77 77 80 137 138

Make span time with this sequence is 138 hr.

S2 sequence shown in Table 6

41
International Journal of Research and Innovations in Science and Technology
Volume 2 : Issue 1 : 2015

Table 6 S2 sequence
Job-m/c M1 M2 M3 M4 M5
J6 3 4 6 18 19
J7 5 7 9 29 31
J4 9 11 13 41 44
J5 13 15 17 53 55
J8 18 21 25 65 69
J10 25 27 31 79 83
J9 31 35 38 91 94
J2 43 46 50 105 115
J1 59 63 67 119 131
J3 77 82 87 134 147

Make span time is 147 hr.

S3 is the given sequence Table 7
Table 7 S3 sequence
Job-m/c M1 M2 M3 M4 M5
J6 3 4 6 18 19
J7 5 7 9 29 31
J4 9 11 13 41 44
J5 13 15 17 53 55
J8 18 21 25 65 69
J9 24 28 31 77 81
J10 31 33 37 91 95
J2 45 48 52 105 115
J1 61 65 69 119 131
J3 79 84 89 134 147

Make span 147 hr.

S4 is the given sequence Table 8
Table 8 S4 sequence
Job-m/c M1 M2 M3 M4 M5
J7 2 4 6 17 19
J3 20 25 30 45 58
J1 36 40 44 59 71
J2 50 53 57 73 83
J10 57 59 63 87 91
J8 62 65 69 99 103
J9 68 72 75 111 114
J4 72 74 76 123 126
J5 76 78 80 135 137
J6 79 80 82 147 148

Make span time 148 hr

Among the sequence S1, S2, S3 & S4. Given the optimal solution S1 is 138 hr.

4.3 NEH (Nawaz Enscore Ham) Algorithm

This algorithm is known as insertion algorithm. And this algorithm is used for make span minimization then it is called
NEH Algorithm.
Steps for this NEH Algorithm:-
Step 1:- Calculate the sum of processing time for each job.
Step 2:- Sort the jobs in the decreasing order of processing times for each job.
Step 3:- Take the first to jobs in the sorted sequence and formulate different combinations.
Step 4:- find the make span for each of the combination.
Step 5:- choose the combination with minimum make span.
Step 6:- Insert the next job from the sequence obtained in Step 2.
Step 7:- Carry out all possible combination of the 3 jobs now.
Step 8:- Repeat Step 4 followed by Step 5 followed by Step 6.
Step 9:- Continue the process till all jobs are completed.
Consider 10 jobs 5 machine problem:

42
International Journal of Research and Innovations in Science and Technology
Volume 2 : Issue 1 : 2015

Table 9 10 jobs 5 machine problem

Job-m/c M1 M2 M3 M4 M5 Processing time
J1 16 4 4 14 12 50
J2 14 3 4 14 10 45
J3 18 5 5 15 13 56
J4 4 2 2 12 3 23
J5 4 2 2 12 2 22
J6 3 1 2 12 1 19
J7 2 2 2 11 2 19
J8 5 3 4 12 4 26
J9 6 4 3 12 3 28
J10 7 2 4 14 4 31

Short in decreasing order processing time in Table 10, this sequence given a result 158 hr. but in NEH heuristic
algorithms have 10 jobs, so 10 different randomly sequence.

The sequences J1-J2-J10-J9-J3-J8-J4-J5-J6-J7 give the minimum make span time in above sequence.

Table 10 Result 158 hr

Job-m/c M1 M2 M3 M4 M5
J1 16 20 24 38 50
J2 30 33 34 52 62
J10 37 39 43 66 70
J9 43 47 50 78 81
J3 61 66 71 93 106
J8 66 69 75 105 109
J4 70 72 77 117 120
J5 74 76 79 129 131
J6 77 78 81 141 142
J7 79 81 83 152 154

Make span time associated with this sequence is 154 hr

5. Lekin:
In Generic job shop scheduling system, it contains a number of scheduling & heuristics algorithms, & it’s allow the
user to link and test his own heuristics and compare their performance with the heuristics algorithms that are embedded
in the system. The Lekin system can be accommodating various machine environments:
(1) Single machine (2) Parallel machine (3) Flow shop (4) Flexible flow shop (5) Job shop
In the lekin software, firstly the user can select a menu in machine environment & enter the all necessary machine data
and job data manually. In the main menu the user also has the option of opening an existing data file. An existing file
contains the data with the machine environments and specific set of jobs. If the user wants to open an existing file &
make changes in the file and work in the modified file. At last the user can save the modified file with a new name. If
the user wants to enter a data set that is completely new, firstly the user must select a machine environment, the dialog
box appears where he has to enter the most basic information. i.e. the number of work centers and the number of
schedules. After the user has done, a second dialog box appears and where the user enters the more detailed work center
information .i.e. the no. of machine at the work center with their availability and the details needed to determine the
setup times on each machine .In the third dialog box the user has to enter the detailed information related with the job

Figure 1 Flow Shop

43
International Journal of Research and Innovations in Science and Technology
Volume 2 : Issue 1 : 2015

Figure 2 Local Search

Figure 3 Objective Chart

Figure 4 Flexible Job Scheduling System

44
International Journal of Research and Innovations in Science and Technology
Volume 2 : Issue 1 : 2015

5. Result
The comparison between algorithms with lekin software Table 11 and the DASH (shifting bottleneck) algorithms given
the optimal solution, total make span time is 135 hr

Table 11 Comparison between algorithms with lekin software

Algorithms Make span time(hr)
Palmer’s 147
CDS (Campbell Dudek Smith) Algorithm 138
NEH (Nawaz Ensore Ham) Algorithm 154
DASH (shifting bottleneck ) 135
GERENAL SB ROUTIN 147
LOCAL SEARCH 147

6. Conclusion
The present work focused on job shop scheduling problem using heuristic method such as Palmer’s heuristic,CDS
(Campbell Dudek Smith) Algorithm& NEH (Nawaz Ensore Ham) Algorithm to minimize the make span time. There
is a large scope of work in the job shop scheduling problem but there is a no perfect method found till date. So: There
are continuous research is going on to minimize the make span for a job shop scheduling problem.

References
[1] Kalczynski, P.J: On the NEH Heuristic for Minimising the Make span in Permutation Flow Shop. The International Journal
of Management Science (2007)
[2] Hejazi, and Saghafian :Flow shop Scheduling Problems with Make span Criterion.AReview, International Journal of
Production Research, 43(14), 2005, pp. 2895-2929
[3] Modrak, V: Flow Shop Scheduling Algorithm to Minimize Completion Time for n-jobs m- Machines Problem, 2010, pp.
273-278 .
[4] Jao Vitor Moccelin;Marcelo seido Nangano: Heuristic for flow shop sequencing with separated and sequence independent
setup time. Sequencing Mech. Sci. & Eng. [online]. 2011, vol.33,
[5] Md. Sanowar Hossain, Md. Asadujjaman, Md. Ashraful Alam Nayon, Priyanka Bhattacharya: Minimization of Make span in
Flow Shop Scheduling Using Heuristics method m machine n jobs problems. Industrial and Energy Engineering 2014.
[6] Shariar Farahmand Rad,Ruben Ruiz,Naser Boroojerdian: A heuristic method for minimizing make span time in permutation
flow shop problem(2006)
[7] Chia, Lee, Minimizing the total completion Time in permutation flow shop, operations . Research , Vol.6, pp. 2111-2121,
(2009).
[8] Malik, A. K. Dhingra, Comparative analysis of heuristics for make span minimizing in flow Shop scheduling. International
Journal of Innovations in Engineering and Technology. Vol. 2, pp. 263-269 (2013).
[9] P. Semančo, V. Modrák, A Comparison of Constructive Heuristics with the Objective of Minimizing Makespan in the Flow-
Shop Scheduling Problem,Acta Polytechnica Hungarica, Vol. 9, pp. 177-190, (2012).
[10] kamburowski ,P.J- An improved NEH heuristic to minimize make span in permutation Flow shop Problems. (2008)

45