Bi criteria scheduling on parallel machines under fuzzy processing time

Bi-criteria Scheduling on Parallel Machines Under
Fuzzy Processing Time
Seema a
, Sameer Sharma b
and Geeta Khanna a
a
Department of Mathematics, D A V College, Jalandhar, Punjab, India
b
Research Scholar, Department of Mathematics, PTU, Jalandhar, India
Email: samsharma31@gmail.com
Abstract: Job scheduling is concerned with the optimal allocation of scare resources with objective of
optimising one or several criteria. Job scheduling has been a fruitful area of research for many decades in which
scheduling resolve both allocation of machines and order of processing. If the jobs are scheduled properly, not
only the time is saved but also efficiency of system is increased. The parallel machine scheduling problem is
widely studied optimization problem in which every machine has same work function and a job can be
processed by any of available machines. Optimising dual performance measures on parallel machines in fuzzy
environment is fairly an open area of research. In real life situations, the processing times of jobs are not always
exact due to incomplete knowledge or an uncertain environment which implies the existence of various external
sources and types of uncertainty. Fuzzy set theory can be used to handle uncertainty inherent in actual
scheduling problems.
This paper pertains to a bi-criteria scheduling on parallel machines in fuzzy environment which optimizes the
weighted flow time and total tardiness simultaneously. The fuzziness, vagueness or uncertainty in processing
time of jobs is represented by triangular fuzzy membership function. The objective of the paper is to find the
optimal sequence of jobs processing on parallel machines so as to minimize the secondary criterion of weighted
flow time without violating the primary criterion of total tardiness. The bi-objective problem with total
tardiness and weighted flow time as primary and secondary criteria respectively, for any number of parallel
machines is NP-hard. A numerical illustration is carried out to the test efficiency of the proposed algorithm.
Keywords: Fuzzy processing time, total tardiness, weighted flow time, due date, weighted job
21st International Congress on Modelling and Simulation, Gold Coast, Australia, 29 Nov to 4 Dec 2015
www.mssanz.org.au/modsim2015
690

Seema et al., Bi-criteria Scheduling on Parallel Machines under Fuzzy Processing Time
1. INTRODUCTION
Job scheduling has been a fruitful area of research for many decades in which scheduling resolve both allocation
of machines and order of processing. If the jobs are scheduled properly, not only the time is saved but also
efficiency of system is increased. The parallel machine scheduling problem is widely studied optimization problem
in which every machine has same work function and a job can be processed by any of available machines.
Optimising dual performance measures on parallel machines in fuzzy environment is fairly an open area of
research. A survey of literature has revealed little work reported on the bicriteria scheduling problems on parallel
machine in fuzzy environment. Chen and Bulfin (1989) have examined single machine scheduling problems when
all jobs have identical processing time. Cenna and Tabucanon (1991) dealt with bicriteria scheduling with parallel
identical machine minimizing the maximum tardiness. Chen and Bulfin (1994) studied scheduling on a single
machine to minimize the maximum tardiness (maximum latness) and number of tardy jobs (late jobs). Parkash
(1997) studied the bi-criteria scheduling problems on parallel machines. Fiala (1997) formulated a parallel machine
scheduling problem with two criteria to minimize the makespan and to minimize the number of job preemption.
Sarin and Hariharan (2000) considered the bicriteria problem of scheduling ‘n’ jobs on two machines to minimize
the primary criterion of maximum tardiness and secondary criterion of number of tardy jobs. Sarin and Parkash
(2004) consider the problem of scheduling jobs on parallel identical machines so as to minimize primary and
secondary criteria. Anghinolfi and Paolucci (2007) studied total tardiness scheduling problems on parallel
machines. Huo et al (2007) studied bicriteria scheduling problems involving number of tardy jobs and maximum
weighted tardiness. Gupta et al (2012) developed an algorithm for the bi-objective problem which optimizes the
number of tardy jobs without violating the value of maximum tardiness with uncertain processing time. Sharma et
al (2013) studied the bi-objective problem with total tardiness and number of tardy jobs as primary and secondary
criteria respectively for any number of parallel machines in fuzzy environment. Sharma et al (2013a) developed an
algorithm to schedule jobs on parallel identical machines so as to minimize the secondary criterion of weighted
flow time without violating the primary criterion of maximum tardiness in fuzzy environment.
The rest of paper is organized as follows: In section 2 problems is formulated. Section 3 describes the role of fuzzy
in scheduling. Section 4 deals with the theorems derived for optimising the bicriteria problem. Section 5 defines
the algorithm proposed to find the optimal sequence for bicriteria problem Weighted flow time/Total tardiness. In
section 6, numerical illustrations are carried out to test the efficiency of the proposed algorithm. The paper is
concluded in section 8 followed by the references.
2. PROBLEM FORMULATION
The following assumptions are made before proceeding with the mathematical formulation in developing
the algorithm for bicriteria problem on parallel machines.
• Jobs are available at time zero
• Jobs are independent of each other
• No pre-emption is allowed
• Machines are identical in all respects and are available all the time
• No machine can handle more than one job at a time.
The following notations will be used all the way through the present paper.
• i : ith job, i = 1, 2, 3, …, n
• di : due date of the ith job
• ci : completion time of ith job
• wi : weight of ith job
• Ti : tardiness of the ith job
• Tmax : maximum tardiness
• j : location of ith job on machine k , where
j = 1, 2, 3, …, n
• n : number of jobs to be scheduled
• m : number of machines
• ta : completion time for job ‘a’
• k : machine on which ith job is
assigned at the jth position
• WFT : weighted flow time of jobs
• Xijk :1; if job i is located at position j on
kth machine and 0; otherwise
.
Before formulating the bicriteria problem, the mathematical formulation for the single criterion is represented
first as given by Parkash (1997). These are as discussed in section 2.1:
2.1 Criterion: Total Tardiness
Tardiness is given by Ti = max (0, ci – di), where ci and di are the completion time and due date of job i, respectively.
The formulation is as follows:
691

