386 

This work is licensed under a Creative Commons Attribution 4.0 International License 

IHJPAS. 37 (1) 2024 

Ibn Al-Haitham Journal for Pure and Applied Sciences 

Journal homepage: jih.uobaghdad.edu.iq 

PISSN: 1609-4042, EISSN: 2521-3407 

  

 

 

 

 

   

1Nagham Muosa Neamah    2,*Bayda Atiya Kalaf   3Hamiden Abd El-Wahed Khalifa  

 
1,2Department of Mathematics, College of Education for Pure Sciences, Ibn Al – Haitham, University 

of Baghdad Iraq  
3Department of Mathematics, College of Science and Arts, Qassim University, Al-Badaya 

51951,Saudi Arabia. 
3Department of Operations and Management Research, Faculty of Graduate Studies for Statistical 

Research, Cairo University, Giza 12613, Egypt 

 

*Corresponding Author. baydaa.a.k@ihcoedu.uobaghdad.edu.iq 

 

 

 

 

Abstract 

           Machine scheduling problems (MSP) are considered as one of the most important classes 

of combinatorial optimization problems. In this paper, the problem of job scheduling on a single 

machine is studied to minimize the multi objective and multi objective function. This objective 

function is: total completion time, total lead time and maximum tardiness time, respectively, 

which are formulated as (∑𝑪𝒋 , ∑ 𝑬𝒋 , 𝑻𝒎𝒂𝒙) are formulated. In this study, a mathematical 

model is created to solve the research problem. This problem can be divided into several sub-

problems and simple algorithms have been found to find the solutions to these sub-problems 

and compare them with efficient solutions. For this problem, some rules that provide efficient 

solutions have been proved and some special cases have been introduced and proved since the 

problem is an NP-hard problem to find some efficient solutions that are efficient for the 

discussed problem 1// 𝐹(∑𝑪𝒋 , ∑𝑬𝒋 , 𝑻𝒎𝒂𝒙), and good or optimal solutions for the multi-

objective functions 1// ∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥,, and emphasize the importance of the dominance 

rule (DR), which can be applied to this problem to improve efficient solutions. 

 

Keywords: Maximum Tardiness, Multi-Criteria, Multi-Objective, Total Completion Times, 

Total Earliness Time.

Received 13 December 2022, Received 6 January 2023, Accepted 13 March 2023, Published 20 January 2024 

 

 

Solving the Multi-criteria, Total Completion Time, Total Earliness Time, and 

Maximum Tardiness Problem 

doi.org/10.30526/37.1.3094 

https://creativecommons.org/licenses/by/4.0/
https://jih.uobaghdad.edu.iq/index.php/j/index#1609-4042
https://jih.uobaghdad.edu.iq/index.php/j/index#2521-3407
mailto:baydaa.a.k@ihcoedu.uobaghdad.edu.iq
https://orcid.org/0000-0001-5393-4083
mailto:nagham2182011@gmail.com
https://orcid.org/0000-0003-1136-0055
mailto:baydaa.a.k@ihcoedu.uobaghdad.edu.iq
https://orcid.org/0000-0002-8269-8822
mailto:Ha.Ahmed@qu.edu.sa


  IHJPAS. 37 (1) 2024 

387 
 

1. Introduction 

       Scheduling involves distributing a set number of resources over a period of time to various 

tasks[1]. One or more objectives may be optimized as a result of this decision-making process. as 

well as, the Scheduling problem is defined as the arrangement of entities (people, tasks, vehicles, 

lecture, etc.) into a pattern in space-time in such a way that constraints are satisfied and certain 

goals are achieved [2-4]. 

Up until the late 1980s, mainstream research has concentrated on a certain single object problem. 

When more than one objective (criteria) is needed, scheduling problems become more difficult to 

model and solve. It is frequently implausible that different objectives will be best served by the 

same set of decision variables [5-8]. 

As a result, there is a trade-off between the multiple objectives. This type of problem is known as 

a multi-objective scheduling problem. Multi-objective scheduling problems are the term used to 

describe this kind of problem [9]. A set of Pareto optimal solutions (Efficient solutions), rather 

than a single optimal solution, are established using multi-criteria optimization based on competing 

objective functions. This set includes one (many) solution(s) that no other solution(s) is better with 

