Nitt paper A fuzzy multi-objective based un-related parallel Machine Scheduling

Abstract--- In this paper, we have addressed a Multi
Objective Problem (MOP) which covers-minimize the
makespan, tardiness, load variation, flow time and secondary
resources constraints for unrelated parallel machine
scheduling problem with consideration of inherent uncertainty
in processing times and due dates. To resolve the above
computationally challenge problem in a reasonable time and
to find a good approximation of Pareto frontier, we have
proposed a Multi-Objective Evolutionary Algorithm (MOEA)
based Fuzzy-Non-dominated Sorting Genetic Algorithm
(FNSGA-II). Over randomly generated test problems, the
performance of the proposed algorithm is validated and the
results are analyzed for the benefit of the manufacturer.
Finally, statistical analysis has been conducted and found that
the proposed algorithm performs reasonably well in terms of
quality, computational time, diversity and spacing metrics.
Keywords– Load Variation, MOEA, Makespan,
Tardiness, Unrelated Parallel Machine
I. INTRODUCTION
HE parallel machine scheduling problem (PMSP) is a very
common production environment that can be found in
several manufacturing situations, in which the allocation of a
set of jobs are assigned to a number of parallel machines in
order to meet customer’s requirement. In general, from the
literature it is found that PMSP is categorized as identical,
uniform and unrelated parallel machine scheduling
problem[1]. Among the above mentioned classifications, it is
found that for unrelated PMSP (UPMSP) the processing time
of each job depends on machines with different processing
capabilities it is assigned to, where workstations are supposed
to be non-identical. However, handling of UPMSP’s with real
life cases is a challenge for researchers and Practitioners due
V.K.Manupati, Assistant professor, Department of Mechanical
Engineering, KL University, Andhra Pradesh, India. E-mail:
manupativijay@gmail.com
R. Sridharan, Professor, Department of mechanical Engineering, NIT
Calicut, Kerala, India. E-mail: sreedhar@nitc.ac.in
N. Arudhra, Student, Department of Mechanical Engineering, KL
University, Andhra Pradesh, India. E-mail: arudhra19@gmail.com
P.Bharadwaj, Student, Department of Mechanical Engineering, KL
University, Andhra Pradesh, India. E-mail:bharadwaj.popuri9@gmail.com
D.Trinath, Student, Department of Mechanical Engineering, KL
University, Andhra Pradesh, India. E-mail:trinathh@outlook.com
M.V.B.T.Santhi, Assistant professor, Department of Computer Science
and Engineering, KL University, Andhra Pradesh, India. E-mail:
santhi_ist@kluniversity.in
to the fact that they are mostly NP-hard in nature and their
special characteristics/requirements in practice [2].
The unrelated parallel machine system has been solved
with many methods and techniques and it has been widely
addressed in the literature from past few years. Leeet al. [6]
addressed the UPMSP to minimize the objective function i.e.,
with dedicated machines and common deadlines kim et al.[4]
and arnaout et al.[5] presented a simulated Annealing and ant
colony algorithm optimization approach for the UPMSP with
sequence dependent setup times.
In real world scheduling problems many factors are often
uncertain. This research deals with scheduling of number of
jobs on an unrelated parallel machine system with secondary
resource constraints. Where, each job can only be processed if
its required machine and other secondary resources are
available
The remainder of this paper is organized as follows. In
section 2, we give a detailed description of the problem with
the basic assumptions and developed a mathematical model
along with the constraints. Section 3 explains the mapping of
NSGA-II, MPSO algorithms for solving the MOP. The
experimentation with an illustrative example having different
complex scenarios is illustrated in Section 4. In Section 5, the
results and their discussions are detailed. The paper concludes
with Section 6 suggesting the directions of the future work.
II. PROBLEM DESCRIPTION
In this paper, we propose a multi-objective UPMSP with
non-zero ready times, job-sequence-and machine-dependent
setup times, and the auxiliary resource constraints in a fuzzy
based environment for improving the performance measures
such as makespan, flow time, tardiness and machine load
variation. Here we consider a set of jobs with j = {1,2.., n} of
n that have to be processed on exactly one machine out of a set
M= {1,2.., m} of m parallel machines. The jobs are processed
on machines that are available continuously to process at most
one job J at a time. When jobs are processing on the machines
we have consider that pre-emption is not allowed and jobs are
processing on machines k with their processing times,
tardiness, makespan and load variation. In this problem, we
consider a sequence dependent and machine dependent which
deals with processing times, and setup times, when a machine
switches its production from job i to job j on the same
machine. We do not consider setup times before processing
the first job on a machine. In this problem the occurrence of
machine idle time is allowed. Idle time on a machine may be
A fuzzy Multi-Objective Based Un-Related Parallel
Machines Scheduling Problem with Sequence and
Machine Dependent Setup Times
V.K.Manupati, R. Sridharan, N. Arudhra, P. Bharadwaj, D.Trinath and M.V.B.T. Santhi
T
International Conference on Advances in Design and Manufacturing (ICAD&M'14) 1275
ISBN 978-93-84743-12-3 © 2014 Bonfring

required to complete a job on its due date, avoiding earliness.
However, to meet the requirements from real-world
production, we have considered more than two objectives
corresponding to constraints for Multi objective problem. The
above mentioned problem makes several assumptions that are
worth highlighting.
2.1 Assumptions
1. Each job requires an operation that can be done on all
machines,
2. Job’s setup times are sequence and machine
dependent,
3. Jobs may have different arrival (ready) times,
4. Assignment of a job to a machine is permitted if the
required secondary resource(s) (e.g., tool, die) is (are)
available,
5. Processing times of jobs are machine dependent,
6. Preemption and machine breakdown are not allowed,
7. Processing times and due dates of jobs due to possible
fluctuations in real world are subject toepistemic
uncertainty (i.e. lack of knowledge in estimating these
parameters precisely).
The indices, parameters and variables used to formulate
the problem mathematically are described below.
1
0
1
0
1 sin
Decision varibles :
if job i precedes job j on machine k
otherwise
if job i is assigned to machine k
otherwise
if proces g of job i is finished before
X
ijk
Yjk
Zij

= 


= 

= sin
0
proces g of job j starts
otherwise





2.2 Mathematical Model
By allocating the above mentioned assumptions and
notations, the problem is being formulated as the following
fuzzy mixed–integer non–linear programming (FMINLP)
model.
ISBN 978-93-84743-12-3 © 2014 Bonfring

Objectives :
N
= w c (1)i i
i=1
N
= w (c -c )(D) (2)i i+1 i
MinZ1
Min Z2
M
i=1
= w (cin -s )i i
i
Z3 i
∑
∑
N
(3)
=1
M k= (D)(c -c ) (4)max max
k=1
Subjected to constraints :
1 ;
1 1
MinZ4

N m
Xijk j
i k
i j
∑
∑
= ∀∑ ∑
= =
≠
;
(5)
(6)
1, ,
,
1
;
1
1
N
X Yijk jk j k
i
i j
N
X Yijk ik
j
i N
j
= ∀∑
=
≠
≤∑
=
= …
≠
(7)
, ,    (8)
, ) (9)
,
(1 ) Max{c } ;,
(1 ) (c , ) ; (
1
1;
c A Xijk s s pj N i ijk j jk
M
c A z Max s p Yj N ij i j jk jk
k
i j k
i
z zij ji
jÎS i jr
i jÎ
+ − ≥ + +
+ − ≥ + ∑
=
+ =
≠
( )
(10),
, (11),
;
;
1
S i jr
i jÎS i jr
T C di
M
X zijk ij
i
k
i i
≠
≠≤∑
=
≥ ∀─
{ } ( )
(12)
0; 0; , 0,1 ; , , .      13
, ,
C T I X Y Z Î i j k
i i ijk ik ij
≥ ≥
The above mentioned objectives, i.e. minimization of total
weighted makespan(Z1), total weighted flow time(Z2)total
weighted tardiness(Z3), machine load variation(Z4) are given
by Eqs. (1) – (4), respectively. Eq (5)assures that each job is
only assigned to one position on a machine. Eq(6) suggests
that if job jis allotted to machine k, then it is adopted by
another job indicating dummy job 0. Constraint (7)specify that
at most one job can immediately adopt the previously allotted
job i on machine k. Constraint (8)computes the completion
time of job when it is processed instantly after job i on
machine . Constraint (9 and 10)ensures that if job I and j
needs same tool, one must be finished earlier before starting
the other. Constraint (11)gives the relation between Xijk and
Zij.Eq(12)computes tardiness of job i.Eventually Eq(13)points
the non-negativity and integrality constraints.
III. MULTI-OBJECTIVE BASED EVOLUTIONARY
ALGORITHM
Most of the UPMSPs are NP-hard in nature and due to its
characteristic it is necessary to solve more than two objectives
simultaneously to find out the optimal solutions that are very
close to reality. In general, it is very difficult to solve the
multiple objectives simultaneously thus we adopted multi-
objective based evolutionary algorithms for solving the above
mentioned complex problem.[7] In this paper, we apply a
NSGA-II which includes parito ranking and crowding system
mechanism for selection of the individuals
3.1.Nondominated sorting Genetic Algorithm
Goldberg was the first who suggested the concept of non-
dominated sorting genetic algorithm (NSGA) and Srinivas and
Deb were the first to implement it. Where NSGA differs from
well known simple genetic algorithm is only in the way the
selection operator works. Although NSGA has been used to
solve a variety of MOPs, its main drawbacks include: (i)high
computational complexity of non-dominated sorting, (ii) lack
of elitism, and (iii) the need for specifying the tunable
parameter. With the advent of NSGA-II, the above mentioned
drawbacks have been resolved.
3.1.1. Initial population generation
Fig.1: Initial Population Generation.
We randomly generate the initial population for a given
population size. According to the characteristics of the
proposed problem, encoding schema and its representation is
designed. An example of the encoding scheme for the problem
is illustrated in Fig 1. Here, we have considered the number of
jobs(1 to 6) as chromosome which is having length seven,
where jobs should process on machines (1 to 4) in such a way
that the secondary resources ( 1 to 3 ) must available. In the
second set of the chromosome representation the machines
and their secondary resources and the encoding scheme of this
layer is shown in Fig 2b. In this layer, zeroes indicate, no job
assign on the machine. One more advantage of indicating
zeroes is for maintaining the chromosome length as uniform.
3.1.2. Evolutionary operators
Cross over
Crossover chooses genes from parent chromosomes and
produce a new offspring. Crossover is done by swapping
portions between two parent chromosomes. It is based on
basic parameter called crossover probability. Specific
crossover built for a particular problem can improve
performance of the genetic algorithm.
Mutation
ISBN 978-93-84743-12-3 © 2014 Bonfring

Mutation randomly used for alternating the values of
particular genes to prevent diminishing all solutions in
population into a local optimum of solved problem.
Non dominated sorting
Non dominating sorting is done by choosing the best
pareto front which is spread throughout the space by
tournament selection based on Pareto domination.
Fig.2: Schematic Procedure for Processing NSGA-II.
OP –Offspring population
PP - Parent population
Fig 2, describes the schematic algorithm throughout the
processing of NSGA-II (Deb et al. 2000)
crowding distance
Crowding distance can be calculated for all chromosomes
of same pareto front, then individual having large crowding
distance is selected to obtain uniform distribution.
Stopping rule
If the maximum generation is reached then stop.
IV. EXPERIMENTATION
Here, Card (g) describes the cardinality of test sample, and
α, β represents the control of job arrival and control of
tightness respectively.
Table 1: Test Sample (TS) Form Machine Shop
Table 1 represents a raw data of random test sample (TS)
taken from a cable and manufacturing company that is
incorporated as unrelated parallel machine which have
sequence dependent and machine dependent setup times
.
V. RESULTS AND DISCUSSION
Figure 3: Pareto Optimal Front for Sets Considering
Makespan vs. Flow Time.
Makespan vs. Tardiness.
Makespan vs. Machine Load Variation.
Pareto optimal front is obtained using the evolutionary
operators based on concerned performance measures(Fig:3,
Fig:4, Fig: 5) such as minimization of makespan, flowtime,
tardiness, and machine load variation, for randomly selected
test samples. The make span is the total completion time of
jobs, flow time is the time taken by the required job to
complete, tardiness is lateness or slow processing i.e., more
than due date, machine load variation is the time to setup or
calibration of machine during processing of jobs on the
machines. Results show better solutions and achieved Pareto
optimal solutions
VI. CONCLUSION AND FUTURE WORK
This paper proposes a fuzzy multi objective UPMSP with
non zero ready times, sequence and machine dependent setup
times. Moreover, we have considered secondary resource
0
200
400
45.542.940.931.123.120.916.614.2 7.3
flowtime
Makespan
Makespan vs Flowtime
Set 1
Set 2
0.00
100.00
200.00
45.5
42.9
40.9
32.3
31.9
23.8
20.9
16.6
14.2
7.3
Tardiness
Makespan
Makespan vs Tardiness
Set
3
0.00
200.00
25.8
33.9
18.7
45.9
9.3
24.9
46.8
48.3
13.4
35.6
MachineLoad
variation
Makespan
Makespan vs Machine load
variation Set 1
Set 2
Set 3
ISBN 978-93-84743-12-3 © 2014 Bonfring

constraints to simultaneously solving different performance
measures to obtain pareto optimal solutions. Here, we have
considered different performance measures as minimization of
makespan, total weighted tardiness, total weighted flow time,
machine load variation. To solve the above mentioned
complex NP hard problem it is necessary to adopt a multi-
objective based evolutionary algorithm i.e., NSGA-II. With
different problem sets by varying its cardinality starting time
and due date the performance of the algorithm is examined.
Experimental results show that the proposed approach is
performing better and obtained optimal solutions in the future
work, one can compare with different multi-objective
evolutionary algorithms and also on large data sets that can
bring the experimentation close to reality.
REFERENCES
[1] T. Cheng, C. Sin, A state-of-the-art review of parallel-machine
schedulingresearch, European Journal of Operational Research 47
(1990) 271–292.
[2] S.A. TORABI, N.Sahebjamnia, S.A.Mansouri,M. Aramon bajestani, “A
particle swarm optimization for fuzzy multi-objective unrelated parallel
machines scheduling problem”,Applied Soft Computing, 13(2013)4750-
4762.
[3] J.-Y. Bang, Y.-D. Kim, Scheduling algorithms for a semiconductor
probing facil-ity, Computers and Operations Research 38 (2011) 666–
673.
[4] J.-P. Arnaout, G. Rabadi, R. Musa, A two-stage ant colony
optimizationalgorithm to minimize the makespan on unrelated parallel
machines withsequence-dependent setup times, Journal of Intelligent
Manufacturing 21(2010) 693–701.
[5] F.A. Cappadonna,A. Costa,S. Fichera, “Make span minimization of
unrelated parallel machines with limited human resources”,Procedia
CIRP 12(2013)450-455.
[6] Lee, Cheng-Hsiung, Ching-Jong Liao, and Chien-Wen Chao. "Unrelated
parallel machine scheduling with dedicated machines and common
deadline." Computers & Industrial Engineering (2014).
[7] Deb, Kalyanmoy. "Multi-objective optimization." Search
methodologies. Springer US, 2014. 403-449.
Dr. Vijay Kumar Manupati received the B-Tech
degree in Department of mechanical engineering from
Siddhardha Engineering College, and M-Tech in
Department of Mechanical engineering with Industrial
Engineering and Management as a specialization from
National Institute of Technology Calicut. He received
his PhD in Department of Industrial and Systems
Engineering from Indian Institute of Technology
Kharagpur. His current research interests belong include
Intelligent manufacturing systems, agent/multi-agent/mobile-agent systems
for distributed control, simulation, integration of process planning and
scheduling in manufacturing. He has published papers inInternational Journal
of Production Research, Computers and Industrial Engineering, and
International Journal of Advanced Manufacturing Technology.
Dr.R.Sridhran completed his B. E. Honours in
Mechanical engineering from madras University, M-
Tech in Department of Industrial Engineering and
Operation Research specialization from IIT Kharagpur,
and Ph. D. in department of Industrial Engineering from
IIT Bombay. He had published many publications and
technical reports in reputed journals. His areas of
research are Operation Management, Supply Chain
Management, Decision Modelling, Simulation Modelling and Analysis
Arudhra Nerella pursuing his Bachelor degree in
Mechanical Engineering from KLUniversity
(Vijayawada, Andhra Pradesh, India). He worked on
several projects like “Controlling the Defects in
Centrifugal Casting”, “Developed a Flexible
Manufacturing System using Cellular Manufacturing
Techniques”. He is a Member of American Society of
Mechanical Engineers. His research interest includes manufacturing,
production, and Supply chain management
TRINATH DESIBOYINA, was born on June 12th
1992 and perusing B .Tech in mechanical engineering
at KLUniversity(2011-2015).He has done internship at
GENTING LANCO Power(India) Private Limited,
Kondapalli,and done an automobile oriented project on
‘Aero car’s, an environmental oriented project on
‘Solar cell’, and a technical project on ‘Conditional
monitoring on rotating machines using vibrational
analysis’ these were done as a part of curriculum
BHARADWAJ POPURI: was born on July 30th
1993
and pursuing B.Tech in mechanical engineering at
KLUniversity (2011-2015),he has done internship on
Quality control charts for variables and attributes at
“Model Dairy Private Limited”, and done his project’s
on ‘ wire electric discharge machining’ and ‘lean
manufacturing in processing industry’ as a part of
curriculum.
M.V.B.T.Santhi received the M-Tech degree in
Computer Science and Engineering from AN
University, in 2010 & B-Tech degree in Computer
Science and Engineering from Jawaharlal Nehru
Technology University, Hyderabad, in 2003 .She is
currently working as an Assistant Professor in
Department of Computer Science & Engineering,
Koneru Lakshmaiah University, Vaddeswaram, Guntur
Dist.A.P
ISBN 978-93-84743-12-3 © 2014 Bonfring

Nitt paper A fuzzy multi-objective based un-related parallel Machine Scheduling

Recommended

More Related Content

What's hot (18)

Viewers also liked (6)

Similar to Nitt paper A fuzzy multi-objective based un-related parallel Machine Scheduling (20)

Recently uploaded (20)

Nitt paper A fuzzy multi-objective based un-related parallel Machine Scheduling