1
1 1
1
m in Z =
S ubject to constraints:
1 --- (1)
1 , --- (2)
is binary , , -
n
i
i
n m
ijk
j k
n
ijk
i
ijk
T
X i
X j k
X i j k
=
= =
=

= ∀ 
≤ ∀
∀ -- (3)
--- (4)i i iT c d i≥ − ∀
along with non-negativity constraints.
2.2 Criterion: Weighted Flow time
The formulation to minimize the weighted flow time (WFT) is as follows:
!
1 1 1
min .
n m m
i ijk
i j k
Z w X
= = =
=   
Subject to: constraints set (1), (2) and (3) respectively, along with non-negativity constraints.
The formulation of the bicriteria problems is similar to that of single criteria problems but with some
additional constraints requiring that the optimal value of the primary objective function is not violated. The
two parts of the bicriteria problem formulation are as follows:
• Primary objective function
Subject to: Primary problem constraint
• Secondary objective function
Subject to:
a. secondary problem constraint
b. primary objective function value constraint
c. primary problem constrain
Here, the problem is divided in two steps: one is primary in which total tardiness of jobs is minimized and
in secondary step: the weighted flow time of jobs is minimised under the objective function value of primary
criterion.
3. ROLE OF FUZZY
Fuzzy set theory has been used to model systems that are hard to define precisely. Zadeh (1965) stated that
most of the early interest in fuzzy set theory pertained to representing uncertainty in human cognitive system.
Uncertainty can be thought of in an epistemological sense as being the inverse of information. Information
about a particular problem may be incomplete, imprecise, fragmentary, unreliable, vague or deficient in some
other way. Fuzzy set theory is now applied to problems in engineering, business, medical and related health
sciences and in natural sciences. A large number of deterministic scheduling algorithms have been proposed
in last decades to deal with scheduling problems with various objectives and constraints. In real life
situations, decisions to be made are often constrained by specific requirements. The decision making process
gets increasingly more complicated with increments in the number of constraints. The real world is
complex; complexity in the world generally arises from uncertainty. From this prospective the concept of
fuzzy environment is introduced in the field of scheduling. For example, the processing times of jobs may
be uncertain due to incomplete knowledge or uncertain environment which implies that there exist various
external sources and types of uncertainty. Fuzzy sets and fuzzy logic can be used to tackle uncertainty
inherent in actual scheduling problems. Here, we use triangular fuzzy membership function to represents
the uncertainty involved in processing of jobs.
Further, the system characteristics are described by membership function; it preserves the fuzziness of input
information. However, the designer would prefer one crisp value for one of the system characteristics rather
than fuzzy set. In order to overcome this problem we defuzzify the fuzzy values of system characteristic by
using the Yager’s (1981) approximation formula. For a triangular fuzzy number ( )
~
1 2 3A , , ;a a a=
~
2 3 13
(A) Average High Ranking of A = ( )
3
a a a
crisp h A
+ −
= = .
692

