Techniques to Restrict an Interval of a Lower Bound in Fuzzy Scheduling Problems

The fuzzy lower bound and the fuzzy optimum solution with the number of efficient solutions were discovered to have a significant relationship in this paper. This relationship conceptually explains the difference between a fuzzy optimum solution and a fuzzy lower bound, allowing new algorithms and approaches to be developed to discover heuristic solutions to these issues. Furthermore, the defuzzification approach has an important role in limiting the gap between the fuzzy optimum solution and the fuzzy lower bound. For a given theorem, multiple approaches provide different intervals.

1. Introduction

Fuzzy multi-objective scheduling problems are mainly focused on two criteria and they are occur oftenly in the real life situations. Solving multi-objective functions is difficult in the sense that we must deal with two various objectives without possessing any prior knowledge of their respective importance. Finding efficient solutions (Pareto set) is one of the approaches that solves this type of problems. From this set the decision maker will select one of these solutions (Heide and David, 2008). In the literature the Pareto set has been studied in the field of the optimization theory by many authors. In convex optimization, Ward looked at the construction of efficient sets (Ward, 1989) Lowe et al. Characterized the set of quasi-efficient solutions to a multiple objective problem (Lowe et al., 1984). For the minimum spanning tree problem, Steiner and Radzik determined all efficient solutions (Steiner and Radzik, 2008). In scheduling problems, the paper of Van Wassenhove and Gelders was the first one that dealt with finding the efficient solutions (Van Wassenhove and Gelders, 1980). Zinchenko studied the structure of Pareto set of some vector problems in scheduling (Zinchenko, 2002). Using the standard boundary intersection technique, Jia and Ierapetritou found Pareto optimum solutions for scheduling difficulties (Jia and Ierapetritou, 2007)). For equal processing times Lazarev et al. Found the Pareto set for jobs with respect of two criteria (Lazarev, 2015), and for a shop scheduling problem Nguyen and Bao computed an efficient solution by using genetic algorithm (Nguyen and Bao, 2016). Some papers are related to this direction, starting with the non-fuzzy case  Jabbar and Ramadhan  firstly introduced  such  relation. Later  Ramadan  and Begard  introduced a relatin  regarding the  bi-criteria  problem namely maximum tardines and maximum earliness ( Amin and Ramadan, 2021). Hassan et al., generlized  the idea to three criteria to minimize the sum of total completion time, maximum earliness and maximum tardiness ( Dara et al., 2022). In the fuzzy environment  Ramadan presented  the same idea to minimize the sum of total fuzzy completion time and  maximum earliness in addition to find all  the efficient  solutions ( Ramadan, 2021).

The focus of this paper is on the structure of efficient solutions where The processing times and deadlines are triangular, fuzzy numbers. The multi-objective problem is to minimize total fuzzy completion time and maximum fuzzy tardiness. We introduce a new definition for fuzzy numbers which is called q-strongly positive fuzzy numbers, and a theorem which finds a relation between the fuzzy lower bound and the fuzzy optimal solution with number of efficient solutions. This relation restricts the fuzzy lower bound through number of efficient solutions.

1. Definitions and Notations

Definition 1: A triangular fuzzy number  can be represented by three components , where  represents the lower bound of the fuzzy number,   the upper bound for the number.  specifies a membership function for a triangular fuzzy number , where

Assume  and  be two triangular fuzzy numbers, with  and , then the addition of two fuzzy nymbers is

• , which is also triangular fuzzy number,

and the subtraction is

1. ii) , which is also triangular fuzzy number (Hsien, 2010)

Definition 2: The procedure that converts a fuzzy number to its crisp value is called defuzzification. For a triangular fuzzy number . A triangular fuzzy number's centroid point is   (Cheng, 1998).

Consider two triangular fuzzy production time   and  ( due dates) where  and . Using this method we say that  if . A special case will occur when , in this case the two numbers are comparable and there is no need to use ranking methods to map them to crisp values. The majority of defuzzification procedures result in a rational number, So, let d be the rational number's denominator, which plays an important part in this paper. Consider a problem  with two any criteria  and  to be minimized simultaneously, then

Definition 3: A sequence  is efficient solution for  if  $ no  s.t.  and , where at least one relation holds with dtrict inequality.

Definition 4: A set of all the efficient solutions for a problem is called  Pareto set.

The notations used in this paper are as follows:

: {1, 2, 3,..., n},

: all possible schedules,

: fuzzy processing time for job , and they are triangular fuzzy number (TFN),

= : fuzzy due date for job , and they are triangular fuzzy number (TFN),

: fuzzy completion time for job ,

: fuzzy lateness for job ,

: fuzzy tardiness of job , where ,

: maximum fuzzy tardiness,

: the crisp value of the fuzzy number ,

: the denominator of a rational number,

EDD (early due date): tasks are arranged in ascending order of ,

SPT (Shortest processing time): tasks are sequenced in ascending order of ,

The fuzzy lower bound ( ) is a value of the objective function that is less than or equal to the fuzzy optimum value.

 (Fuzzy upper bound): an objective function value larger than or equal to the fuzzy optimum value. 

2. Background of the Problem

A set  of  jobs to be processed on a one- machine. Each one has a fuzzy processing time  which is a triangular fuzzy number , and a triangular fuzzy due date , for . At time zero, all jobs are accessible, and the machine can only process one task at a time, and a job's execution cannot be stopped. A schedule is made by placing tasks in a certain sequence such that the fuzzy completion time  of each job j may be calculated. In fact, employment processing timelines are unpredictable. As a result, each job's completion time is unknown.

