Abstract
In this paper a bi-criterion fuzzy scheduling problem was presented and the problem under consideration is total fuzzy completion time and maximum earliness, where the processing times and the due dates are triangular fuzzy numbers. Each of jobs is to be processed without interruption on a single machine and becomes available for processing at time zero. A new definition of fuzzy numbers was given namely m-strongly positive fuzzy numbers, through this definition we found an interval which restricts the range of the fuzzy lower bound and presented a relation between the fuzzy lower bound and the fuzzy optimal solution with number of efficient solutions. Also we found the exact solution of the problem through finding the Pareto set.
Keywords
Main Subjects
Highlights
In this paper, we investigated the problem which was the total fuzzy completion time and maximum earliness, where the processing times and the due dates are triangular fuzzy numbers.
We presented a new structure of fuzzy number , and through this we found a relation between the fuzzy lower bound and the fuzzy optimal solution with number of efficient solutions. This relation restricted the range of the fuzzy lower bound which is a main factor to find an optimal solution. Also we found the exact solution under this structure, through finding the Pareto set.
Full Text
1. Introduction
Different approaches to fuzzy multi-objective have been considered with fuzzy parameters (Duenas and Petrovic, 2008). (Ishii and Tada, 1995) studied the maximum tardiness with fuzzy precedence relation. An extensive review of scheduling problems with multi-objectives was introduced by ( T’kindt and Billaut, 2001) where they focused on single machine scheduling, parallel-machine scheduling, flow shop and fuzzy scheduling problems. Many research articles in scheduling problems dealt with earliness penalties. (Jayanthi et al., 2017) minimized earliness and tardiness costs where both processing times and due dates are fuzzy (Niroomand et al., 2016) focused on a problem of minimizing earliness and tardiness with common fuzzy due date on a single machine. Two important types of bi-criteria scheduling problems are there, the hierarchical problems and the simultaneous problems. Simultaneous problems mean that the two objectives have the same importance. In this case a Pareto set can be found which provides deeper insights to the decision maker to choose one of these solution ( Lei, 2009). Many important works were done regarding Pareto set. (Hoogeveen and Velde, 1995) minimized total completion time and maximum cost simultaneously. For equal processing times with respect to criteria and (Lazarev et al., 2015) found the Pareto set for these jobs. (Nguyen and Bao, 2016) found the efficient solution to the mixed shop scheduling problem by using genetic algorithm. (Abdul-Razaq and Kawi, 2010) solved simultaneously a function of square completion time and maximum tardiness. In this paper a bi-criterion scheduling problem is studied which is minimize total fuzzy completion time and maximum fuzzy earliness. A new definition of fuzzy numbers is introduced, a relation between the lower bound and the optimal solution with number of efficient solutions for a problem is given. Also an exact solution of the problem was found through the Pareto set.
2. Definitions and Notations
Definition 1. Triangular fuzzy number is a fuzzy number represented by three points The membership function of a triangular fuzzy number is defined by
Suppose that and are two triangular fuzzy numbers where and , then
(i) , which is also triangular fuzzy number,
(ii) , which is also triangular fuzzy number (Hsien, 2010).
To find a crisp value of the triangular fuzzy number, the procedure that converts a fuzzy number to its crisp value is called defuzzification. Consider the following triangular fuzzy number the centroid point method of the triangular fuzzy number is (Cheng, 1998). Let and be two triangular fuzzy processing times where and , also for the due dates and be two triangular fuzzy due dates where and . Most of the defuzzification methods lead to a rational numbers, so let be the denominator of the rational number which has a great role in this paper.
: the set {1, 2, 3,..., n},
: the set of permutation schedules,
: fuzzy processing time of job , and they are triangular fuzzy numbers (TFN),
: fuzzy due date of job ,
: fuzzy completion time of job ,
: fuzzy earliness of job , where ,
: maximum fuzzy earliness,
: crisp value of the fuzzy number ,
: the denominator of a rational number, and can be teated as a fuzzy number as , i.e. ,
(Minimum fuzzy slack times): jobs are sequenced in non-decreasing order of minimum fuzzy slack times , where ,
(Shortest processing time): jobs are sequenced in non-decreasing order of ,
(Fuzzy lower bound): is a value of the objective function which is less than or equal to the fuzzy optimal value,
(Fuzzy upper bound): is a value of the objective function which is greater than or equal to the fuzzy optimal value.
Definition 2. A feasible schedule is Pareto optimal, or efficient, with respect to the criteria and if there is no feasible schedule such that both and , where at least one of the inequalities is strict.
3. Structure of the Problem
It is important to introduce some structures of bi-criteria problems to understand the relation among their solutions as illustrated in the following table.
Let and be two criteria, then
Types |
Structures |
Notes |
Possible solutions |
s.t. |
Hierarchical problems |
Optimal solution |
|
and |
Simultaneous problems |
Pareto set, no optimal solution |
|
+ |
Sum of two problems |
Optimal solution |
Now consider a set , of jobs to be processed on a single machine without interruption. Each job has a triangular fuzzy processing time , and a triangular fuzzy due date , for . All jobs are available at time zero and the machine can only process one job at a time. The objective functions nuder study are and .
For the problem , let the fuzzy lower bound and the fuzzy upper bound , where the fuzzy completion time of jobs can be calculated according to the following formulas:
(1)
The fuzzy earliness is defined as a fuzzy maximum of zero and the difference between the fuzzy due date and the fuzzy completion time of this job, this means
(2)
where the fuzzy completion time of each job and can be obtained by Eq.(1) and maximum fuzzy earliness is
(3)
4. Pareto Set in Fuzzy Environment
It is known that the minimum slack time -rule , if no idle time is allowed , is minimized by sequencing the jobs in of non-decreasing order of . Since is irregular function then the value of is in the range . (Hoogeveen and Velde, 1995) minimized total completion time and maximum cost simultaneously in polynomial time. (Kurz and Canterbury, 2005) found the Pareto set for the same problem by using genetic algorithm. In the fuzzy environment the problem is . We will present a new definition of fuzzy numbers, and then introduce our results.
4.1. M-strongly positive numbers
Definition 3. Two fuzzy numbers and are said to be -strongly positive iff - , where is any positive number greater than or equal .
Theorem 1. If the fuzzy processing times are comparable with the ordering by one of the ranking methods , then the sequence is one of the efficient solutions.
Proof. Suppose that all , are different, so the unique sequence gives the absolute minimum of . Hence there is no sequence such that .If more than one sequence exists , let be a sequence satisfying the -rule and such that jobs with equal are in sequence. Hence there is no sequence such that . So the is one of the efficient solution.
In general the sequence must not be an efficient solution, it is possible to a sequence to have the same value as the sequence has.
Let , be a fuzzy processing time, and be its corresponding crisp value. According to the above defuzzify method . Also for . For the fuzzy earliness , , is the crisp value and can be found in the same way.
5. An algorithm
We introduce an algorithm which finds all efficient solutions (Pareto set) for the problem .
Step (0): Compute , and , let , .
Step (1): Solve [10].
Step (2): , .
Step (3): If stop, else , go to step (1).
Theorem 2. The algorithm generates all the efficient solutions of the problem if the efficient solutions are -strongly positive fuzzy numbers and .
Proof. Since the efficient solutions , where are -strongly positive, so the difference between and is , .
Let
Therefore, the difference between and is , In the steps of the algorithm we find a sequence of fuzzy earliness , and the difference between each one is -strongly positive. To apply the step of the algorithm, we have
so if then the next solution may lead to an infeasible solution(not efficient solution). Therefore must be greater than or equal to .
Consider the set of maximum fuzzy earliness and the set of total fuzzy completion time , where each two elements in both sets are m-strongly positive, this means that and are m-strongly positive , and and are m-strongly positive too, . is number of efficient solutions. Let be the fuzzy optimal value of the problem .
Theorem 3. If the efficient solutions are 3-strongly positive numbers of the problem , then there exists a fuzzy number such that and where = number of efficient solutions and .
Proof. Since , so there exists such that which proves the first part of the theorem. It remains to show that or to show that . We have
implies that .
To prove we will use the mathematical induction on .
If , that is, there is only one efficient solution which is then
since and are equal , so
Thus , so the theorem is true for .
If , that is, the number of efficient solutions is two which are and , say. Since , so . We have the following two cases:
a- If is fuzzy optimal then
since and are strongly positive , so
Thus , so the theorem is true for .
b- If is fuzzy optimal then
since they are strongly positive , so
so the theorem is true for .
If , that is, the number of efficient solutions is three which are , and , say. Since , so . We have the following three cases:
(a) If is fuzzy optimal then
since and are strongly positive , so
Thus , so the theorem is true for .
(b) If is fuzzy optimal then
since each of the difference is strongly positive , so
so the theorem is true for .
(c) If is fuzzy optimal then
since they are strongly positive , so
so the theorem is true for .
Suppose the theorem is true for , that is, the theorem is true for the efficient solutions , , , ..., . Let , that means , there are efficient solutions , , , ..., , . If any one of the first efficient solutions is fuzzy optimal and as the theorem is true for we get .
If the last efficient solution is fuzzy optimal then
implies that
and then . Thus the theorem is true for .
6. Conclusion and Discussion
In this paper, we investigated the problem which was the total fuzzy completion time and maximum earliness, where the processing times and the due dates are triangular fuzzy numbers.
We presented a new structure of fuzzy number , and through this we found a relation between the fuzzy lower bound and the fuzzy optimal solution with number of efficient solutions. This relation restricted the range of the fuzzy lower bound which is a main factor to find an optimal solution. Also we found the exact solution under this structure, through finding the Pareto set.