4. THEOREMS
The following theorems have been established to optimize the bicriteria scheduling on parallel machines
involving maximum tardiness and weighted flow time
4.1. Theorem: A sequence S of jobs following early due date (EDD) order is an optimal sequence with
maximum tardiness (Tmax).
i.e. when jobs are processed on any of available parallel machines by early due date rule, the corresponding
sequence of job processing is optimal with respect to maximum tardiness as given by Sharma et al (2013a).
4.2. Theorem: A sequence S of jobs following weighted smallest processing time (WSPT) rule, in
which the jobs are placed to the earliest available location on the machines in WSPT order, minimizes
the weighted flow time.
Proof: Let, if possible sequence S obtained by using the WSPT rule (i.e. by arranging the jobs in
decreasing order of their weights; break the ties (if any) arbitrary) is not optimal. Let there exist a better
sequence of jobs S′ (say) in which adjacent jobs i and j are interchanged.
Let Ci(S) and Cj(S) be the completion times of jobs i and j in schedule S respectively. Similarly, let Ci′(S)
and C′j (S) be the completion times of jobs i and j in schedule S′.
Therefore, we can have: For sequence S: we have:
Ci (S) = ta +1,Cj (S) = ta +2
For sequence S′: we have:
Ci (S′) = ta +2, Cj (S′) = ta +1
Next, the WTF contribution of these jobs for the sequence S is:
W (S) = wi ×Ci (S) + wj ×Cj (S)
= wi ×(ta +1)+wj ×(ta +2)
= wi ×ta + wi +wj× ta +2wj = (wi + wj )ta + wi +2wj ---- (5)
Similarly, the WTF contribution of these jobs for the sequence S′ is
W (S′) = wi ×Ci (S′) +wj ×Cj (S′)= wi ×(ta +2)+ wj ×(ta +1) = wi ta +2wi +wj ta + wj ---- (6)
= (wi + wj )ta +2wi + wj .
Since, the jobs i and j are placed by WSPT rule. Therefore, we have wi ≥ wj. Hence, from results (5) and (6),
we have: W (S′) ≥W (S).Therefore, WTF for the sequence S′ is more as compared to the sequence S.
Hence, the sequence S following the Weighted Shortest Processing Time (WSPT) rule minimizes the
Weighted Flow Time (WTF).
4.3. Theorem: A set of jobs initially arranged by Early Due Date order then a late job need to be
considered for being exchanged only with another late job or a job having the same due date improves
the value of secondary criteria of weighted flow time given the primary criterion of minimum total
tardiness.
Proof: Let us pick any two jobs i and j from the EDD schedule.
Let job j be the late job. The following cases may arise:
Case I: Job i is late and di < dj
In this case, we have either ci = cj or ci < cj.
If ci = cj, then the switching of these jobs will not improve the solution.
If ci < cj, then the tardiness T and T’
before and after the exchange are
'
max(0, ) , max(0, )i i i j j i i j j iT c d c d T c d c d= − + − = − + −
In case if ci > dj, then switching job i and job j will worsen the primary criterion.
In case if ci < dj, then switching job i and job j does not change the total tardiness and weighted flow time. The
only case in which the primary criterion is not violated and weighted flow time improves is, if ci = dj.
Case II: If job i is not late and di < dj
In this case, the total tardiness before and after switching job i and j is '
,j j i jT c d T c d= − = − . Here, we have
'
T T< .
Hence, the primary criterion of total tardiness is violated.
Case III: If job i is not late job di > dj
In this case, the total tardiness before and after switching job i and job j is '
,j j i jT c d T c d= − = − . Here, we
have '
T T< .
Hence, the primary criterion of total tardiness is again violated.
Case IV: If job i is late and di > dj
In this case, we get the similar result as we get in case I, discussed above.
Hence, we have shown that a switching among any two jobs will worsen the EDD schedule except that made under
the exchange condition ci = dj as stated in the algorithm. Hence, a set of jobs initially arranged in EDD order, a late
job needs to be considered for being exchange only with another late job or a job having the same due date to
potentially improve the value of a secondary criterion, given the primary criterion of minimizing total tardiness.
693

