Abstract
In this research paper, n jobs have to be scheduled on one-machine to minimize the sum of maximum earliness and maximum tardiness. We solved a series of bi-criteria scheduling problems that related to minimize the sum of the maximum earliness and tardiness. Three new algorithms were presented, two for hierarchical objective and one for the simultaneous objective. Using the results of these algorithms, we minimize the sum of maximum earliness and maximum tardiness. This objective considered as one of the NP-hard problem, and it is also irregular, so this objective missed some helpful properties of regularity. The proposed algorithms had simple structures, and simple to implement. Lastly, they tested for different n.
Main Subjects
Highlights
In this paper, three algorithms were presented to find optimal schedule for the problem of minimizing the sum of maximum earliness and maximum tardiness during solving some problems related to these objectives Emax and Tmax. This objective is an NP-hard and it is irregular, so some properties of regular objective are missed. Therefore, we can conclude that this objective is difficult to solve, especially in the case where the range between Tmax (MST) and Tmax (EDD) is large or between Emax (MST) and Emax (EDD). The proposed algorithms were easy to run and had a simple structure. To evaluate the ability of the algorithm, it was tested on some examples with different .
Full Text
1. Introduction
Scheduling (sequencing) in the theoretical and practical is an important area of operational research. Since most of the scheduling problems have large sizes, it is necessary to find a desirable algorithm for these problems (Werner et al., 2018). Many researchers considered single objective function, where in the practical the decision maker has to choose only a single objective from many objectives (T'kindt and Billaut, 2002). Recently, multi-criteria scheduling problems have increased. In general, two structures are existed hierarchical minimization and the simultaneous minimization (Hoogeveen, 1992). In the hierarchical the objectives are not in same important, where in the simultaneous the objectives have the same important.
In this paper, scheduling jobs on single machine are considered without interruption. Each job has positive processing time and due-date. The objective function to be is the sum of maximum earliness and maximum tardiness which first is introduced by Amin-Nayeri and Moslehi (Nayeri and Moslehi, 2000). The two criteria were considered by many authors; here we introduce some recent works that related to them. Each criterion has been studied in different environments individually or composite by many authors. (Jawad et al., 2020) introduced some heuristic approaches to the total completion time and the total earliness. Also, (Ali and Jawad, 2020) used local search methods for the total completion time and the total earliness. (Cheachan and Kadhim, 2021) applied a branch and bound technique to the problem of the total completion time and the maximum earliness where the due dates are triangular fuzzy numbers. (Baker, 2014) addressed the stochastic scheduling problem to minimize total expected earliness and tardiness costs. (Chachan and Hameed, 2019) used branch and bound method to solve four criteria, completion time, the tardiness, the earliness, and the late work. With unequal release date (Aneed, 2013) found the optimal solution by branch and bound method of the sum of completion times, maximum earliness and maximum tardiness.
Here, a new algorithm was presented to minimize the sum of maximum earliness and maximum tardiness ). A new algorithm is presented which depends on an optimal solution of some related problems as shown in Figure (1). First we solved problem (1) and showed that this solution was the first efficient solution for the problem (3). Also by solving problem (2) we obtained the last efficient solution for the problem (3). The next step was finding all the efficient solutions for problem (3), and then found the sum of each efficient solution obtained the optimal solution of problem (4).
2. Notations and Definitions
In this section the following notations are used
N = the set {1, 2, 3,…, n}.
P = the set of permutation schedules.
p = a permutation schedule.
pj = processing time for job j.
dj = due date for job j.
Cj = completion time for job j.
Ej = Max {dj – Cj , 0}; the earliness of job j.
Emax = Max {Ej}; the maximum earliness.
Ti = Max {Cj – dj, 0}; the tardiness of job j.
Tmax = Max {Tj}; the maximum tardiness.
MST: (minimum slack times) jobs are sequenced in non-decreasing order of minimum slack times sj, where sj = dj - pj.
SPT: (shortest processing time) they are in non-decreasing order of pj.
EDD- rule: (Early due date) they are sequenced in non-decreasing order of dj.
Definition (1) (Jouni, 2000): Consider a problem P , a schedule pÎP (where P is the set of all schedules) is said to be feasible, if it satisfies the constraints of P.
Definition (2) (Aneed, 2013): A feasible schedule is efficient, with respect to the criteria ( f and ) if there is no any feasible schedule such that ) and ) and at least one of the inequalities is strict.
3. Mathematical Formulations
Here, some problems are considered which constructed by two objectives as shown in the Figure (1).
s.t. |
s.t.
|
+ |
2 |
4 |
3 |
1 |
and
|
Figure (1): Sub-problems
The problem can be stated as: n jobs are available for processing at time 0, and their parameters are known in advance. The key parameters in the model include the processing time for job j (pj) and the due date (dj). In the actual schedule, job j completes at time Cj ( Baker, 2014). The two objectives under consideration are the maximum tardiness and maximum earliness. For a sequence p of the jobs, earliness Ep(j), and the tardiness Tp(j) are given by:
Cp(1)= pp(1),
Cp(j)= Cp(j-1)+ pp(j), j= 2, 3, ..., n,
Ep(j)= max{dp(j)- Cp(j), 0}, j= 1, 2, ..., n,
Tp(j)= max{Cp(j)- dp(j), 0}, j= 1, 2, ..., n.
So the mathematical form of this problem can be formulated as:
, .
, . ... (P
, .
, .
4. Combine Conflicting Criteria
To solve problem (P), two structures are available to combine conflicting criteria, namely hierarchical and simultaneous (Hoogeveen, 1992). For the hierarchical case, the criteria are ranked according to their importance, where for the simultaneous case the criteria have the same importance (Hoogeveen and Velde, 1996).
4.1. Problems (1) and (2)
The problem (1) and (2) can be written as:
1/ / Lex (Tmax, Emax) and 1/ / Lex (Emax, Tmax) respectively and they are not solved yet. The optimal schedules of and are given by MST-rule and EDD-rule respectively (Abdul-Razaq and Mohammed, 2016), but there are no any direct method to solve the composition of them. So, we will present two new algorithms.
An Algorithm (1)
Algorithm (1) for problem (1) is a modification of Smith’s algorithm (Smith, 1956), and Lawler’s algorithm (Lawler, 1973).
Step (1): Set R=å pj, N= {1, 2, ..., n}, k = n, j = 1, 2, ..., n.
Step (2): Find a job j* such that R- dj* ≤ Tmax (EDD). If there exist a tie, order these jobs by MST rule. Assign job j* in position .
Step (3): Set R = R - pj, N = N - {j*}, k = k-1. If k = 0, stop. Else, go to step (2).
Proposition (1): Algorithm (1) gives optimal schedule for problem (1).
Proof: The job j* in step (2) of algorithm (1) satisfies the condition Tj* ≤ Tmax (EDD). Also, if there exists a tie, then choose the job j* with largest sj*. Hence the constructed schedule gives optimal for problem (1).
An Algorithm (2)
Algorithm (2) for problem (2) is a modification of the algorithm of Hoogeveen and Van de Velde (Hoogeveen and Velde, 1990).
Step (1): Find Emax (MST) = E*.
Step (2): k = 1, rj = max {sj–E*, 0} "jÎ N, σ = (φ), σ be the schedule jobs.
Step (3): Find a job j*ÎN with minimum rj such that rj* ≤ Ck-1 (if a tie exists, choose the
job j* with smallest dj*.
Step (4): N=N-{j*}, σ = (σ, σ (k)). If N= φ go to step (5), Else k=k+1, go to step (3).
Step (5): stop.
Proposition (2): Algorithm (2) gives optimal schedule for problem (2).
Proof: The job j* in step (3) of algorithm (2) satisfies the condition Ej* ≤ Emax (MST). Also, if there exists a tie, then choose the job j* with smallest dj*. Hence the constructed schedule gives optimal for problem (2).
4.2. Problems (3)
This problem is a simultaneous case, and it can be written as follows: 1/ / F (Emax, Tmax),
i.e., minimize a function F of two criteria with the same important. So, the optimal solution doesn’t make sense, because there exists no such solution that minimizes both criteria simultaneously. Here, we will present a new algorithm to find all the efficient solutions. MST-rule doesn’t give efficient solution for the problem (3) (Kawi and Abdul-Razaq, 2017) because there exists pÎ P such that Emax (p) = Emax (MST) and Tmax (p) < Tmax (MST) as illustrate in the following example
Example (1): Consider 4- jobs problem
i |
1 |
2 |
3 |
4 |
pi |
1 |
5 |
12 |
19 |
di |
18 |
21 |
25 |
30 |
MST- sequence (4, 1, 2, 3) gives Emax = 11, Tmax = 12, where the sequence (4, 3, 2, 1) gives Emax = 11, Tmax = 19. Therefore, the sequence (4, 3, 2, 1) dominates the sequence is (4, 1, 2, 3). To find such p (say p*), it is exactly the optimal solution of problem (2).
Proposition (3):p* is the first efficient solution of problem (3).
Proof: Since Emax (p*) = Emax (MST) from algorithm (2), and if a tie exist during the algorithm, choose the job j* with smallest dj*. So p* is efficient solution for problem (3).
An Algorithm (3)
This algorithm finds all the efficient solutions of the problem (3) which depends on the known algorithm (Van Wassenhove and Gelders, 1980).
Step (1): Find p Î Õ by using algorithm (2). p is the first efficient solution of problem (3),
D = Tmax (p)-1.
Step (2): Set R=å pj, N= {1, 2, ..., n}, k = n, j = 1, 2, ..., n.
Step (3): Find a job j* such that R- dj* ≤ D. If there exist a tie, order these jobs by MST rule. Assign job j* in position .
Step (4): Set R = R - pj*, N = N - {j*}, k = k-1. If k = 0, p* is a solution, go to step (5).
Else, go to step (3).
Step (5): D = Tmax (p*)-1, go to step (2).
Note that the algorithm stops whenever Tmax reached Tmax (EDD). This gives the following proposition.
Proposition (4): The solution of problem (1) is the last efficient solution of problem (3).
Proof: Let sÎÕ be the optimal solution of problem (1), i.e., Tmax (s) = Tmax (EDD). To prove that s is efficient for problem (3). For s, Tmax (s) = Tmax (EDD) < Tmax (s*) " s*Î Õ. Also, gives minimum Emax (s).
4.3. Optimal Schedule for Problem (4)
After characterized all the efficient solution for problem (3). Now it is clear that one of the sum of the efficient solutions is optimal schedule for problem (4). To illustrate the algorithms consider again the example (1)
1 |
2 |
3 |
4 |
|
1 |
5 |
12 |
19 |
|
18 |
21 |
25 |
30 |
Using algorithm (2) to solve problem (2), we have Emax (MST) = 11, and s1= 17, s2 = 16, s3= 13, and s4 = 11; r1= 17, r2 = 16, r3= 13, and r4 = 11. From rj (j=1, 2, 3, 4), choose r4 and assign it in position 1, then job 1, 2, 3. So, get the schedule (4, 1, 2, 3) with Emax= 11 and Tmax = 12. This solution is the first efficient solution for the problem (3). Using algorithm (1) to solve problem (1), we have R=å pj= 37, N= {1, 2, 3, 4}, k = 4, j = 1, 2, 3, 4, Tmax (EDD) = 7. Find that job 4 satisfies the condition, so assign job 4 in position 4, R= 37- p4= 18. Continue to choose jobs 1, 2, 3. So the sequence (3, 2, 1, 4) is optimal with Emax= 13 and Tmax = 7. It is also the last efficient solution for problem (3).
To find the efficient solutions for the problem (3), use algorithm (3) stating with the schedule (4, 1, 2, 3) with Emax= 11 and Tmax = 12. D = 12-1=11. Job 4 satisfies the condition, R=37-19=18. Continue with ordering the jobs according to MST-rule if there exist a tie. We get the schedule (3, 2, 1, 4) with Emax= 13 and Tmax = 7. Optimal solution for problem (4) is one of the efficient solutions namely (3, 2, 1, 4) with value 20.
5. Computational Results
Here, the results are introduced via computational tests to show the ability of the proposed algorithm. The problems were generated as follows: are generated from the uniform distribution Also, is generated from the uniform distribution . The algorithm was coding by Matlab 8.1 (R2013a) and implemented on Intel (R) Pentium (R) CPU 2117U@ 1.80 GHZ, with RAM 4.00 GB personal computer.
6. Conclusion
In this paper, three algorithms were presented to find optimal schedule for the problem of minimizing the sum of maximum earliness and maximum tardiness during solving some problems related to these objectives Emax and Tmax. This objective is an NP-hard and it is irregular, so some properties of regular objective are missed. Therefore, we can conclude that this objective is difficult to solve, especially in the case where the range between Tmax (MST) and Tmax (EDD) is large or between Emax (MST) and Emax (EDD). The proposed algorithms were easy to run and had a simple structure. To evaluate the ability of the algorithm, it was tested on some examples with different .