respect to objective functions[[10-14]. 

The most important literature survey for the last eight years. [15] discussed the multi-criteria in 

order to establish a collection of efficient solutions for the general problem, and scheduling 

problems that are researched on a single machine are considered. 1// (∑𝑪𝒋, ∑𝑻𝒋, 𝑻𝑴𝒂𝒙) , 1// 

𝑭(∑𝑪𝒋, ∑𝑬𝒋 , 𝑬𝑴𝒂𝒙) , 1// ∑𝑪𝒋 + ∑𝑻𝒋 + 𝑻𝑴𝒂𝒙 , 1// ∑𝑪𝒋 + ∑𝑬𝒋 + 𝑻𝑴𝒂𝒙. [16] examined the multi-

objective problem, which is the sum of completion time, tardiness, earliness, and late work. 1// 

∑ (𝑬𝒋 + 𝑻𝒋 + 𝑪𝒋 + 𝑼𝒋 + 𝑽𝒋)
𝒏
=𝟏 ,1//∑ (𝜶𝑱𝑬𝒋 + 𝜷𝒋𝑻𝒋 + 𝜽𝒋𝑪𝒋 + 𝜸𝒋𝑼𝒋 +𝝎𝒋𝑽𝒋)

𝒏
=𝟏 ,1/𝑺𝒇/ ∑ (𝜶𝒋𝒇𝑬𝒋𝒇 +

𝒏
=𝟏

𝜷𝒋𝒇𝑻𝒋𝒇 + 𝜽𝒋𝒇𝑪𝒋𝒇 + 𝜸𝒋𝒇𝑼𝒋𝒇 +𝝎𝒋𝒇𝑽𝒋𝒇). They suggested an Upper Bound (limits) UB and a Lower 

Boundary (limits) LB be used in the application of the Branch and Bound method. [17] studied the 

multi-criteria (∑𝑪𝒋 , 𝑻𝒎𝒂𝒙, 𝑹𝑳), multi-objective function (∑𝑪𝒋 + 𝑻𝒎𝒂𝒙 + 𝑹𝑳) and   founded the 

optimal solution by using the BAB method with and without DR then using some heuristic 

methods. [18] introduced a heuristic algorithm to reduce the (∑𝑪𝒋 + 𝑬𝒎𝒂𝒙 + 𝑻𝒎𝒂𝒙) in a single 

machine scheduling. 

In this paper, survey the tricriteria scheduling problem and begin with some basic scheduling 

concepts of multi-criteria problems, and basic rules are given in section 1. Section 2 provides 

information on problem formulation, analysis, and various algorithms. The Dominance Rule is 

described in section 3. In section 4 by proving several rules, we show there exists is an effective 

solution to our problem. The conclusions is given in section 5 and upcoming works. 

2. Significant Notations. 

In this paper, the following notations are used: 

𝑵:  jobs set s. t. 𝑁 = {1,2, … , 𝑛}. 

𝒏: number of available jobs.   

𝒑𝒋: Ttime of the job 𝑗′𝑠 processing, which means it must be processed for a period of length  𝒑𝒋.      

𝒅𝒋: The due date for job 𝑗 (or the jobs’ due date), the optimal date for finishing the jobs; job 

termination after the deadline is allowed but will result in a penalty.  

 

 



IHJPAS. 37 (1) 2024 

388 
 

𝒔𝒋: The Job's slack time for 𝑗 s. t. 𝑠𝑗 = 𝑑𝑗 − 𝑝𝑗. 

𝑪𝒋: The job 𝑗′𝑠 completion time where 𝐶𝑗 = ∑ 𝑝𝑘
𝑗
𝑘=1 . 

𝑳𝒋: The lateness time of jobs, s. t. 𝐿𝑗 = −(𝑑𝑗 − 𝐶𝑗) = 𝐶𝑗 − 𝑑𝑗. 

𝑬𝒋: The earliness of job 𝑗  s. t. 𝐸𝑗 = 𝑚𝑎𝑥 {−𝐿𝑗 , 0} =  𝑚𝑎𝑥{𝑑𝑗 − 𝐶𝑗 , 0}  . 

𝑻𝒋: The tardiness of job 𝑗  s. t. 𝑇𝑗 = 𝑚𝑎𝑥 {𝐿𝑗 , 0} =  𝑚𝑎𝑥{𝐶𝑗 − 𝑑𝑗, 0}  .    

∑𝑪𝒋: Total completion time. 

∑𝑬𝒋: Total earliness time. 

𝑻𝒎𝒂𝒙 : Maximum tardiness  s. t. 𝑇𝑚𝑎𝑥 = 𝑚𝑎𝑥𝑗∈𝑁{𝑇𝑗}. 

𝑭: The ₱-problem's objective function. 

𝑭𝟏: The (𝑆₱)-problem's objective function. 

Shortest Processing Tim (SPT): Jobs are Sequencing in non-decreasing order of the processing 

times 𝑝𝑗 (i. e. 𝑝1 ≤ 𝑝2 ≤ ⋯ ≤ 𝑝𝑛), this rule is well known to minimize ∑𝐶𝑗 for problem 1// ∑𝐶𝑗 

[8]. 

Earliest Due Date (EDD): Jobs are sequenced in non-decreasing order of their due dates 

𝑑𝑗(i. e. 𝑑1 ≤ 𝑑2 ≤ ⋯ ≤ 𝑑𝑛), this rule used to minimize 𝑇𝑚𝑎𝑥  for problem 1// 𝑇𝑚𝑎𝑥 [19]. 

Minimum Slack Time (MST): Jobs are sequenced in non-decreasing order of their slack time 

𝑠𝑗 = 𝑑𝑗 − 𝑝𝑗 (i. e. 𝑠1 ≤ 𝑠2 ≤ ⋯ ≤ 𝑠𝑛). To minimize 𝐸𝑚𝑎𝑥  using this rule [20]. 

Efficient Solution (EFSO): A feasible schedule 𝛼∗ is known as Pareto optimal or ( non-

dominated) If there is absolutely no feasible schedule 𝛼, then the set of feasible schedules with 

regard to the criteria ℎ1 , ℎ2 and ℎ3 such that ℎ1(𝛼) ≤ ℎ1(𝛼
∗) , ℎ2(𝛼) ≤ ℎ2(𝛼

∗) and ℎ3(𝛼) ≤

ℎ3(𝛼
∗), are satisfied with at least one of the inequalities [21]. 

 

3. Mathematical Formulation  

In this section, the three-criteria scheduling problem (1// 𝑭(∑𝑪𝒋 , ∑ 𝑬𝒋 , 𝑻𝒎𝒂𝒙)) to be studied will 

be described. Let the number of jobs available at time 0 be represented by 𝑁 = {1,2, … , 𝑛}, 

(i. e, 𝑟𝑗 = 0 for all 𝑗) and need processing on just one machine. For each job, 𝑗 has a processing 

time 𝑝𝑗 and a due date 𝑑𝑗, given a list of jobs in the sequence 𝛼 = (𝛼1, 𝛼2, … , 𝛼𝑛), the earliest 

completion time possible 𝐶𝑗 = ∑ 𝑝𝛼𝑘
𝑛
𝑘=1 , the tardiness of job 𝑗, 𝑇𝑗 = 𝑚𝑎𝑥 {𝐶𝑗 − 𝑑𝛼𝑗 , 0} , the 

earliness of job 𝑗, 𝐸𝑗 = 𝑚𝑎𝑥 {𝑑𝛼𝑗 − 𝐶𝑗 , 0}. The aim of this problem is finding a schedule  α ∈ 𝒮 to 

find a schedule, (where 𝒮 is the set of all possible feasible schedules; where a feasible schedule 

means it satisfies all the constraints of the problem ₱) that minimizes the multi-criteria 

(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥), which is denoted by (𝑆𝐶𝑆𝐸𝑇), can be formulated mathematically as follows: 

𝑀𝑖𝑛{∑𝐶𝑗, ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥}
s. t.                                

𝐶1 = 𝑝𝛼1                                            

𝐶𝑗 ≥ 𝑝𝛼𝑗                      𝑗 = 1,2, … , 𝑛

𝐶𝑗 = 𝐶𝛼(𝑗−1) + 𝑝𝛼𝑗     𝑗 = 2,… , 𝑛    

𝑇𝑗 ≥ 𝐶𝑗 − 𝑑𝛼𝑗              𝑗 = 1,2, … , 𝑛

𝐸𝑗 ≥ 𝑑𝛼𝑗 − 𝐶𝑗              𝑗 = 1,2, … , 𝑛

𝑇𝑗 ≥ 0, 𝐸𝑗 ≥ 0            𝑗 = 1,2, … , 𝑛}
 
 
 
 

 
 
 
 

                                                                                          …(𝑆𝐶𝑆𝐸𝑇). 



IHJPAS. 37 (1) 2024 

389 
 

Where 𝛼𝑗  indicate where job 𝑗 falls in the ordering α and 𝒮 represents the collection of all 

schedules. Finding the set of all efficient solutions to the problem (𝑆𝐶𝑆𝐸𝑇) is challenging since 

it’s an NP-hard problem (because the problem 1// ∑ 𝐸𝑗
𝑛
𝑗=1  is NP-hard [22]). 

Proposition (1):  There is an efficient schedule for the problem (𝑆𝐶𝑆𝐸𝑇) that satisfies the SPT 

rule. 

Proof: (a) first, assume that  𝑝𝑖 ≠ 𝑝𝑗 for all 𝑖, 𝑗. The unique sequence SPT,  (𝑆𝑃𝑇∗) provides the 

bare minimum of  ∑𝐶𝑗. As a result, no sequence exists 𝛿 ≠ 𝑆𝑃𝑇∗ s.t. 

 ∑𝐶𝑗(𝛿) ≤ ∑𝐶𝑗 (𝑆𝑃𝑇
∗), ∑𝐸𝑗 (𝛿) ≤ ∑𝐸𝑗 (𝑆𝑃𝑇

∗), and 𝑇𝑚𝑎𝑥(𝛿) ≤ 𝑇𝑚𝑎𝑥(𝑆𝑃𝑇
∗)                          (1)                                                                    

The presence of one or more strict inequalities. 

 (b) If there is more than one sequence SPT (the processing times of jobs are equal), assume 𝑆𝑃𝑇∗ 

be a sequence that satisfies the rule of SPT and jobs with equal processing times in the EDD and 

MST sequence. If a set of jobs that are to be early or partially early is specified, then this EDD and 

MST order minimized ∑𝐸𝑗. 

Note that if the event is several jobs at the same processing times, the due date is considered 

identical, or slack times, then 𝑆𝑃𝑇∗ is not unique. Show that each 𝑆𝑃𝑇∗- sequence is an efficient, 

sequence that does not satisfy the SPT rule which cannot dominate an 𝑆𝑃𝑇∗ sequence by (1.1). If 

δ is an SPT-sequences but not an SPT* sequence, it cannot dominate 𝑆𝑃𝑇∗ since  

∑𝐶𝑗(𝛿) = ∑𝐶𝑗(𝑆𝑃𝑇
∗), ∑𝐸𝑗 (𝑆𝑃𝑇

∗) ≤ ∑𝐸𝑗 (𝛿) and 𝑇𝑚𝑎𝑥(𝑆𝑃𝑇
∗) ≤ 𝑇𝑚𝑎𝑥(𝛿)              

by virtue of the EDD and MST rule. Hence all the 𝑆𝑃𝑇∗ sequences are efficient.                            

As mentioned in proposition (1), shown that the SPT rule is efficient for the problem (𝑆𝐶𝑆𝐸𝑇) but 

the EDD rule does not, as shown in the example below. 

Example (1): Suppose the problem (𝑆𝐶𝑆𝐸𝑇) has the following data in Table 1: 

Table 1. The data of  𝑝𝑗 , 𝑑𝑗 , and  𝑠𝑗 for problem (𝑆𝐶𝑆𝐸𝑇) 

 Job1 Job2 Job3 Job4 Job5 

𝑝𝑗 2 5 7 5 8 

𝑑𝑗 6 9 8 11 14 

𝑠𝑗  4 4 1 6 6 

 

A feasible schedule is provided by the SPT rule(1,2,4,3,5) and (1,4,2,3,5), hence 

(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) = (67,6,13) from 𝑆𝑃𝑇∗ order (1,2,4,3,5) and (∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) = (67,7,13) 

from SPT order (1,4,2,3,5), it is clear that in the  𝑆𝑃𝑇∗sequence the tasks  (2,4) are arranged with 

equal processing time in the rule of the MST or EDD. But EDD rule (1,3,2,4,5) with 

(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) = (71,4,13) and MST rule (3,1,2,4,5) with (∑𝐶𝑗, ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) = (76,1,13) 

hence 𝑆𝑃𝑇∗the sequence gives an efficient solution for the problem (𝑆𝐶𝑆𝐸𝑇). 

For the problem(𝑆𝐶𝑆𝐸𝑇), we can deduce seven sub problems (𝑆₱𝑖) for 𝑖 = 1 to 7: 



IHJPAS. 37 (1) 2024 

390 
 

1) 1//𝐿𝑒𝑥(∑𝐶𝑗, ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) problem  𝑆₱1. 

2) 1//𝐿𝑒𝑥(∑𝐶𝑗, 𝑇𝑚𝑎𝑥 , ∑𝐸𝑗) problem  𝑆₱2. 

3) 1//𝐿𝑒𝑥(𝑇𝑚𝑎𝑥 , ∑𝐶𝑗  , ∑𝐸𝑗) problem  𝑆₱3. 

4) 1//𝐿𝑒𝑥(𝑇𝑚𝑎𝑥 , ∑𝐸𝑗 , ∑𝐶𝑗) problem  𝑆₱4. 

5) 1//𝐿𝑒𝑥(∑𝐸𝑗 , ∑𝐶𝑗 , 𝑇𝑚𝑎𝑥) problem  𝑆₱5. 

6) 1//𝐿𝑒𝑥( ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥 , ∑𝐶𝑗) problem  𝑆₱6. 

7) 1// (∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥) problem  𝑆₱7. 

(1) 1// 𝑳𝒆𝒙(∑𝑪𝒋, ∑𝑬𝒋, 𝑻𝒎𝒂𝒙)(𝑺₱𝟏): The definition of this problem is as follows: 

𝑀𝑖𝑛  {𝑇𝑚𝑎𝑥}                                                   
s. t.                                                                    

∑ 𝐶𝑗
𝑛
𝑗=1 = 𝐶∗ where 𝐶∗ = ∑ 𝐶𝑗(𝑆𝑃𝑇)

𝑛
𝑗=1                

∑ 𝐸𝑗
𝑛
𝑗=1 ≤ 𝐸, 𝐸 ∈ [∑ 𝐸𝑗

𝑛
𝑗=1 (𝑀𝑆𝑇),∑ 𝐸𝑗

𝑛
𝑗=1 (𝑆𝑃𝑇)]}

 
 

 
 

                                                        (𝑆₱1). 

Since the most important function in this problem (S₱1), ∑ 𝐶𝑗
𝑛
𝑗=1 , should be optimal, the following 

easy algorithm produces the best possible outcome. 

Algorithm (𝑺𝑪𝑺𝑬𝑻𝟏) for 1//𝑳𝒆𝒙(∑𝑪𝒋, ∑𝑬𝒋, 𝑻𝒎𝒂𝒙) 𝐩𝐫𝐨𝐛𝐥𝐞𝐦 (𝑺₱𝟏). 

 

ST1: is the Sequencing of jobs according to the SPT rule and the 

computation(∑𝑪𝒋, ∑𝑬𝒋, 𝑻𝒎𝒂𝒙).  

ST2: If there are jobs with equal processing times, then order these 

jobs: (a) using the MST rule and the calculation (∑𝑪𝒋, ∑𝑬𝒋, 𝑻𝒎𝒂𝒙). 