Seema et al., Bicriteria scheduling on parallel machines under fuzzy processing time
5. ALGORITHM
The following algorithm is proposed to find the optimal sequence for bi-criteria problem WFT/Total Tardiness:
Step 1: Find the crisp values of the fuzzy processing time of various jobs on different machines using Yager
(1981) approximation formula.
Step 2: Arrange all the jobs on the available parallel machines in an early due date (EDD) order. If there is a tie then
use Weightage Shortest Processing Time (WSPT) to break the tie.
Step 3: Let C be a set of jobs that cannot be switched and L be a set of all late jobs.
Initially, C = {∅}.
Step 4: Consider first late job i ∉ C. If none exit the go to the step 6; else go step 5.
Step 5: Check all the late jobs after job i. If there exist j ∈L, j≠i such that ci ≥ dj and wi < wj , So we exchange the
job i with job j which has maximum weight amongst all jobs satisfying these conditions; update L, if necessary else
set C = C + {i} and go to Step 4.
Step 6: Consider the first non late job i ∉ C. If none exist then exit else go to step 7.
Step 7: Check all the early jobs after job i. If there exist a non late job j after job i for which ci ≤ dj and cj ≤ di and
wi < wj ; exchange the job i with j which has maximum weight amongst all jobs satisfying the above conditions else
set C = C + {i} and go to Step 6.
6. NUMERICAL ILLUSTRATION
The following numerical illustrations are carried out to test the efficiency of algorithm proposed to optimize the
bicriteria WFT/Total Tardiness on parallel machines in fuzzy environment.
6.1. Consider an example of jobs with processing time in fuzzy environment, due date and jobs Weight given in table
1 to be scheduled on three parallel machines in a flowshop. The objective is to obtain a Sequence of the jobs
processing optimising the bicriteria taken as WTF/Total Tardiness.
Table 1. Jobs with fuzzy processing time.
Solution: The crisp values for fuzzy processing time of given jobs is as follow
Table 2. Jobs with crisp values for processing time.
On arranging the jobs in EDD order on the parallel available machines M1, M2 and M3, We have
Table 3. Jobs scheduling following EDD order.
Jobs M1 M2 M3 wi di Ti
1 0 – 29/3 4 20/3 9/3
5 0 – 20/3 1 25/3 -
4 0 - 26/3 5 26/3 -
2 20/3 – 40/3 6 29/3 11/3
3 26/3 -58/3 3 32/3 26/3
6 29/3 – 64/3 2 35/3 29/3
Therefore, Total Tardiness =
9 11 26 29 75
3 3
+ + +
= units and weighted flow time
Jobs Processing Time Due Date Weight (wi)
1 (8,9,10) 20/3 4
2 (5,6,7) 29/3 6
3 (9,10,11) 32/3 3
4 (7,8,9) 26/3 5
5 (5,6,7) 25/3 1
6 (10,11,12) 35/3 2
Jobs Processing Time Due Date Weight(wi)
1 29/3 20/3 4
2 20/3 29/3 6
3 32/3 32/3 3
4 26/3 26/3 5
5 20/3 25/3 1
6 35/3 35/3 2
694

Weighted Flow Time 1
1
n
i i
i
n
i
i
wc
w
=
=
=


