Heuristic Approaches for Solving bi-objective Single Machine Scheduling Problems

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 E_max and T_max. 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 T_max (MST) and T_max (EDD) is large or between E_max (MST) and E_max (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 .

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.

p_j = processing time for job j.

d_j = due date for job j.

C_j = completion time for job j.

E_j  = Max {d_j – C_j , 0}; the earliness of job j.

E_max = Max {E_j}; the maximum earliness.

T_i = Max {C_j – d_j, 0}; the tardiness of job j.

T_max = Max {T_j}; the maximum tardiness.

MST: (minimum slack times) jobs are sequenced in non-decreasing order of minimum slack times s_j, where s_j = d_j - p_j.

SPT: (shortest processing time) they are in non-decreasing order of p_j.

EDD- rule: (Early due date) they are sequenced in non-decreasing order of d_j.

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).

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 (p_j) and the due date (d_j). In the actual schedule, job j completes at time C_j ( Baker, 2014). The two objectives under consideration are the maximum tardiness and maximum earliness. For a sequence p of the jobs, earliness E_p(j), and the tardiness T_p(j)  are given by:

C_p(1)= p_p(1),

C_p(j)= C_p(j-1)+ p_p(j),                                            j= 2, 3, ..., n,

E_p(j)= max{d_p(j)- C_p(j), 0},                      j= 1, 2, ..., n,

T_p(j)= max{C_p(j)- d_p(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 (E_max, T_max) 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=å p_j, N= {1, 2, ..., n}, k = n,  j = 1, 2, ..., n.

Step (2): Find a job j* such that   R- d_j* ≤ T_max (EDD). If there exist a tie, order these jobs by MST rule. Assign job j* in position  .

Step (3): Set R = R - p_j, 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 T_j* ≤ T_max (EDD). Also, if there exists a tie, then choose the job j* with largest s_j*. 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 E_max (MST) = E*.

Step (2): k = 1, r_j = max {s_j–E*, 0} "_jÎ N, σ = (φ), σ be the schedule jobs.

Step (3): Find a job j*ÎN with minimum r_j such that r_j* ≤ C_k-1 (if a tie exists, choose the

job j* with smallest d_j*.

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 E_j* ≤ E_max (MST). Also, if there exists a tie, then choose the job j* with smallest d_j*. 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 (E_max, T_max),

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 E_max (p) = E_max (MST) and  T_max (p) < T_max (MST) as illustrate in the following example

Example (1):  Consider 4- jobs problem

MST- sequence (4, 1, 2, 3) gives E_max = 11, T_max = 12, where the sequence (4, 3, 2, 1) gives E_max = 11, T_max = 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 E_max (p^*) = E_max (MST) from algorithm (2), and if a tie exist during the algorithm, choose the job j* with smallest d_j*. 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 = T_max (p)-1.

Step (2): Set R=å p_j, N= {1, 2, ..., n}, k = n,  j = 1, 2, ..., n.

Step (3): Find a job j* such that   R- d_j* ≤ D. If there exist a tie, order these jobs by MST rule. Assign job j* in position .

Step (4): Set R = R - p_j*, 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 = T_max (p^*)-1, go to step (2).

Note that the algorithm stops whenever T_max reached T_max (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., T_max (s) = T_max (EDD). To prove that s is efficient for problem (3). For s, T_max (s) = T_max (EDD) < T_max (s^*) " s^*Î Õ. Also, gives minimum E_max (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)

Using algorithm (2) to solve problem (2), we have E_max (MST) = 11, and  s₁= 17, s₂ = 16, s₃= 13, and s₄ = 11; r₁= 17, r₂ = 16, r₃= 13, and r₄ = 11. From r_j (j=1, 2, 3, 4), choose r₄ and assign it in position 1, then job 1, 2, 3. So, get the schedule (4, 1, 2, 3) with E_max= 11 and T_max = 12. This solution is the first efficient solution for the problem (3). Using algorithm (1) to solve problem (1), we have R=å p_j= 37, N= {1, 2, 3, 4}, k = 4, j = 1, 2, 3, 4, T_max (EDD) = 7. Find that job 4 satisfies the condition, so assign job 4 in position 4, R= 37- p₄= 18. Continue to choose jobs 1, 2, 3. So the sequence (3, 2, 1, 4) is optimal with E_max= 13 and T_max = 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 E_max= 11 and T_max = 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 E_max= 13 and T_max = 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 E_max and T_max. 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 T_max (MST) and T_max (EDD) is large or between E_max (MST) and E_max (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 .