Smith proposed an approach for solving a single machine scheduling issue that reduced overall completion time while ensuring that all tasks were finished on time (Smith, 1965). Van Wassenhove extended the idea to find the Pareto set of the simultaneous problem  which is a function of two cost criteria where  and   and without constrants on jobs. The solution of this problem is difficult and sometimes is not possible, this means, there is in general no  which minimizes  and , as a result, we're looking for a sequence that provides a fair solution to both goals. (if such a sequence exists). To define such a sequence, Van Wassenhove and Gelders introduced the concept of efficiency in scheduling problems (Van Wassenhove and Gelders, 1980).

3.   Needed Calculations

Consider a scheduling problem with n-jobs with one machine and processing times that are considered to be fuzzy. Let  be the job  fuzzy processing time. The following formulas can be used to compute the fuzzy completion time of jobs:

                                                                                                                                              (1)

A penalty is charged if a task is done beyond its due date; nevertheless, if a job is performed before its due date, it is deemed early (Hsien, 2010)  The difference between the fuzzy completion time and the fuzzy due date of this job is a fuzzy maximum of zero, and the fuzzy tardiness of a work in a given sequence is a fuzzy maximum of zero, which implies

                                                   ,                                                                              (2)

where the fuzzy completion time ,  may be achieved for each job , and maximum fuzzy tardiness is

                                                                                                                  (3)

4.   Efficient Solutions and Optimal Solution

With the number of effective solutions, Jabbar and Ramadhan discovered a relationship between the lower bound and the optimization method for a problem which was minimizing total completion time and maximum tardiness (Jabbar and Ramadhan, 2006).  In the case where all the inputs data are are fuzzy numbers, we generalized the case by introducing new definition. The problem is

                                                                                                                                 (4)

 where  and . This problem is in simultaneously form and has efficient solutions, one of the efficient solutions will be fuzzy optimal for the sum of the problem, i.e.,

                                                                                                                                  (5)

For the problem (5) let the fuzzy lower bound  , the fuzzy upper bound  and  be the fuzzy optimal value. To find our results we introduce the following.

Definition 5: If (k^L+k+k^U) – (g^L+g+g^U) ≥ m, where m may be any positive integer greater than or equal to one, two fuzzy numbers  and  are q-strongly positive.

Think of the sets of maximum fuzzy tardiness  and total fuzzy completion time , where   is an efficient solution for each , and both sets have two components that are q-strongly positive. Implying that  and  are q-strongly positive numbers, and  and  are -strongly positive numbers too.

Theorem 1 ( New): If the problem has 3-strong positive numbers efficient solutions for problem , then there exists a fuzzy number  such that  and  where =number of  efficient solutions and .

Proof. Since  , so there exists  such that  this proves the first part. Now, to show that  or . We have  

 ,

 implies that .

 For  use mathematical induction on .

 If , In other words, there is just one effective solution, which is  then

  since  and  are equal , so 

Thus , which proves the case .

If , Such that, there are only two effective solutions, that are  and , instance. Since , so . The following are two scenarios:

• If is optimal then

 since  and  are -strongly positives , so the difference between  and  is . Thus , As a result, the theorem holds for  .

b- If  is optimal then

  since they are -strongly positives , so 

 so it  is true for .

 If , means we have three efficeient solutions namelly, ,  and .  Since , so . We have the following three cases:

• If is optimal then

 since  and  are -strongly positives , so the difference between  and  is . Thus , so it is true for .

 b- If  is optimal then

    since each of the difference is -strongly positive , so  so it is true for .

c- If  is optimal then

, since they are -strongly positives , so

 so it is true for .

Assume that the theorem holds for , such that, for the  most efficient solutions , , , ..., . Let  , that means , there are  efficient solutions , , , ..., , . Whether any of the first  optimal processes is the optimum, and the theorem holds fo   then we get .

If is the most efficient solution, then

 implies that

 and then . Thus it is true for .

Corollary 1:  If the efficient solutions are not -strongly positive for the problem , then  $ a fuzzy number  s.t.   and  where = number of  efficient solutions and .

 Proof. We prove only the second part which is  .

This will be done by the same way of the above theorem. Since they are not -strongly positive,  so the difference between each of any two one is less than . If  which is the worst case, then , , .

It's vital to note that the  and  values are the same, so the theorem depends  strongly on the defuzzification method.

To illustrate the theorem we give here an example. 

Consider the following data. For simple calculation we  have the due dates as cris number.

There are three efficient solutions for the problem, and by using the mentioned defuzzification method the fficient solutions for this problem are: sequence (1, 2, 3) with = (18, 26, 35) and  = (8, 13, 18) which is SPT- rule, sequence (1, 3, 2) with = (18, 28, 37) and  = (5, 10, 15), and sequence (3, 2, 1) ) with = (22, 34, 45) and  = (3, 8, 13). Now

= (18,26, 35) (3,8, 13)= (21, 34, 48),

 = (18,26, 35) (8,13, 18)= (26, 39, 53),

= (18, 28, 37)  (5, 10, 15) = (23, 38, 52), it is the sum of one the efficient solutions for   which is the sequence (1, 2, 3), and  = (23, 38, 52)  (21, 34, 48)= (-25, 4, 31),  =  . = number of efficient solutions, -1= 3-1= 2, and = - = (8, 13, 18)  (3, 8, 13) = (-5, 5, 15).   = ( ,   =  . So, for this example    [2, .