=
29 20 26 40 58 64
4 1 5 6 3 2
3 3 3 3 3 3
6 5 4 3 2 1
× + × + × + × + × + ×
+ + + + +
= 15.34 units.
Therefore, set of late jobs = L= 1,2,3,6 and set of jobs that cannot be switched C = ∅
On considering 1st
late job i= 1 ∈ L and 1 ∉ C there is a late job j = 2 ∈ L, j ≠ i after job i such that ci ≥ dj and wi <
wj. Therefore on interchanging the job i with job j, the job schedule becomes
Table 4. Reduced Job scheduling table.
Jobs M1 M2 M3 wi di Ti
2 0 – 20/3 6 29/3 -
5 0 – 20/3 1 25/3 -
4 0 - 26/3 5 26/3 -
1 20/3 – 49/3 4 20/3 29/3
3 20/3 – 52/3 3 32/3 20/3
6 26/3 - 61/3 2 35/3 26/3
Therefore, Total Tardiness = 75/3 units and weighted flow time
WFT = 1
1
n
i i
i
n
i
i
wc
w
=
=
= =


20 20 26 49 52 61
6 1 5 4 3 2
3 3 3 3 3 3
6 5 4 3 2 1
× + × + × + × + × + ×
+ + + + +
= 11.8 units.
Therefore, set of late jobs = L= 1,3,6 and set of jobs that cannot be switched C = ∅
On considering 1st
late job i = 1 ∈ L and 1 ∉ C, there is no late job after job i satisfying ci ≥ dj and wi < wj , therefore
C = C + = 1 .
Now, on considering the next late job i = 3 ∈ L and 3 ∉ C, there is no late job after job i satisfying ci ≥ dj and wi <
wj , therefore C = C + = 1,3 .
Now, on considering the next late job i= 6 ∈ L and 6 ∉ C, there is no late job after job i.
So set C= C + = 1,3,6 .
Now, there is no late job i ∉C, so we pick the first non late job i =2 ∉ C.
Next, we observe that there is no early job j after job i in the schedule for which ci ≤ dj and cj ≤ di and wi < wj; so set
C = C + = 1,2,3,6
Now, on consider the next non late job i =5 ∉ C, there is no early job j after job i in the schedule for which ci ≤ dj
and cj ≤ di and wi < wj, so set C = C + = 1,2,3,5,6
Similarly, on consider the next non late job i =4, there is no early job j after job i in the schedule.
Therefore C = C + = 1,2,3,4,5,6
Hence, the optimal sequence of jobs processing is 2 – 5 – 4 – 1 – 3 – 6 with minimum WFT as 11.8 units and Total
tardiness as 75/3 units.
7. DISCUSSION
7.1. The proposed algorithm optimizes the bi-criteria problem of minimizing the weighted flow time for a
minimum value of total tardiness.
Proof: The result can be verified by considering the following two cases:
Case 1: When jobs i and j are late jobs, .i.e. i and j ∈ L
This case corresponds to step 5 of the algorithm .We know that if jobs are initially arranged in early due date order,
a late job need to be considered for being exchanged only with another late job in order to potentially improve the
value of secondary criterion of weighted flow time, given the primary criterion of minimum total tardiness.
If the conditions ci ≥ dj and wi < wj for i , j ∈ L, then job j appearing after job i in the schedule violate the primary
criterion of minimum total tardiness. Hence, jobs i and j must be exchanged in order to optimize the secondary
criterion of weighted flow time for a given minimum value of primary criterion of total tardiness.
Case 2: When jobs are early jobs
This case corresponds to step 7 of the algorithm. Since, early jobs remain early jobs even when they are exchanged.
Therefore, if there exist a non late job j after an early job i for which ci ≤ dj and cj ≤ di and wi < wj then interchange
the job i with job j which has maximum weight amongst all jobs satisfying the above conditions otherwise, the
secondary criterion of weighted flow time will remain optimized with minimum total tardiness.
7.2. If the problem of single criteria, Total Tardiness, is NP-hard, the scheduling problem on parallel
machines optimising the bi-objective function WFT / Total Tardiness will also be NP-hard.
Solution: We shall prove the result by the method of contradiction:
695