(b) using the EDD rule and the calculation(∑𝑪𝒋, ∑𝑬𝒋, 𝑻𝒎𝒂𝒙). 

ST3: If more than one SPT schedule appeared, then choose the 

schedule with minimum ∑𝑬𝒋 and 𝑻𝒎𝒂𝒙 . 

 

Note: Same as an example (1) for 𝑆₱1. 

 

(2) 1//𝑳𝒆𝒙(∑𝑪𝒋 , 𝑻𝒎𝒂𝒙, ∑𝑬𝒋)(𝑺₱𝟐): This problem is defined as follows: 

  

𝑀𝑖𝑛  {∑𝐸𝑗}                                                   
s. t.                                                                

∑ 𝐶𝑗
𝑛
𝑗=1 = 𝐶∗ where  𝐶∗ = ∑ 𝐶𝑗(𝑆𝑃𝑇) 

𝑛
𝑗=1       

𝑇𝑚𝑎𝑥 ≤ 𝑇, 𝑇 ∈ [𝑇𝑚𝑎𝑥(𝐸𝐷𝐷), 𝑇𝑚𝑎𝑥(𝑆𝑃𝑇)]       }
 

 

                                                              (𝑆₱2). 

The problem (S₱2)with ∑ 𝐶𝑗
𝑛
𝑗=1   is the most important function, it must be optimal, so the easy 

algorithm 𝑺𝑪𝑺𝑬𝑻𝟏 that gives us the best result for (S₱2). 

 

(3) 1//𝑳𝒆𝒙(𝑻𝒎𝒂𝒙, ∑𝑪𝒋, ∑𝑬𝒋)(𝑺₱𝟑): This problem is defined as follows: 

 



IHJPAS. 37 (1) 2024 

391 
 

𝑀𝑖𝑛∑ 𝐸𝑗
𝑛
𝑗=1                                                               

s. t.                                                                          
𝑇𝑚𝑎𝑥 = 𝑇

∗  where  𝑇∗ = 𝑇𝑚𝑎𝑥(𝐸𝐷𝐷)                     
∑ 𝐶𝑗 ≤ 𝐶, 𝐶𝑛
𝑗=1 ∈ [∑ 𝐶𝑗

𝑛
𝑗=1 (𝑆𝑃𝑇),∑ 𝐶𝑗(𝐸𝐷𝐷)] 

𝑛
𝑗=1 }

 

 

                                                                 (S₱3).  

Given that 𝑇𝑚𝑎𝑥 is a more important function in this problem (S₱3) and should be optimal, the 

following algorithm offers the best solution. 

 

Algorithm (𝑺𝑪𝑺𝑬𝑻𝟐) for 1//𝑳𝒆𝒙(𝑻𝒎𝒂𝒙, ∑𝑪𝒋, ∑𝑬𝒋) 𝐩𝐫𝐨𝐛𝐥𝐞𝐦 (𝑺₱𝟑).  

 

ST1: Arrange the jobs according to the rule of EDD and calculate 

𝑻𝒎𝒂𝒙(𝑬𝑫𝑫) =  𝑻
∗. 

ST2: Calculated 𝐷𝑖 = 𝑑𝑖 + 𝑇
∗, for all in 𝑁 𝑤ℎ𝑒𝑟𝑒 𝑁 = {1, … , 𝑛}. 

ST3: Suppose 𝑡 = ∑ 𝑝𝑖𝑖∈𝑁  and 𝐾 equals 𝑛. 

ST4: Finding a job 𝑗 using the Smith backward algorithm and 

satisfying 𝐷𝑗  ≥  𝑡, 𝑝𝑗 ≥ 𝑝𝑖 (Choose the job 𝑗 with the largest due 

date if there is a tie). Assign position 𝐾to job 𝑗.  

ST5: Assign the variables 𝑡 = 𝑡 − 𝑝𝑗 , 𝑁 = 𝑁 − {𝑗} and 𝐾 = 𝐾 − 1; 

if  𝐾 = 1 proceed to step 6; if not, proceed to step 4. 

ST6:  Find 𝑇𝑚𝑎𝑥 , ∑𝐶𝑗  and ∑𝐸𝑗 for the sequence that results. 

 

 

Example (2): Consider the data for the problem 𝑆₱3 in Table 2. 

Table 2. The data of  𝑝𝑗 , 𝑑𝑗 , and  𝑠𝑗 for problem 𝑆₱3 

 Job1 Job2 Job3 Job4 

𝑝𝑗 9 3 7 2 

𝑑𝑗 12 5 9 10 

     

𝑠𝑗  3 2 2 8 

 

Hence the (EDD) schedule (2,3,4,1) gives (𝑇𝑚𝑎𝑥, ∑𝐶𝑗, ∑𝐸𝑗) = (46,2,9). 𝑇𝑚𝑎𝑥(𝐸𝐷𝐷) = 𝑇∗, 𝑡 =

21 , 𝐷𝑖 = 𝑑𝑖 + 𝑇
∗ = (21,14,18,19). The schedule (4,2,3,1) is given by Smith's backward 

algorithm with (𝑇𝑚𝑎𝑥, ∑𝐶𝑗 , ∑𝐸𝑗) = (40,8,9). 

(4) 1//𝑳𝒆𝒙(𝑻𝒎𝒂𝒙, ∑𝑬𝒋, ∑𝑪𝒋)(𝑺₱𝟒):  This problem is defined as follows: 

𝑀𝑖𝑛∑ 𝐶𝑗
𝑛
𝑗=1                                                               

s. t.                                                                           
𝑇𝑚𝑎𝑥 = 𝑇∗   where    𝑇∗ = 𝑇𝑚𝑎𝑥(𝐸𝐷𝐷)                  
∑ 𝐸𝑗 = 𝐸 , 𝐸
𝑛
𝑗=1 ∈ [∑ 𝐸𝑗

𝑛
𝑗=1 (𝑀𝑆𝑇), ∑ 𝐸𝑗(𝐸𝐷𝐷)]

𝑛
𝑗=1 }

 

 

                                                               . . . (𝑆₱4). 

 

Given that 𝑇𝑚𝑎𝑥 is a more important function in this problem S₱4and should be perfect, the 

algorithm 𝑺𝑪𝑺𝑬𝑻𝟐 offers the best solution. 



IHJPAS. 37 (1) 2024 

392 
 

 

(5) 1//𝑳𝒆𝒙(∑𝑬𝒋, ∑𝑪𝒋, 𝑻𝒎𝒂𝒙) (𝑺₱5): This problem is defined as follows: 

 

𝑀𝑖𝑛   {𝑇𝑚𝑎𝑥  }                                                          
s. t.                                                                              

  ∑ 𝐸𝑗 = 𝐸
∗   where 𝐸∗  = ∑ 𝐸𝑗

𝑛
𝑗=1 (𝑀𝑆𝑇)           𝑛

𝑗=1     

∑ 𝐶𝑗
𝑛
𝑗=1 ≤ 𝐶  , 𝐶 ∈ [∑ 𝐶𝑗(𝑆𝑃𝑇)

𝑛
𝑗=1 , ∑ 𝐶𝑗

𝑛
𝑗=1 (𝑀𝑆𝑇)]  }

 
 

 
 

                                                       . . . (𝑆₱5) . 

 

(6) 1//𝑳𝒆𝒙(∑𝑬𝒋, 𝑻𝒎𝒂𝒙, ∑𝑪𝒋)(𝑺₱6): The case can be written as: 

 

𝑀𝑖𝑛  {∑ 𝐶𝑗
𝑛
𝑗=1 }                                           

s. t.                                                                     
 ∑ 𝐸𝑗
𝑛
𝑗=1 = 𝐸∗  where   𝐸∗ = 𝑚𝑖𝑛{∑ 𝐸𝑗

𝑛
𝑗=1 (𝑀𝑆𝑇)}   

𝑇𝑚𝑎𝑥 ≤ 𝑇 , 𝑇 ∈ [𝑇𝑚𝑎𝑥(𝑀𝑆𝑇), 𝑇𝑚𝑎𝑥(𝐸𝐷𝐷)]              }
 
 

 
 

                                                            . . . (𝑆₱6). 

 

Given that 1// ∑𝐸𝑗 is an NP-hard problem, the problems (S₱5) and (S₱6) are both NP-hard. 

(7) 1// ∑𝑪𝒋 + ∑𝑬𝒋 + 𝑻𝒎𝒂𝒙  𝐏𝐫𝐨𝐛𝐥𝐞𝐦. 

The objective of the problem is to find the sequence of job processing that will minimize 

∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥 . Following is a definition of this sub-problem: 

Suppose that α is any machine schedule that is possible to formulate as follows for a given schedule 

𝛼 = (𝛼1, 𝛼2, … , 𝛼𝑛). Assume that α is any schedule that can be expressed as follows for a certain 

schedule 𝛼 = (𝛼1, 𝛼2, … , 𝛼𝑛): 

𝐹1 = 𝑀𝑖𝑛{∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥}
s. t.                                                 

𝐶1 = 𝑝𝛼1                                                   

𝐶𝑗 ≥ 𝑝𝛼𝑗                          𝑗 = 1,2, … . , 𝑛

𝐶𝑗 = 𝐶𝛼(𝑗−1) + 𝑝𝛼𝑗        𝑗 = 2,… . , 𝑛    

𝑇𝑗 ≥ 𝐶𝑗 − 𝑑𝛼𝑗                𝑗 = 1,2, … . , 𝑛

𝐸𝑗 ≥ 𝑑𝛼𝑗 − 𝐶𝑗               𝑗 = 1,2, … . , 𝑛

𝑇𝑗 ≥ 0, 𝐸𝑗 ≥ 0             𝑗 = 1,2, … . , 𝑛 }
 
 
 
 

 
 
 
 

                                                                                           …(S₱7). 

Finding a processing order 𝛼 = (𝛼1, … , 𝛼𝑛) for the jobs on a single machine that minimizes the 

sum of the total completion times, the total earliness, and the maximum tardiness 

