Abstract
In this paper, a fuzzy scheduling problem with triangular fuzzy numbers for processing times and due dates is provided. Each of the n operations is to be performed on a single machine without interruption and then becomes ready for processing at time zero. We generalized some ideas by giving a definition and a theorem to find a relation between the fuzzy lower bound and the fuzzy optimal solution for a problem with number of efficient solutions that minimizes total fuzzy completion time and maximum fuzzy tardiness. Also the results show how to choose the best defuzzification method in fuzzy scheduling
Highlights
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.
Full Text
Fuzzy multiobjective scheduling problems are mainly focused on two criteria and they are occur oftenly in the real life situations. Solving multiobjective 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 quasiefficient 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 nonfuzzy case Jabbar and Ramadhan firstly introduced such relation. Later Ramadan and Begard introduced a relatin regarding the bicriteria 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 multiobjective problem is to minimize total fuzzy completion time and maximum fuzzy tardiness. We introduce a new definition for fuzzy numbers which is called qstrongly 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.
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
and the subtraction is
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.
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).
Consider a scheduling problem with njobs 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)
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 qstrongly 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 qstrongly positive. Implying that and are qstrongly positive numbers, and and are strongly positive numbers too.
Theorem 1 ( New): If the problem has 3strong 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:
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:
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.
J 
1 
2 
3 

(2, 3, 4) 
(4, 5, 7 
(4, 5, 9) 

7 
5 
2 
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= 31= 2, and =  = (8, 13, 18) (3, 8, 13) = (5, 5, 15). = ( , = . So, for this example [2, .