Let if possible the bi-objective function WFT / Total Tardiness is not NP-hard. Therefore, there must exists a
polynomial algorithm which can solve the problem of optimising the bi-objective function WFT / Total Tardiness
on parallel processing machines.
This implies that single criteria of Total Tardiness can be optimized in polynomial time; .i.e. Total Tardiness is not
NP-hard. This is a contradiction as Total Tardiness is NP-hard.
Hence, the scheduling problem optimising the bi-objective function WFT / Total Tardiness on parallel processing
machines will also be NP-hard.
8. CONCLUSION
In this paper a heuristic algorithm to optimize the bicriteria scheduling problem involving total tardiness and
weighted flow time on parallel machines is developed. In real life situation the processing time of jobs may vary
due to lack of complete knowledge, uncertainty and vagueness. The concept of fuzzy processing time is introduced
in processing of jobs to handle under these uncertainties. The optimal sequence of jobs processing for the problem
disused above is 2 – 5 – 4 – 1 – 3 – 6 with minimum WFT as 11.8 units and Total tardiness as 75/3 units. The study
may further be extended by using trapezoidal fuzzy numbers, by generalizing the number of machines, by
introducing the concepts of non availability constraints and machines processing the jobs with different speeds.
REFERENCES
Anghinolfi, D. and Paolucci, M., “Parallel machine total tardiness scheduling problem”, Computers and Operation
Research, 34(11) (2007) 3471-3490.
Cenna, A.A. and Tabucanon, M.T., “Scheduling problem in a job shop with parallel processor”, International Journal
of Production Economics, 25(1-3) (1991) 95-101.
Chen, C.L. and Bulfin, R.L., “Scheduling unit processing time jobs on a single machine with multiple criteria”,
Computers and Operations Research, 17 (1989) 1-17.
Chen, C.L. and Bulfin, R.L., “Scheduling a single machine to minimize two criteria: maximum tardiness and number
of tardy jobs”, IIE Transaction, 26 (1994) 76-84.
Falia, P., “Heuristic solving a bicriteria parallel machine scheduling problem”, Kybernetika, 33 (1997) 687-694.
Gupta, D., Sharma, S. and Aggarwal, S., “Bi-objective scheduling on parallel machines with uncertain processing
time”, Advances in Applied Science Research, 3(2) (2012) 1020-1026.
Huo, Y., Leung, J.Y.T. and Zhao, H., “Bicriteria scheduling problems: number of tardy jobs and maximum weighted
tardiness”, European Journal of Operational Research, 177(1) (2007) 116-134.
Parkash, D., “Bi-criteria Scheduling problems on parallel machines” Ph.D. Thesis, University of Birekshurg (1997)
Virginia.
Sarin, S.C. and Hariharan, R., “A two machine bicriteria scheduling problem”, International Journal of Production
Economics, 65(2) (2000) 125-139.
Sarin, S.C. and Parkash, D., “Equal processing time bicriteria scheduling on parallel machines”, Journal of
Combinatorial Optimization, 8(2004), 227-240.
Sharma, S., Gupta, D. and Seema, “Bicriteria scheduling on parallel machines: total tardiness and weighted flowtime
in fuzzy environment”, International Journal of Mathematics in Operational Research, 5(4) (2013) 492-507.
Sharma, S., Gupta, D. and Seema, “Bi-Objective scheduling on parallel machines in fuzzy environment”, Advances
in Intelligent System and Computing, 236 (2013) 365-372.
Yager, R.R., “A procedure for ordering fuzzy subsets of the unit interval”, Information Sciences, 24(1981) 143-161.
Zadeh, L.A., “ Fuzzy Sets”, Information and Control, 8(1965) 338-353.
696

Bi criteria scheduling on parallel machines under fuzzy processing time

Recommended

More Related Content

What's hot (18)

Viewers also liked (13)

Similar to Bi criteria scheduling on parallel machines under fuzzy processing time (17)

Recently uploaded (20)

Bi criteria scheduling on parallel machines under fuzzy processing time