(∑𝐶𝑗(𝛼) + ∑𝐸𝑗(𝛼) + 𝑇𝑚𝑎𝑥(𝛼)) , 𝛼 ∈ 𝒮 (where 𝒮 is the set of all feasible solutions), is the aim of 

this problem. 

Proposition(2): The optimal solution for 1// ∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥  problem is an EFSO for the 1// 

𝐹(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥). 

Proof: let 𝛽 be an optimal schedule for 1// ∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥 problem. Suppose that 𝛽 gives no 

efficient solution for the problem 1// 𝐹(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥), so there is a schedule α which is efficient 

for 1// 𝐹(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) problem such that: 

∑𝐶𝑗 (𝛼) ≤ ∑𝐶𝑗(𝛽) and ∑𝐸𝑗 (𝛼) ≤ ∑𝐸𝑗(𝛽)  and 𝑇𝑚𝑎𝑥(𝛼) ≤ 𝑇𝑚𝑎𝑥(𝛽),  

and when there are strict inequities in at least one. As a result, it follows: 



IHJPAS. 37 (1) 2024 

393 
 

∑𝐶𝑗 (𝛼) + ∑𝐸𝑗 (𝛼) + 𝑇𝑚𝑎𝑥(𝛼) ≤ ∑𝐶𝑗(𝛽) + ∑𝐸𝑗(𝛽) + 𝑇𝑚𝑎𝑥(𝛽), so, for1// ∑𝐶𝑗 + ∑𝐸𝑗 +

𝑇𝑚𝑎𝑥 , 𝛼 is a schedule that gives the better solution from 𝛽. However, since 𝛽is the optimal 

schedule, the assumption is contradicted, so 𝛽 should give an efficient solution to 1// ∑𝐶𝑗 +

 ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥 .   

4. Special cases of the problems (𝑺𝑪𝑺𝑬𝑻)and (𝑺₱𝟕) 

In this part, give some special cases and examples for problems (𝑺𝑪𝑺𝑬𝑻)and (𝑺₱𝟕) that lead to 

efficient and optimal solutions respectively. 

4.1 Special Cases of the Problem(𝑺𝑪𝑺𝑬𝑻) 

Case(𝟒. 𝟏. 𝟏): If  𝑝1 = 𝑑1and 𝑝𝑗 = 𝑑𝑗 − 𝑑𝑗−1, for all 𝑗 in 𝛼 (except 1) then SPT schedule 𝛼  

gives an efficient schedule for problem (𝑆𝐶𝑆𝐸𝑇). 

Proof: Since 𝑝1 = 𝑑1 and 𝑝2 = 𝑑2 − 𝑑1 = 𝑑2 − 𝑝1, then  𝐶1 = 𝑑1 and 𝐶2 = 𝑝1 + 𝑝2 = 𝑝1 +

𝑑2 − 𝑝1 = 𝑑2 then 𝐶2 = 𝑑2 and so on 𝐶𝑗 = 𝑑𝑗  for 𝑗 = 1,2, . . , 𝑛. Since 𝐶𝑗 = 𝑑𝑗  for all 𝑗 in 𝜎  

hence 𝐿𝑗 = 0 , ∀𝑗, then 𝐸𝑗 = 𝑇𝑗 = 0, so ∑𝐸𝑗 = 𝑇𝑚𝑎𝑥 = 0. 

Then the problem 1 // (∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) reduced to1 // ∑𝐶𝑗. 

But the rule that solved this problem was SPT. 

Then 𝛼 provides an efficient solution to (𝑆𝐶𝑆𝐸𝑇) problem . 

 

Case(𝟒. 𝟏. 𝟐): If 𝑝𝑗 = 𝑝 and 𝑑𝑗 = 𝑗𝑝 for all 𝑗 in the schedule σ,then 𝜎 gives an EFSO to 

(𝑆𝐶𝑆𝐸𝑇). 

Proof: Since 𝑑𝑗 = 𝑗𝑝 = 𝐶𝑗 ∀𝑗 ∈ 𝜎, (this means there is no job late and early s. t. 𝐸𝑗 = 0 = 𝑇𝑗) 

then ∑ 𝐸𝑗 = 𝑇𝑚𝑎𝑥 = 0𝑛
𝑗=1 . Then the problem 1// 𝐹(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) reduced to 1// ∑ 𝐶𝑗

𝑛
𝑗=1  . 

Now since 𝑝𝑗 = 𝑝 for every job 𝑗 in α, then ∑ 𝐶𝑗
𝑛
𝑗=1 = 𝑝 (

𝑛2+𝑛

2
). But 𝑝 (

𝑛2+𝑛

2
) is constant, hence 

any schedule gives an EFSO to (𝑆𝐶𝑆𝐸𝑇). 

As a result, every schedule provides an efficient solution to the problem.  

 

Case (𝟒. 𝟏. 𝟑): If 𝑑𝑗 = 𝑘𝑝𝑗 for all 𝑘 ≥ 2 and 𝑗 ∈ α = SPT schedule then 𝛼 is an EFSO to the 

(𝑆𝐶𝑆𝐸𝑇). 

proof: Let 𝑠𝑗 = 𝑑𝑗 − 𝑝𝑗 be the slack time of the job j (𝑗 = 1,… , 𝑛) since 𝑑𝑗 = 𝑘𝑝𝑗  then 𝑠𝑗 =

𝑘𝑝𝑗 − 𝑝𝑗 = (𝑘 − 1)𝑝𝑗. Since SPT schedule, the processing time for tasks is arranged in a non-

descending sequence (this meam 𝑝𝑖 ≤ 𝑝𝑗  for all 𝑖 ≤ 𝑗). Then (𝑘 − 1)𝑝1 ≤ (𝑘 − 1)𝑝2 ≤ ⋯ ≤

(𝑘 − 1)𝑝𝑛, hence 𝑠1 ≤ 𝑠2 ≤ ⋯ ≤ 𝑠𝑛. which is MST order, since MST order gives EFSO for 

∑𝐸𝑗. Hence SPT is efficient for (𝑆𝐶𝑆𝐸𝑇).  

Case(𝟒. 𝟏. 𝟒): If SPT and MST are identical then they give an efficient schedule for (𝑆𝐶𝑆𝐸𝑇).  

Proof: Since SPT and MST are identical then ∑ 𝐶𝑗
𝑛
𝑗=1  is minimum value, and ∑𝐸𝑗   is minimum 

value. But 𝑠𝑗 = 𝑑𝑗 − 𝑝𝑗 and 𝑑1 − 𝑝1 ≤. . . ≤ 𝑑𝑛 − 𝑝𝑛 then 𝑑1 − 𝑝1 + 𝑝1 ≤. . . ≤ 𝑑𝑛 − 𝑝𝑛 + 𝑝𝑛 

(since 𝑝1 ≤ ⋯ ≤ 𝑝𝑛), hence 𝑑1 ≤. . . ≤ 𝑑𝑛(which is EDD order), since the EDD order gives EFSO 

for the 𝑇𝑗 then  𝑇𝑚𝑎𝑥 is minimum. Hence all schedule an EFSO for (𝑆𝐶𝑆𝐸𝑇) .  

Case(𝟒. 𝟏. 𝟓): If the processing times of all jobs are identical, then MST ordered is EFSO to 

problem (𝑆𝐶𝑆𝐸𝑇). 



IHJPAS. 37 (1) 2024 

394 
 

Proof: Since the processing times of all jobs are identical, then ∑𝐶𝑗 = 𝑝 (
𝑛(𝑛+1)

2
), it is the same 

for any sequence. Since MST schedule, ordered the slack time of jobs in a non-decreasing sequence 

(that mean 𝑠𝑖 ≤ 𝑠𝑗  for all 𝑖 ≤ 𝑗 in MST  schedule). Since 𝑠𝑗 = 𝑑𝑗 − 𝑝, using MST rule and adding 

𝑝 for each term, is produced  𝑑𝑖 ≤ 𝑑𝑗  for all 𝑖 ≤ 𝑗 (which is EDD order), hence EDD and MST are 

identical. Since MST order gives efficient value for ∑𝐸𝑗 and EDD order gives efficient value for 

the 𝑇𝑗 then  𝑇𝑚𝑎𝑥 is minimum. Hence MST is an EFSO for the third criterion ∑𝐶𝑗, ∑𝐸𝑗, 𝑇𝑚𝑎𝑥 . 

 

Case(𝟒. 𝟏. 𝟔): If 𝑑𝑗 = 𝑑, and SPT and MST are identical ∀𝑗, (𝑗 = 1,2, . . . , 𝑛) in a schedule  α, 

then 𝛼 is EFSO to ( 𝑆𝐶𝑆𝐸𝑇 ). 

Proof: Since 𝑑𝑗 = 𝑑 , there are two cases:  

a) If 𝑑𝑗 = 𝑑 = 𝑝𝑗, hence 𝐶𝑗 ≥ 𝑑𝑗 for all 𝑗 (this means all jobs are late s. t. 𝐸𝑗 = 0 =

∑𝐸𝑗  for all 𝑗). Then 1// (∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) reduce to 1// (∑𝐶𝑗, 𝑇𝑚𝑎𝑥), as result, the SPT 

rule provides an EFSO to the problem ( 𝑆𝐶𝑆𝐸𝑇 ).where 𝑑𝑗 = 𝑑 for all the orders of  𝑗 and 

SPT gives EFSO for 1// ∑𝐶𝑗. 

b) 𝑑𝑗 = 𝑑 > 𝑝𝑗  for all 𝑗 hence either 𝑑 ≤ 𝐶𝑗  or 𝐶𝑗 > 𝑑, since SPT and MST are identical (this 

mean ∑𝐶𝑗 , ∑𝐸𝑗  is minimum values). Then a schedule 𝛼 is an EFSO to ( 𝑆𝐶𝑆𝐸𝑇 ). 

 

Case (𝟒. 𝟏. 𝟕): if 𝑝𝑗 = 𝑝, 𝑑𝑗 = 𝑑 and  𝑑 ≤ 𝐶𝑗  for all 𝑗 in a schedule α  then any schedule 𝛼 is 

EFSO to ( 𝑆𝐶𝑆𝐸𝑇 ).  

