On Pareto Set for a Bi-criterion Scheduling Problem Under Fuzziness.

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.

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 

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.