Proof: Since 𝑑 ≤ 𝐶𝑗 for all 𝑗 (this means all jobs are late s. t. 𝐸𝑗 = 0 = ∑𝐸𝑗  ) and 𝑇𝑗 =

𝑚𝑎𝑥{𝐿𝑗 , 0} = 𝑚𝑎𝑥{𝑗𝑝 − 𝑑, 0} then 𝑇𝑚𝑎𝑥 = 𝑚𝑎𝑥{𝑚𝑎𝑥{𝑗𝑝 − 𝑑, 0}} = 𝑛𝑝 − 𝑑. Hence 1 ∕∕

(∑𝐶𝑗 , ∑ 𝐸𝑗 , 𝑇𝑚𝑎𝑥) reduced to 1// (∑𝐶𝑗 , 𝑇𝑚𝑎𝑥) = (𝑝 (
𝑛2+𝑛

2
) , 𝑛𝑝 − 𝑑). Then any schedule is an 

EFSO to (𝑆𝐶𝑆𝐸𝑇) because the three quantities are constant.  

Case(𝟒. 𝟏. 𝟖): If 𝑑𝛼𝑖 + 𝑝𝛼𝑗 ≤ 𝑑𝛼𝑗  for all 𝑖, 𝑗 in 𝑆𝑃𝑇 schedule  𝛼 , where 𝑖 ≤ 𝑗, SPT and EDD 

are identical, then 𝛼 is the EFSO for (𝑆𝐶𝑆𝐸𝑇). 

Proof: Since 𝑑𝛼𝑖 + 𝑝𝛼𝑗 ≤ 𝑑𝛼𝑗   ∀𝑖, 𝑗 in 𝛼, then 𝑑𝛼𝑖 ≤ 𝑑𝛼𝑗 − 𝑝𝛼𝑗   for all 𝑖, 𝑗 and 𝑑𝛼𝑖 − 𝑝𝛼𝑖 ≤ 𝑑𝛼𝑗 −

𝑝𝛼𝑗  , for all 𝑖, 𝑗 (Since 𝑝𝛼𝑖 ≥ 0 and 𝑝𝛼𝑖 ≤ 𝑝𝛼𝑗 ).Then s𝛼𝑖 ≤ s𝛼𝑗  , for all 𝑖, 𝑗 (this mean all jobs are 

ordered in MST order for all 𝑖, 𝑗 in 𝛼), then ∑𝐸𝑗 is minimum. Hence SPT gives the optimal solution 

for both criteria ∑𝐸𝑗 𝑎𝑛𝑑 ∑𝐶𝑗, and 𝑇𝑚𝑎𝑥(SPT) =  𝑇𝑚𝑎𝑥(𝐸𝐷𝐷) (since SPT and EDD are identical). 

Then SPT is an EFSO for the problem (𝑆𝐶𝑆𝐸𝑇) . 

 

Case(𝟒. 𝟏. 𝟗): If 𝑑𝑗 + 𝑝𝑗 ≤ 𝐶𝑗+1 for 𝑗 = 1,2, . . , 𝑛 − 1 then the SPT schedule is an EFSO for 

(𝑆𝐶𝑆𝐸𝑇) . 

Proof: Let 𝜎 = (𝜎1, 𝜎2, . . , 𝜎𝑛) by SPT sequence, since 𝑑𝑗 + 𝑝𝑗 ≤ 𝐶𝑗+1  , ∀𝑗(𝑗 = 1,2, . . , 𝑛 − 1). 

Then 𝑑𝑗 ≤ 𝐶𝑗+1 − 𝑝𝑗 = ∑ 𝑝𝑖
𝑗+1
𝑖=1 − 𝑝𝑗 = 𝐶𝑗 + 𝑝𝑗+1 − 𝑝𝑗  ∀𝑗(𝑗 = 1,2, . . , 𝑛 − 1). 

𝐶𝑗 + 𝑝𝑗+1 − 𝑝𝑗 =  {
𝐶𝑗       if 𝑝𝑗 = 𝑝𝑗+1          , 𝑗 = 1,2, . . , 𝑛 − 1

𝐶𝑗 + 𝑝 if 𝑝 = 𝑝𝑗+1 − 𝑝𝑗 , 𝑗 = 1,2, . . , 𝑛 − 1
}                                      (1) 

Since 𝜎 is the SPT schedule, there are two cases: 



IHJPAS. 37 (1) 2024 

395 
 

a) 𝑝𝑗 = 𝑝𝑗+1, for 𝑗 = 1,2, . . , 𝑛 − 1 and Equation (1).  Hence 𝑑𝑗 ≤ 𝐶𝑗  (this means all jobs are 

late s. t. 𝐸𝑗 = 0 = ∑𝐸𝑗). The problem 1 ∕∕ (∑𝐶𝑗 , ∑ 𝐸𝑗 , 𝑇𝑚𝑎𝑥) reduced to 1// (∑𝐶𝑗 , 𝑇𝑚𝑎𝑥), 

so SPT schedule is an EFSO . 

b) 𝑝𝑗 < 𝑝𝑗+1, for 𝑗 = 1,2, . . , 𝑛 − 1 and by (4.1),then 𝑑𝑗 ≤ 𝐶𝑗 + 𝑝, 𝑝 > 0 then 𝑑𝑗 − 𝐶𝑗 ≤ 𝑝 

(this means all jobs are late 𝑠. 𝑡. 𝐸𝑗 = 0 = ∑𝐸𝑗), hence 1 ∕∕ (∑𝐶𝑗 , ∑ 𝐸𝑗 , 𝑇𝑚𝑎𝑥)reduced  to 

1// (∑𝐶𝑗 , 𝑇𝑚𝑎𝑥), also SPT rule is an EFSO . 

Case(𝟒. 𝟏. 𝟏𝟎): If 𝐶𝑗 ≥ 𝑑𝑗  and SPT, EDD rules are identical  for all 𝑗 in a schedule 𝛼, then 𝛼 

schedule gives an EFSO for (𝑆𝐶𝑆𝐸𝑇).  

Proof: Let σ be an SPT schedule with 𝐶𝑗 ≥ 𝑑𝛼𝑗 for each 𝑗 in 𝜎 (this means that all jobs in the SPT 

schedule are late), hence 𝐸𝑗 = 0 = ∑𝐸𝑗  for all 𝑗 in 𝛼. then 1//  𝐹(∑𝐶𝑗 , ∑ 𝐸𝑗 , 𝑇𝑚𝑎𝑥) reduced to 

1//(∑𝐶𝑗 , 𝑇𝑚𝑎𝑥).Hence SPT schedule is efficient for (𝑆𝐶𝑆𝐸𝑇) . 

 

Case(4.1.11):  If the SPT schedule gives 𝐶𝑗 ≤ 𝑑𝑗 ∀𝑖 ∈ 𝑁 then this SPT schedule gives an EFSO 

for (𝑆𝐶𝑆𝐸𝑇). 

Proof: Since 𝐶𝑗 ≤ 𝑑𝑗 for all 𝑗 in the SPT schedule (this means all jobs are early s. t. 𝑇𝑗 = 0 =

𝑇𝑚𝑎𝑥 for all 𝑗) and 𝐸𝑗 = 𝑚𝑎𝑥{−𝐿𝑗 , 0} then ∑𝐸𝑗 = ∑𝑚𝑎𝑥{−𝐿𝑗 , 0} for all 𝑗. Hence 1//

 𝐹(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥) reduced to 1// (∑𝐶𝑗, ∑ 𝐸𝑗). Hence SPT rule gives an EFSO. 

4.2 Special Cases for Subproblem (S₱7)   

We introduce some special cases for the problem (S₱7)that has optimal solutions in this section. 

Case(4.2.1): If  𝑝1 = 𝑑1and 𝑝𝑗 = 𝑑𝑗 − 𝑑𝑗−1, for all 𝑗 in 𝛼 (except 1) then SPT schedule 𝛼  gives 

an optimal solution for the problem 1// ∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥.  

Proof: Proof as in case (4.1.1) and (∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥)=∑𝐶𝑗.  

Case(4.2.2): If 𝑝𝑗 = 𝑝 and 𝑑𝑗 = 𝑗𝑝 for all 𝑗 in the schedule σ, then 𝜎 gives an optimal solution for 

the problem 1// (∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥). 

Proof: Verified by the case (4.1.2), hence  (∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥) = ∑ 𝐶𝑗
𝓃
𝑗=1 = 𝑝 (

𝑛2+𝑛

2
) . 

Case (4.2.3): If 𝑑𝑗 = 𝑘𝑝𝑗 for all 𝑘 ≥ 2 then the SPT schedule is an optimal solution for the 

problem (S₱7). 

Proof: Proof as in case (4.1.3).  

Case (4.2.4): If SPT and MST are identical then they give an optimal schedule for the problem 

(S₱7).  

Proof: Proof as in case (4.1.4).  

Case (4.2.5): If 𝑝𝑗 = 𝑝 ∀𝑗 ∈ 𝑁, then the EDD schedule is an optimal schedule for (S₱7). 

Proof: Proof as in case (4.1.5).  

 

Case(4.2.6): If 𝑑𝑗 = 𝑑, and  SPT and MST  are identical ∀𝑗, (𝑗 = 1,2, … , 𝑛) in schedule 𝛼 then 

the 𝛼 gives an optimal value for (S₱7). 

Proof: Proof as in case (4.1.6), and 



IHJPAS. 37 (1) 2024 

396 
 

∑ 𝐶𝑗
𝑛
𝑗=1 + ∑ 𝐸𝑗

𝑛
𝑗=1 + 𝑇𝑚𝑎𝑥 =

{
∑ 𝐶𝑗
𝑛
𝑗=1 + 𝑇𝑚𝑎𝑥,                                                      , if 𝑑 = 𝑝𝑗(𝑖. 𝑒. , 𝐶𝑗 ≥ 𝑑𝑗 = 𝑑)                        

∑ 𝐶𝑗
𝑛
𝑗=1 + ∑ 𝐸𝑗

𝑛
𝑗=1 + 𝑇𝑚𝑎𝑥 = ∑ 𝑑𝑛

𝑗=1 + 𝑇𝑚𝑎𝑥, if 𝑑 > 𝑝𝑗  then either 𝐶𝑗 ≥ 𝑑𝑗  or 𝐶𝑗 < 𝑑𝑗   
. 

 

Case (4.2.7): Any schedule gives an optimal solution for the problem S₱7 if  𝑝𝑗 = 𝑝, 𝑑𝑗 =

𝑑 and  𝑑 ≤ 𝐶𝑗  ∀𝑗(𝑗 = 1,2, … . , 𝑛).  

 

Proof: Proof as in case (4.1.7), and (∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥) = 𝑝 (
𝑛2+𝑛

2
) + 𝑛𝑝 − 𝑑 . 

If 𝑑𝛼𝑖 + 𝑝𝛼𝑗 ≤ 𝑑𝛼𝑗  for all 𝑖, 𝑗 in schedule 𝑆𝑃𝑇 𝛼 , where 𝑖 ≤ 𝑗 and SPT and EDD are identical, 

then 𝛼 is the EFSO for (𝑆𝐶𝑆𝐸𝑇). 

Case (4.2.8): If 𝑑𝛼𝑖 + 𝑝𝛼𝑗 ≤ 𝑑𝛼𝑗  for all 𝑖, 𝑗 in schedule 𝑆𝑃𝑇 𝛼 , where 𝑖 ≤ 𝑗 , SPT and EDD are 

identical, then 𝛼 is the optimal solution for  (S₱7). 

Proof: Proof as in case (4.1.8).  

 

Case (4.2.9): If 𝑑𝑗 + 𝑝𝑗 ≤ 𝐶𝑗+1 for 𝑗 = 1,2, . . , 𝑛 − 1 then the SPT schedule is an optimal solution 

for (𝑆₱7). 

Proof: Verified by the case (4.1.9).  

 

Case (4.2.10): If 𝐶𝑗 ≥ 𝑑𝑗 , SPT and EDD rules are identical  for all 𝑗 in a schedule 𝛼, then schedule 

𝛼 gives an optmal solution for(𝑆₱7). 

Proof: Verified by the case (4.1.10).            

 

Case (4.2.11): If the SPT schedule gives 𝐶𝑗 ≤ 𝑑𝑗 ∀𝑖 ∈ 𝑁 then this SPT schedule gives an optimal 

schedule  for (𝑆₱7). 

Proof: Proof as in case (4.1.11).  

 

In Table 3, an examples give for describing the special cases for two problems ( 𝑆𝐶𝑆𝐸𝑇 ) and 

(𝑆₱7) by calculating the objective functions(𝐹)and (𝐹1)respectively, using 6 jobs. 

 

 

 

 

 

 

 

 

 

 

 

 

 



IHJPAS. 37 (1) 2024 

397 
 

Table 3. Special Cases of Problem ( 𝑆𝐶𝑆𝐸𝑇 ) and (𝑆₱7) In the following examples. 

5. Dominance Rules  for Single Machine Scheduling Problem  

          Dominance Rules (DRs) are used efficiently in reducing the current sequences[23-25]. DR 

is used usually to indicate whether a certain node in a BAB method can be eliminated before 

calculating its lower bound. These rules are been useful when a node has a lower bound less than 

the optimum solution and can be eliminated [26-28]. When the nodes are dominated by others in 

the BAB procedure, DRs can be used also to cut these nodes. Such developments may heavily 

reduce the number of nodes in searching for an efficient solution. Where the DRs are also 

applicable to such problems[29,30]. 

 The dominance rules as we mentioned before are used in an attempt to eliminate nodes in the BAB 

method which makes us reduce the time spent on solving this problem1// ∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥  . 

Rule (1): 

If  𝑝𝑖 ≤ 𝑝𝑗 and 𝑑𝑖 ≤ 𝑑𝑗 then there is an optimal schedule wherein the job 𝑖 processing before job  

. 

Proof: Consider a schedule 𝜎 = 𝜎1𝑖𝑗𝜎2  and a schedule  �̇� = 𝜎1𝑗𝑖𝜎2 see Figure (1) 

 

Figure1.  The scheduling 𝜎 and�̈� 

𝐹1 𝐹 conditions 𝒑𝒋 𝐚𝐧𝐝 𝒅𝒋 case 

57 (57,0,0) 𝑝1 = 𝑑1and 𝑝𝑗 = 𝑑𝑗 − 𝑑𝑗−1 for all 𝑗  𝑝𝑗 = 1,2,4,7,5,3 , 𝑑𝑗 =

1,3,10,22,22,15,6   

(4.1.1) 

(4.2.1) 

126 (126,0,0)  𝑝𝑗 = 𝑝 and 𝑑𝑗 = 𝑗𝑝 , ∀𝑗  𝑝𝑗 = 6, 𝑑𝑗 = 6,12,18,24,30,36  (4.1.2) 

(4.2.2) 

94 (78,12,4) 𝑑𝑗 = 𝑘𝑝𝑗  for all 𝑘 ≥ 2  𝑝𝑗 = 3,4,2,5,6,8 , 𝑑𝑗 =

9,12,6,15,18,24  

(4.1.3) 

(42.3) 

267 (222,2,43) 𝑝𝑖 ≤ 𝑝𝑗  and 𝑠𝑖 ≤ 𝑠𝑗 for all  𝑗 . 𝑝𝑗 = 6,10,12,14,14,18 , 𝑠𝑗 =

2,4,8,10,12,13. 

(4.1.4) 

(4.2.4) 

72 (63,0,9) 𝑝𝑗 = 𝑝 for all 𝑗 in a schedule EDD 𝛼 . 𝑝𝑗 = 3 , 𝑑𝑗 = 3,4,6,7,8,9  (4.1.5) 

(4.2.5) 

62 (41,11,10) 𝑑𝑗 = 𝑑,∀𝑗  𝑝𝑗 = 5,4,3,2,1,1 , 𝑑𝑗 = 6  (4.1.6) 

(4.2.6) 123 (106,0,17) 𝑝𝑗 = 7,6,5,3,2,1 , 𝑑𝑗 = 7  

130 (105,0,25) 𝑝𝑗 = 𝑝 , 𝑑𝑗 = 𝑑, 𝑑 ≤ 𝐶𝑗for all 𝑗  

 

𝑝 = 𝑑 = 5  (4.1.7) 

(4.2.7) 130 (105,2,23) 𝑝 = 5, 𝑑 = 7 , 𝑝 < 𝑑    

34 (34,0,0) 𝑑𝑖 + 𝑝𝑗 ≤ 𝑑𝑗   for all 𝑗 ,  SPT and 

EDD  rules are identical. 

𝑝𝑗 = 1,1,3,3,2,2 , 𝑑𝑗 = 1,2,9,12,4,6    (4.1.8) 

(4.2.8) 

73 (59,0,14) 𝑑𝑗 + 𝑝𝑗 ≤ 𝐶𝑗+1 for all 𝑗 = 2,3, … , 𝑛   𝑝𝑗 = 5,4,3,2,4,2 , 𝑑𝑗 = 6,7,4,3,5,2  (4.1.9) 

(4.2.9) 

39 

126 

(35,0,4) 

(101,0,25) 

𝐶𝑗 ≥ 𝑑𝑗  , for all 𝑗  𝑝𝑗 = 4,3,2,2,1,1 , 𝑑𝑗 = 14,9,5,6,2,3  

𝑝𝑗 = 3,4,5,6,8,9 , 𝑑𝑗 = 3,5,6,7,9,10   

(4.1.10) 

(4.2.10) 

83 (78,5,0) 𝐶𝑗 ≤ 𝑑𝑗  , for all 𝑗  𝑝𝑗 = 8,5,2,6,4,3, 𝑑𝑗 = 30,14,2,21,10,6  (4.1.11) 

(4.2.11) 



IHJPAS. 37 (1) 2024 

398 
 

 

which is obtained by interchanging the jobs i and j in σ. For these schedules, we study two cases, 

and in every case, we will make a comparison between them. 

First case: If 𝑝𝑖 ≤ 𝑝𝑗  , 𝑑𝑖 ≤ 𝑑𝑗  produces that 𝑠𝑖 ≤ 𝑠𝑗  

In this situation, there are: 

The condition of the processing times ensures that: 

∑𝐶𝒦(𝜎) ≤ ∑𝐶𝒦(�̇�)                                                                                                                                 (2)  

And the condition of the slack times ensures that:    

𝐸𝑚𝑎𝑥(𝜎) ≤ 𝐸𝑚𝑎𝑥(�̇�) then  ∑𝐸𝒦(𝜎) ≤ ∑𝐸𝒦(�̇�)  

And the condition on the due date ensures that: 

𝑇𝑚𝑎𝑥(𝜎) ≤ 𝑇𝑚𝑎𝑥(�̇�)                                                                                                                                 (3)  

Hence ∑𝐶𝒦(𝜎) + ∑𝐸𝒦(𝜎) + 𝑇𝑚𝑎𝑥(𝜎) ≤ ∑𝐶𝒦(�̇�) + ∑𝐸𝒦(�̇�) + 𝑇𝑚𝑎𝑥(�̇�)    

Second case: If 𝑝𝑖 ≤ 𝑝𝑗  , 𝑑𝑖 ≤ 𝑑𝑗  yields that 𝑠𝑖 ≥ 𝑠𝑗 .  

In this situation,  The condition on the processing times ensures that (5.1) is satisfied, and the cost 

which is obtained from Equation (2) is equal to 𝑝𝑗 − 𝑝𝑖  

i. e. ∑𝐶𝒦(�̇�) = ∑𝐶𝒦(𝜎) + 𝑝𝑗 − 𝑝𝑖                                                                                                         (4)  

, then 𝑑𝑖 − 𝐶𝑖(𝜎) = 𝑑𝑖 − 𝐶𝑗(�̇�) + 𝑝𝑗 − 𝑝𝑖, since 𝐶𝑖(𝜎) = 𝐶𝑗(�̇�) − 𝑝𝑗 + 𝑝𝑖 . 

since 𝑠𝑖 = 𝑑𝑖 − 𝑝𝑖 ≥ 𝑠𝑗 = 𝑑𝑗 − 𝑝𝑗  then 𝑑𝑖 − 𝑝𝑖 − 𝐶𝑗(�̇�) ≥ 𝑑𝑗 − 𝑝𝑗 − 𝐶𝑗(�̇�) hence 𝑑𝑖 − 𝑝𝑖 +

𝑝𝑗 − 𝐶𝑗(�̇�) ≥ 𝑑𝑗 − 𝒞𝑗(�̇�)  

, from which we deduce that 𝐸𝑚𝑎𝑥(𝜎) ≥ 𝐸𝑚𝑎𝑥(�̇�) then ∑𝐸𝒦(𝜎) ≥ ∑𝐸𝒦(�̇�) the addition in cost 

which is obtained from this inequality is equal to 𝑠𝑖 − 𝑠𝑗, i.e., 

∑𝐸𝒦(𝜎) = ∑𝐸𝒦(�̇�) + (𝑠𝑖 − 𝑠𝑗)                                                                                                         (5).  

Since 𝑝𝑖 ≤ 𝑝𝑗 then 𝑝𝑗 − 𝑝𝑖 ≥ 0       ∀𝑖, 𝑗                                                                                    

Since 𝑑𝑖 ≤ 𝑑𝑗  then 𝑑𝑗 − 𝑑𝑖 ≥ 0       ∀𝑖, 𝑗                                                                                     

From 𝑠𝑖 − 𝑠𝑗 ≤ 𝑝𝑗 − 𝑝𝑖 , then  ∑𝐸𝒦(�̇�) + (𝑠𝑖 − 𝑠𝑗) ≤ ∑𝐸𝒦(�̇�) + 𝑝𝑗 − 𝑝𝑖 .  

 (by adding ∑𝐸𝑘(�̇�) for both sides)  by Equation (5) 

Then  ∑𝐶𝒦(𝜎) + ∑𝐸𝒦(𝜎) ≤ ∑𝐶𝒦(𝜎) + 𝑝𝑗 − 𝑝𝑖 + ∑𝐸𝒦(�̇�) . 

 From Equation (3) 

 ∑𝐶𝒦(𝜎) + ∑𝐸𝒦(𝜎) ≤ ∑𝐶𝒦(�̇�) + ∑𝐸𝒦(�̇�)(by adding 𝑇𝑚𝑎𝑥   for both sides) .  

And  ∑𝐶𝒦(𝜎) + ∑𝐸𝒦(𝜎) + 𝑇𝑚𝑎𝑥(𝜎) ≤ ∑𝐶𝒦(�̇�) + ∑𝐸𝒦(�̇�) + 𝑇𝑚𝑎𝑥(�̇�) . 

 

Rule (2): 

The schedule σij  is dominated by the schedule σji if the following inequalities hold: 

(1) 𝑝𝑖 ≤ 𝑝𝑗  (2) 𝑑𝑗 ≤ 𝑑𝑖 (3) 𝑑𝑗 ≥ 𝑠𝑖. 

Proof: Consider a schedule 𝜎 = 𝜎1𝑖𝑗𝜎2  and a schedule  �̇� = 𝜎1𝑗𝑖𝜎2  

 

which is obtained by interchanging the jobs i and j in σ. The condition of the processing times 

ensures that (∑C𝒦(σ) ≤ ∑C𝒦(σ̇)                                                                                                    

 is satisfied and then the addition in cost is obtained by  

( ∑𝐶𝒦(�̇�) = ∑𝐶𝒦(𝜎) + 𝑝𝑗 − 𝑝𝑖                                                                                                     (6) 

Since 𝐶𝑖(𝜎) = 𝐶𝑗(�̇�) − 𝑝𝑗 + 𝑝𝑖 then 𝑑𝑖 − 𝐶𝑖(𝜎) = 𝑑𝑖 − 𝐶𝑗(�̇�) + 𝑝𝑗 − 𝑝𝑖.The condition (1), (2) 

implies, since 𝑠𝑖 ≥ 𝑠𝑗 then 𝑑𝑖 − 𝑝𝑖 − 𝐶𝑗(�̇�) ≥ 𝑑𝑗 − 𝑝𝑗 − 𝐶𝑗(�̇�) hence 𝑑𝑖 − 𝑝𝑖 + 𝑝𝑗 − 𝐶𝑗(�̇�) ≥

𝑑𝑗 − 𝐶𝑗(�̇�) from which we deduce that 𝐸𝑚𝑎𝑥(𝜎) ≥ 𝐸𝑚𝑎𝑥(�̇�) then ∑𝐸𝒦(𝜎) ≥ ∑𝐸𝒦(�̇�). 



IHJPAS. 37 (1) 2024 

399 
 

Then the addition in cost from this inequality is obtained from  

 ( ∑𝐸(𝜎) = ∑𝐸𝒦(�̇�) + (𝑠𝑖 − 𝑠𝑗)                                                                                                     

𝑑𝑖 ≥ 𝑑𝑗  and 𝑝𝑗 ≥ 𝑝𝑖 this mean 𝑝𝑗 − 𝑝𝑖 ≥ 0, hence 𝑑𝑖 − 𝑑𝑗 + 𝑝𝑗 − 𝑝𝑖 ≥ 𝑝𝑗 − 𝑝𝑖, and    

𝑠𝑖 − 𝑠𝑗 ≥ 𝑝𝑗 − 𝑝𝑖. Then ∑𝐸𝑘(�̇�) + (𝑠𝑖 − 𝑠𝑗) ≥ ∑𝐸𝒦(�̇�) + 𝑝𝑗 − 𝑝𝑖, (by adding ∑E𝒦(σ̇) for both 

sides). 

from ( ∑𝐸𝒦(𝜎) = ∑𝐸𝒦(�̇�) + (𝑠𝑖 − 𝑠𝑗)                                                                          

and then ∑𝐶𝒦(𝜎) + ∑𝐸𝒦(𝜎) ≥ ∑𝐶𝒦(𝜎) + 𝑝𝑗 − 𝑝𝑖 + ∑𝐸𝒦(�̇�), (by adding ∑𝐶𝑘(𝜎) for both 

sides). 

From Equation (6) there is ∑𝐶𝒦(𝜎) + ∑𝐸𝒦(𝜎) ≤ ∑𝐶𝒦(�̇�) + ∑𝐸𝒦(�̇�) (by adding 𝑇𝑚𝑎𝑥 for both 

sides), finally ∑𝐶𝒦(𝜎) + ∑𝐸𝒦(𝜎) + 𝑇𝑚𝑎𝑥(𝜎) ≤ ∑𝐶𝑘(�̇�) + ∑𝐸𝒦(�̇�) + 𝑇(�̇�) . 

 

Example (3): Let’s use MSP with 5 jobs and processing time and due date as the following table: 

Table 4. The data of  𝑝𝑗 , 𝑑𝑗 , and  𝑠𝑗 for problem (𝑆𝐶𝑆𝐸𝑇) 

 

 

 

 

 

 

When using the Rule (1) we obtain the DRs mentioned in Figure (3). 

 

 

   

                                                                                                

 

 

 

 

Figure (3): The DRs of the example (3). 

 

From Rule (1) there are (6) DRs, as can see: 12, 1 3,14, 16, 2 6, 42, 4 3, 4 

6,53. in Table 5, contain (7) likely sequences some /all are subject to the aforementioned DRs. 

The adjacency matrix 𝐴 is as followings: 

 

𝐴(𝐺) =

[
 
 
 
 
0 1 1 1 𝑎15
0 0 𝑎23 0 𝑎25
0 𝑎32 0 0 0
0 1 1 0 𝑎45
𝑎51 𝑎52 1 𝑎54 0 ]

 
 
 
 

 . where 𝑎𝑗𝑖 = {
1, if 𝑎𝑖𝑗 = 0    

0, if 𝑎𝑖𝑗 = 1     
. 

 

 

 

 

 

 

 1 2 3 4 5 

𝑝𝑗 1 8 10 4 9 

𝑑𝑗 14 28 27 23 12 

𝑠𝑗 13 20 17 19 3 

1 4 

5 

2 

3 



IHJPAS. 37 (1) 2024 

400 
 

Table 5. The efficient sequences for  example  (3) under DR 

 EF-SQ ( 𝑺𝑪𝑺𝑬𝑻 ) 𝑺₱𝟕 

Seq. POS1 POS 2 POS 3 POS 4 POS 5 (∑𝑪𝒋, ∑𝑬𝒋, 𝑻𝒎𝒂𝒙) ∑𝑪𝒋 + ∑𝑬𝒋 + 𝑻𝒎𝒂𝒙 

1 1 4 2 5 3 (73,46,10) 129 

2 1 4 5 2 3 (74,37,5) 116 

3 1 4 5 3 2 (76,34,4) 114 

4 1 5 4 2 3 (79,30,5) 114 

5 1 5 4 3 2 (81,27,5) 113 

6 5 1 4 2 3 (87,22,4) 114 

7 5 1 4 3 2 (89,19,4) 112 

Where EF-SQ =efficient sequence, POS = position 

The sequences (1–7) provide the problem ( 𝑆𝐶𝑆𝐸𝑇 ) an effective value and the sequence (7) an 

optimal value for the problem (S₱7), as can be shown in Table 5. 

 

 

6. Conclusions  

In this study, a mathematical model was created to address the research problems 

1//𝐹(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥), 1// ∑𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥. Discovered a straightforward algorithm for the 

efficient schedule for sub-problems for 1//𝐹(∑𝐶𝑗 , ∑ 𝐸𝑗 , 𝑇𝑚𝑎𝑥) and it was proven that some rules 

give efficient (optimal) solutions to these problems ( 𝑆𝐶𝑆𝐸𝑇 )and(S₱7), finding and proving some 

special cases that find some efficient (optimal) solutions suitable for the problems 

( 𝑆𝐶𝑆𝐸𝑇 )and(S₱7). This paper has proved the efficacy of rules SPT and EDD and demonstrated 

the significance of the Dominance Rule (DR) that can be used in this problem to improve efficient 

solutions. 

In the future, it would be interesting to conduct a study on the following machine scheduling 

problems (MSPs). 

1) 1/𝑟𝑗/ 𝐹(∑𝐶𝑗 , ∑𝐸𝑗 , 𝑇𝑚𝑎𝑥). 

2) 1/𝑟𝑗/ ∑ 𝐶𝑗 + ∑𝐸𝑗 + 𝑇𝑚𝑎𝑥 . 

3) 1/𝑆𝑓/ 𝐹(∑𝐶𝑗 , ∑ 𝐸𝑗 , 𝑇𝑚𝑎𝑥). 

 

Acknowledgment 

The authors are greatly appreciated the referees for their valuable comments and suggestions for 

improving the paper 

Conflict of Interest  

The authors declare that they have no conflicts of interest. 

Funding 

There is no financial support in preparation for the publication. 

 

References 

1. WASSENHOVE, L.N.V. Single Machine Scheduling to Minimize Total Late Work. Oper. Res. 1992, 

40, 586–595. https://doi:10.1287/opre.40.3.586. 

2. Tanaev, V.; Gordon, W.; Shafransky, Y. M. Scheduling theory. Single-stage systems. Springer Science 

and Business Media. 2012.  

3. Hoogeveen, H. Multicriteria Scheduling. Eur. J. Oper. Res. 2005, 167, 592–623. 

https://doi:10.1016/j.ejor.2004.07.011. 

https://doi:10.1287/opre.40.3.586
https://doi:10.1016/j.ejor.2004.07.011


IHJPAS. 37 (1) 2024 

401 
 

4. Zaidan, A.A.; Atiya, B.; Abu Bakar, M.R.; Zaidan, B. B. A new hybrid algorithm of simulated 

annealing and simplex downhill for solving multiple-objective aggregate production planning on fuzzy 

environment. Neural Comput & Applic, 2019, 31, 1823–1834. 

 https://doi.org/10.1007/s00521-017-3159-5 

5. Chachan, H. A., ; Jaafar, H. A. Exact Solutions for Minimizing cost Function with Five Criteria and 

Release Dates on Single Machine. Ibn AL-Haitham Journal For Pure and Applied Sciences, 2020. 

33(3), 140–157. https://doi.org/10.30526/33.3.2479 

6. Ali, Z.M.; Abdul Razaq, T.S. Minimizing The Total Completion Times, The Total Tardinessand The 

Maximum Tardiness. 2015, 28, 155–170. 

7. Ahmed, M.G.; Ali, F.H. Exact Method with Dominance Rules for Solving Scheduling on a Single 

Machine Problem with Mult iobjective Function. Al-Mustansiriyah J. Sci. 2022, 33, 56–63. 

https://doi:10.23851/mjs.v33i2.1091. 

8. Ali, F.H.; Ahmed, M.G. Local Search Methods for Solving Total Completion Times, Range of Lateness 

and Maximum Tardiness Problem. Proc. 6th Int. Eng. Conf. Sustainable Technol. Dev. IEC 2020, 103–

108. https://doi:10.1109/IEC49899.2020.9122821. 

9. Hassan, D.A.; Mehdavi-Amiri, N.; Ramadan, A.M. A Heuristic Approach to Minimize Three Criteria 

Using Efficient Solutions. Indones. J. Electr. Eng. Comput. Sci. 2022, 6, 334–341. 

https://doi:10.11591/ijeecs.v26.i1.pp334-341. 

10. Abdullah, H. F. Multicriteria Scheduling Problems to Minimize Total Tardiness Subject to Maximum 

Earliness or Tardiness. Ibn AL-Haitham Journal For Pure and Applied Sciences, 2017, 23(1), 311–

320. https://jih.uobaghdad.edu.iq/index.php/j/article/view/988 

11. Smith, W.E. Various Optimizers for Single-Stage Production. Nav. Res. Logist. Q. 1956, 3, 59–66, 

https://doi:10.1002/nav.3800030106 

12. Abdul-Razaq, T.S.; Akram, A.O. Local Search Algorithms for Multi-Criteria Single Machine 

Scheduling Problem. Ibn AL-Haitham J. Pure Appl. Sci. 2018, 436–

451.https://doi:10.30526/2017.ihsciconf.1817. 

13. Hoogeveen, J.A. Minimizing Maximum Promptness and Maximum Lateness on a Single Machine. 

Math. Oper. Res. 1996, 21, 100–114, https://doi:10.1287/moor.21.1.100. 

14. Jawad, A.A.; Ali, F.H.; Hasanain, W.S. Using Heuristic and Branch and Bound Methods to Solve a 

Multi-Criteria Machine Scheduling Problem. Iraqi J. Sci. 2020, 61, 2055–2069. 

https://doi:10.24996/ijs.2020.61.8.21 

15. Abdul-Zahra, I.; Abbas, I. T.; Kalaf, B. A.; Bakar, R. A.; June, L. W., ; Monsi, M. B. . The Role of 

Dynamic Programming in the Distribution of Investment Allocations between Production Lines with 

an Application. International Journal of Pure and Applied Mathematics, 2016, 106(2), 365-380. 

16. Atiya, B.; Bakheet, A. J. K.; Abbas, I. T.; Bakar, M. R. A.; Soon, L. L., ; Monsi, M. B. Application of 

simulated annealing to solve multi-objectives for aggregate production planning. AIP Conference 

Proceedings (2016, June). 1739(1), 020086). AIP Publishing LLC.  https://doi.org/10.1063/1.4952566 

17. Kalaf, B. A., Mohammed, G. J.;  Salman, M. D. A New Hybrid Meta-Heuristics Algorithms to Solve 

APP Problems. In Journal of Physics: Conference Series (2021, May). 1897(1), 012011). IOP 

Publishing. 

18. Allahverdi, A.;Ng, C. T.; Cheng, T. E.; Kovalyov, M. Y. A survey of scheduling problems with setup 

times or costs, European Journal of Operational Research, 2008. 187(3), 985–1032. 

https://doi.org/10.1016/j.ejor.2006.06.060. 

19. Allaoua, H.; Brahim, B. New Properties for Solving the Single-Machine Scheduling Problem with 

Early/Tardy Jobs, Journal of Intelligent Systems, 2017, 26(3), 531–543. https://doi.org/10.1515/jisys-

2016-0063. 

20. Jawad, A.A.; Ali, F.H. ; Hasanain, W.S. .Using heuristic and branch and bound methods to solve a 

multi-criteria machine scheduling problem, Iraqi Journal of Science, 2020,  61(8), 2055–2069. 

https://doi.org/10.24996/ijs.2020.61.8.21 

https://doi.org/10.1007/s00521-017-3159-5
https://doi.org/10.30526/33.3.2479
https://doi:10.23851/mjs.v33i2.1091
https://doi:10.1109/IEC49899.2020.9122821
https://doi:10.11591/ijeecs.v26.i1.pp334-341
https://jih.uobaghdad.edu.iq/index.php/j/article/view/988
https://doi:10.1002/nav.3800030106
https://doi:10.30526/2017.ihsciconf.1817
https://doi:10.1287/moor.21.1.100
https://doi:10.24996/ijs.2020.61.8.21
https://doi.org/10.1063/1.4952566
https://doi.org/10.1016/j.ejor.2006.06.060
https://doi.org/10.1515/jisys-2016-0063
https://doi.org/10.1515/jisys-2016-0063
https://doi.org/10.24996/ijs.2020.61.8.21


IHJPAS. 37 (1) 2024 

402 
 

21. Mahnam, M.; Moslehi, G.; Fatemi Ghomi, S.M.T. Single machine scheduling with unequal release 

times and idle insert for minimizing the sum of maximum earliness and tardiness, Mathematical and 

Computer Modelling, 2013, 57(9–10), 2549–2563 https://doi.org/10.1016/j.mcm.2013.01.007. 

22. Mosheiov, G.; Oron, D. ; Shabtay, D. Minimizing total late work on a single machine with generalized 

due-dates, European Journal of Operational Research, 2021, 293(3), 837–846. 

https://doi.org/10.1016/j.ejor.2020.12.061. 

23. Neamah, N. M.; Kalaf, B. A. Solving the multi-criteria: Total completion time, total late work, and 

maximum earliness problem. Periodicals of Engineering and Natural Sciences, 2023. 11(3), 46-57. 

24. Centinkaya, M.; Ozyurek, C., The Effect of Inquiry-Based Science Activities on Prospective Science 

Teachers’ Scientific Process Skills, International Online Journal of Education and Teaching, . 2019, 

6(1), 56–70. 

25. Chachan, H.A. Solving Machine Scheduling Problem Using Particle Swarm Optimization Method, The 

Iraqi Magazine For Administrative Sciences, 2012, 8(33), 197–213. 

26. Abid, H. ; Mohammed, A. Scheduling job families with setups on a single machine, Journal of Kerbala 

University, 2012, 10(2), 99–113. 

27. Adel D., Search method for solving multicriteria scheduling problem,  2022,  13(March 2021), 1709–

1720. 

28. Ahmadov, Y. ; Helo, P., A cloud based job sequencing with sequence-dependent setup for sheet metal 

manufacturing’, Annals of Operations Research, 2018,  270(1–2),5–24. 

https://doi.org/10.1007/s10479-016-2304-3. 

29. Ahmed, M. ; Ali, F. Efficient Algorithms to Solve Tricriteria Machine Scheduling Problem. Journal of 

Al-Rafidain University College For Sciences, 2020, (1), 485-493. 

30. Ahmed, M.G. and Ali, F.H. Exact Method with Dominance Rules for Solving Scheduling on a Single 

Machine Problem with Multi objective Function’, Al-Mustansiriyah Journal of Science, 2022, 33(2), 

56–63. Available at: https://doi.org/10.23851/mjs.v33i2.1091. 

 

https://doi.org/10.1016/j.mcm.2013.01.007
https://doi.org/10.1016/j.ejor.2020.12.061
https://doi.org/10.1007/s10479-016-2304-3