# Nature-Inspired Metaheuristics for Two-Agent Scheduling with Due Date and Release Time

Authors: Hongwei Li; Yuvraj Gajpal; Chirag Surti; Dongliang Cai; Amit Kumar Bhardwaj
Journal: Complexity
 (2020)

---

## Abstract

This paper delves into a two-agent scheduling problem in which two agents are competing for a single resource. Each agent has a set of jobs to be processed by a single machine. The processing time, release time, weight, and the due dates of each job are known in advance. Both agents have their objectives, which are conflicting in nature. The first agent tries to minimize the total completion time, while the second agent tries to minimize the number of tardy jobs. The two agents’ scheduling problem, an NP-hard problem, has a wide variety of applications ranging from the manufacturing industry to the cloud computing service provider. Due to the wide applicability, each variation of the problem requires a different algorithm, adapted according to the user’s requirements. This paper provides mathematical models, heuristic algorithms, and two nature-based metaheuristic algorithms to solve the problem. The algorithm’s performance was gauged against the optimal solution obtained from the AMPL-CPLEX solver for both solution quality and computational time. The outlined metaheuristics produce a solution that is comparable with a short computational time. The proposed metaheuristics even have a better solution than the CPLEX solver for medium-size problems, whereas the computation times are much less than the CPLEX solvers.


---

## Body

## 1. Introduction

The scheduling problems have always been an intriguing topic for scholars because of their wide range of applications. The academic community has extensively explored scheduling problems as they are extensively utilized in manufacturing and service industries to optimize resource allocation. Often, scheduling is a critical process as it influences the productivity of an organization. The scheduling problem has a wide range of applications in different industries and different environments. For example, in the engineering discipline, the scheduling problem is used for disassembly sequence to maximize revenue (Feng et al. [1]; Feng et al. [2]), for scheduling multicluster tools for wafer fabrication in the process industry (Zhu et al. [3]). The machine-scheduling problem is mainly motivated by the manufacturing industry. The usual scheduling problem involves finding a sequence of jobs in a machine, flow of jobs through different machines, or assigning jobs to different machines.The machine-scheduling problem involves the allocation of resources to process different jobs under different machine settings such as single-machine setting [4], flowshop machine setting [5], job shop machine setting [6], and parallel machine setting [7]. The classical machine-scheduling involves the processing of different jobs for a single customer/agent. When the jobs belong to different customers, the resultant scheduling problem is a multiagent scheduling problem.The research on the multiagent scheduling models started approximately fourteen years ago. An application of multiple agents scheduling problem can be encountered in many industries such as aircraft landing problem [8], railroad track allowance problem [9], networks [10], and cloud computing services [7]. Two-agent scheduling problem is a special case of a multiagent scheduling problem.Agnetis et al. [11] and Baker and Smith [4] started a new branch in scheduling problems in which two agents use the same resource for processing jobs. Each agent has its objective function to be optimized. Two-agent scheduling problems can have the special challenge of optimizing two different objective functions belonging to two different agents. Two measures were proposed by Suresh and Chaudhuri [12]. The first measure assigns a weight to each agent’s objective function to convert the multiobjective problem to a single objective problem. The second measure minimizes the first agent’s objective function but tries to keep the objective function of the second agent under some predefined limit. Cheng et al. [13] named these two types of multiagent scheduling problems as the “minimality model” and “feasibility model,” respectively. In this paper, we follow the second research direction and study the feasibility model, where the objective function of the first agent is minimized, and the objective function of the second agent is kept under some limit. This paper aims to provide a mathematical formulation of the model and develop a metaheuristic to find a good quality solution.Although many two-agent scheduling models have been studied in recent years, the studies related to the release date-related two-agent scheduling model are relatively limited [14]. The number of tardy jobs minimization is aimed at only a few papers. Informed about the two-agent scheduling with due date literature, we consider a series of two-agent scheduling problems with due date-related objective in this paper. We have defined the single-machine-scheduling problems with unequal job release date constraints to minimize the total completion time, the total weighted completion time, and the number of tardy job objectives.We have considered the scheduling problems of a two-agent single machine which is donated as1|∑UB≤Q,r|∑wACA (Problem 1), 1|∑UB≤Q,r|∑CA (Problem 2), 1∑UB≤Q∑wACA (Problem 3), and 1∑UB≤Q∑CA (Problem 4) with the following assumptions, where A and B represent two agents in the problem:(i)
The jobs from the two agents have a real release time(ii)
The jobs from agentA have positive weight(iii)
The jobs from agentB have a positive due date for all four problems(iv)
The job will not be released until the shared machine fully processes it(v)
The jobs from the two agents have a nonzero processing time(vi)
Preemption is not allowedThe paper contributes to the scheduling literature in many ways. In our knowledge, this paper first time develops algorithms to solve the two-agent scheduling problem to minimize the weighted completion and number of tardy job objectives. A mathematical model based on MILP formulation is developed to find the optimal solution for the problem. Also, this paper investigates two nature-based metaheuristics to solve the problem. The novel features of the proposed metaheuristics are the hybridization of the algorithm with local search schemes. The proposed local search scheme not only improves the solution quality but also obtains a feasible solution.The remainder of the paper is organized as follows. Section2 investigates the single machine-scheduling literature. Section 3 addresses the problem definition associated with the mathematical model. Section 4 introduces the proposed ant colony optimization (i.e., ACO) and intelligent water drop (IWD) algorithm. Section 5 provides the numerical experiment results, related analysis, and a comparison of the proposed ACO algorithm with the optimal solution generated by the AMPL software. Section 6 outlines the conclusion and suggests future research directions.


## 2. Literature Review

Since the publication of Baker and Cole Smith [4] and Agnetis et al. [11], many scholars have explored a two-agent single-machine-scheduling problem. Two-agent scheduling problem considers two agents in which each agent has a set of jobs for processing in a single-machine. Generally speaking, the research of a single-machine and two-agent scheduling models could be classified into two main categories. The first category is called a minimality model, and the second category is called a feasibility model. Each research area has further research directions that can be classified based on their features. These features include different objective functions of each agent, release date, weight, the nature of processing time, due date, and among other constraints.


### 2.1. Two-Agent Scheduling Problem with the Number of Tardy Job Objectives

Agnetis et al. [11] investigated three due date criteria based on two-agent scheduling models to minimize the number of tardy jobs. These problems are denoted by 1∑UjB≤Q∑UiA (P1), 1∑UjB≤Q∑CiA (P2), and 1∑UjB≤Q∑wiACiA (P3). They have proven the computational complexity of the problems mentioned above. The first problem could be solved in On3 time while the complexity of the second problem is proved to be a binary NP-hard. The complexity of the second problem is still unknown. Ng et al. [15] provided many lemmas for1∑UjB≤Q∑CiA problem: the scheduling of all A-type jobs is done in the shortest processing time (SPT) rule and the scheduling of all B-type jobs is done in the earliest due date first rule (EDD) following an optimal schedule. Furthermore, they developed a pseudopolynomial-time algorithm to solve the problem of searching for an optimal solution. Ng et al. [15] studied the complexity of several two-agent scheduling problems to minimize tardy jobs. They also pointed out that the problem is strongly NP-hard if the upper bound is equal to zero.Leung et al. [16] referred the Agnetics et al.’s [11] work and proved the complexity of a two-agent scheduling problem to minimize the total tardiness objective of the first agent while limiting the total number of tardy jobs of the second agent within a prespecified upper limit (i.e., 1∑UjB≤Q∑TjA) is binary NP-hard. Lee et al. [17] extend Ng et al.’s [15] problem (i.e., 1∑UjB=0∑wiACiA), considering an actual processing time approach. They proposed a branch-and-bound algorithm and heuristics to solve the problem. Yin et al. [18] studied the single-machine two-agent scheduling problem with release times and due date for minimizing the number of tardy jobs of first agent while keeping the maximum lateness of the jobs of the other agent within prespecified value. Yuan [19] studied the multiagent scheduling problem to minimize the weighted number of tardy jobs from each agent. Yin et al. [20] studied the two-agent scheduling problem for determining the due dates. The literature studies other variants of the two-agent scheduling problem. However, they differ from the problem considered in this paper in terms of either objective function (Wan et al. [21]; Mor and Mosheiov [22]) or machine settings (Mor and Mosheiov [23]; Lei [24]; Yu et al. [25]). A literature survey by Li et al. [26] and Yin et al. [27] can be referred to find different variants of the two-agent scheduling problem with due date-related objectives.The articles by Cheng et al. [14]; Yin et al. [28]; and Chen et al. [29] are closely related to the problem considered in our paper. Cheng et al. [14] considered the two-agent scheduling problem with total weighted completion time and number of tardy jobs minimization. Although Cheng et al. [14] used the same objective functions considered in this paper, they followed the minimality model and minimized the two objective functions’ weighted sum. Yin et al. [28] proposed a two-agent scheduling model for unrelated parallel machine-scheduling problem to minimize the number of total completion time and the number of tardy jobs criteria. They proposed a column generation method embedded with branch-and-price algorithms to find the optimal solution. The complexity of the problem considered in this paper is proved to be NP-hard by Chen et al. [29]. Their research work was based on proving the complexity, and they did not provide an algorithm to solve the problem. Motivated by Chen et al.’s [29] complexity, this paper proposes a mixed linear integer programming (MILP) formulation and a metaheuristic algorithm to solve the problem.


### 2.2. Nature-Inspired Algorithm

This paper uses two nature-inspired algorithms to solve the problem under consideration. The foraging behavior of real ants inspires the ACO while the flow of water drops inspires the IWD. Nature-inspired algorithms have been used to solve a wide variety of scheduling problems. Feng et al. [1] used ACO to solve the disassembly problem for CNC machine tools. Decision-making involves finding the sequence of disassembly operations to maximize demand satisfaction and minimize disassembly cost simultaneously. Zhang et al. [30] used ACO for cross docks operations in which decision-making involves finding the assignment of receiving and shipping doors. Jia et al. [31] used a bee colony algorithm to solve bike repositioning in bike-sharing systems in which decision-making involves finding the routes of the repositioning vehicles and the number of parked bikes of the corresponding station. Yagmahan and Yenisey [5] used ACO to solve the flowshop scheduling problem for finding a sequence of jobs. Li et al. [32] used an ant colony algorithm to solve two agents’ scheduling problems to minimize total weighted completion time and makespan objectives. Hosseini [33] implements the IWD algorithm to solve the traveling salesman problem. Alijla et al. [34] used IWD to solve three combinatorial optimization problems; (1) rough set for subset feature selection (RSFS), (2) multiple knapsack problem (MKP), and (3) traveling salesman problem (TSP). The successful application of algorithms inspired by natural phenomena to solve different problems motivated us to use them to solve the two agents’ scheduling problems considered in this paper.


## 2.1. Two-Agent Scheduling Problem with the Number of Tardy Job Objectives

Agnetis et al. [11] investigated three due date criteria based on two-agent scheduling models to minimize the number of tardy jobs. These problems are denoted by 1∑UjB≤Q∑UiA (P1), 1∑UjB≤Q∑CiA (P2), and 1∑UjB≤Q∑wiACiA (P3). They have proven the computational complexity of the problems mentioned above. The first problem could be solved in On3 time while the complexity of the second problem is proved to be a binary NP-hard. The complexity of the second problem is still unknown. Ng et al. [15] provided many lemmas for1∑UjB≤Q∑CiA problem: the scheduling of all A-type jobs is done in the shortest processing time (SPT) rule and the scheduling of all B-type jobs is done in the earliest due date first rule (EDD) following an optimal schedule. Furthermore, they developed a pseudopolynomial-time algorithm to solve the problem of searching for an optimal solution. Ng et al. [15] studied the complexity of several two-agent scheduling problems to minimize tardy jobs. They also pointed out that the problem is strongly NP-hard if the upper bound is equal to zero.Leung et al. [16] referred the Agnetics et al.’s [11] work and proved the complexity of a two-agent scheduling problem to minimize the total tardiness objective of the first agent while limiting the total number of tardy jobs of the second agent within a prespecified upper limit (i.e., 1∑UjB≤Q∑TjA) is binary NP-hard. Lee et al. [17] extend Ng et al.’s [15] problem (i.e., 1∑UjB=0∑wiACiA), considering an actual processing time approach. They proposed a branch-and-bound algorithm and heuristics to solve the problem. Yin et al. [18] studied the single-machine two-agent scheduling problem with release times and due date for minimizing the number of tardy jobs of first agent while keeping the maximum lateness of the jobs of the other agent within prespecified value. Yuan [19] studied the multiagent scheduling problem to minimize the weighted number of tardy jobs from each agent. Yin et al. [20] studied the two-agent scheduling problem for determining the due dates. The literature studies other variants of the two-agent scheduling problem. However, they differ from the problem considered in this paper in terms of either objective function (Wan et al. [21]; Mor and Mosheiov [22]) or machine settings (Mor and Mosheiov [23]; Lei [24]; Yu et al. [25]). A literature survey by Li et al. [26] and Yin et al. [27] can be referred to find different variants of the two-agent scheduling problem with due date-related objectives.The articles by Cheng et al. [14]; Yin et al. [28]; and Chen et al. [29] are closely related to the problem considered in our paper. Cheng et al. [14] considered the two-agent scheduling problem with total weighted completion time and number of tardy jobs minimization. Although Cheng et al. [14] used the same objective functions considered in this paper, they followed the minimality model and minimized the two objective functions’ weighted sum. Yin et al. [28] proposed a two-agent scheduling model for unrelated parallel machine-scheduling problem to minimize the number of total completion time and the number of tardy jobs criteria. They proposed a column generation method embedded with branch-and-price algorithms to find the optimal solution. The complexity of the problem considered in this paper is proved to be NP-hard by Chen et al. [29]. Their research work was based on proving the complexity, and they did not provide an algorithm to solve the problem. Motivated by Chen et al.’s [29] complexity, this paper proposes a mixed linear integer programming (MILP) formulation and a metaheuristic algorithm to solve the problem.


## 2.2. Nature-Inspired Algorithm

This paper uses two nature-inspired algorithms to solve the problem under consideration. The foraging behavior of real ants inspires the ACO while the flow of water drops inspires the IWD. Nature-inspired algorithms have been used to solve a wide variety of scheduling problems. Feng et al. [1] used ACO to solve the disassembly problem for CNC machine tools. Decision-making involves finding the sequence of disassembly operations to maximize demand satisfaction and minimize disassembly cost simultaneously. Zhang et al. [30] used ACO for cross docks operations in which decision-making involves finding the assignment of receiving and shipping doors. Jia et al. [31] used a bee colony algorithm to solve bike repositioning in bike-sharing systems in which decision-making involves finding the routes of the repositioning vehicles and the number of parked bikes of the corresponding station. Yagmahan and Yenisey [5] used ACO to solve the flowshop scheduling problem for finding a sequence of jobs. Li et al. [32] used an ant colony algorithm to solve two agents’ scheduling problems to minimize total weighted completion time and makespan objectives. Hosseini [33] implements the IWD algorithm to solve the traveling salesman problem. Alijla et al. [34] used IWD to solve three combinatorial optimization problems; (1) rough set for subset feature selection (RSFS), (2) multiple knapsack problem (MKP), and (3) traveling salesman problem (TSP). The successful application of algorithms inspired by natural phenomena to solve different problems motivated us to use them to solve the two agents’ scheduling problems considered in this paper.


## 3. Problem Definition and Notation

This section first describes the terminologies and notations used in this paper and then provides the linear programming formulation for the problem.


### 3.1. Problem Definition

In all four problems, we consider that we haven number of jobs from agent A and agent B that are to be scheduled at a single machine. Each of the A and the B jobs has a positive processing time and a positive release time. Additionally, A-type jobs also have a positive weight, and B-type jobs have a positive due date. The problems involve assigning jobs to the shared machine and then finding sequence for the assigned job so that the total weighted completion time or total completion time of A-type jobs is as minimum as possible while limiting the number of tardy jobs of B-type jobs within a prespecified limit. We use the following notations to describe and formulate the problems:X: set of agents, X = {A, B}nx: the number of jobs for the agent x∈Xn: total number of jobs, n=nA+nBN: set of all n jobs, N=1,2,3,…,nNB: set of B-type jobs, consisting of nB jobs, NB=nA+1,nA+2,…,n.JX: job set of the agent x∈Xpix: the processing time of ith job for the agent x∈Xrix: release date of ith job for the agent x∈Xwix: weight of ith job for the agent x∈Xδix: the density of ith job for the agent x∈X, δix=wix/pixdix: due date of ith job for the agent x∈XCix: completion time of ith job for the agent x∈Xσ: ordered set of jobs already scheduledfxσ for a given sequence σ, the value of the objective function for the agent x∈XQ: the upper bound, a constant number.bigM: a large numberIn this paper, we consider four problems, denoted as follows:Problem 1:1∑m=1nBUmB≤Q,r∑l=1nAwlAClAProblem 2:1∑m=1nBUmB≤Q,r∑l=1nAClAProblem 3:1∑m=1nBUmB≤Q∑l=1nAwlAClAProblem 4:1∑m=1nBUmB≤Q∑l=1nAClAProblem 1 is a single-machine two-agent scheduling problem. This problem minimizes the total weighted completion time of A-type jobs subjected to an upper bound on the total number of tardy B-type jobs. It also has arbitrary release dates and arbitrary weights. Problem 2 minimizes the total completion time of A-type of jobs. Problem 3 and Problem 4 have the same objective functions as Problem 1 and Problem 2, respectively, but they do not consider release date. Problem 3 focuses on finding such a schedule that minimizes the total weighted completion time of A-type jobs and/or ensures that the maximum number of tardy B-type jobs does not exceed the upper boundQ. Problem 4 is an unweighted case of Problem 3. The objective of Problem 4 is to minimize the total completion time of A-type jobs.


### 3.2. NP-Hardness

Agnetis et al. [11] have proved that the problems 1fmaxB≤Q∑wjACjA and 1∑UjB≤Q∑wjACjA are binary NP-hard. They also reported that problem 1∑UjB≤Q∑CjA is still open. Therefore, Problem 1 is also NP-hard. Recently, Chen et al. [29] proved that problem 1∑m=1nBUmB≤Q∑l=1nAwlAClA is NP-hard.


### 3.3. The General Mathematical Model of Problems

All four problems considered in this paper can be formulated in a common mathematical model. Problem 2 is an unweighted case of Problem 1. By putting weights of all jobs into one, Problem 1 is thereby reduced to Problem 2. By placing all jobs’ release dates to zero, Problem 3 and Problem 4 can be reduced from Problem 1 and Problem 2, respectively. As a result, we can formulate a general mathematical model for all four problems.We use the following decision variables to formulate the problem:Xij: a binary variable for assigning job i at position j, i,j∈1,nYj: a binary variable for starting job at position j just after completion of the job at position j − 1, j∈1,nUi: a binary variable for tardy B-type jobs, i∈nA+1,nCTi1: completion time of job i∈1,nCTi2: completion time of job at position j, j∈1,nSTj: starting time of job at position j, j∈1,nThe mixed-integer linear programming (MILP) formulation for the problem can be described as follows:(1)minimizeZ=∑i=1nACTi1×wiA,subject to(2)∑j=1nXij=1;∀i∈N,(3)∑i=1nXij=1;∀j∈N,(4)CT12=∑i=1nXi1×ri+pi;(5)CTj2=STj+∑i=1nXi1×pi;∀j∈Nj≥2,(6)STj≥CTj−12,∀j∈N,(7)STj≥∑i=1nXij×ri,∀j∈Nj≥2,(8)STj≤CTj−12+bigM×1−Yj;∀j∈Nj≥2,(9)STj≤∑i=1nXij×ri+bigM×Yj;∀j∈Nj≥2,(10)CTi1≥CTj2−bigM×1−Xij;∀i,j∈N,(11)CTi1≤CTj2+bigM×1−Xij;∀i,j∈N,(12)CTi1≤di+bigM×Ui;∀i∈NB,(13)∑i=1NBUi≤Q;(14)CTi1≥0;∀i∈N,(15)CTj2≥0;∀j∈N,(16)STj≥0;∀j∈N.Equation (1) represents the minimization of the objective function of agent A. Constraint (2) and (3) make sure that every job is assigned to only one position of the machine. The completion time of the job at position j will be calculated using constraint (4) and constraint (5). In case a job is scheduled at the first position in the sequence, then constraint (4) is used to calculate the first job’s completion time, while constraint (5) is used to calculate the rest of the jobs’ completion times. Constraints (6)–(9) are used to determine jobs’ starting time. Constraint (6) ensures that any job will not be scheduled at any position before the previous job is completed. Constraint (7) states that any job will not be scheduled at any position before its release date. Constraints (8) and (9) ensure that the job’s starting time is the same as the previous job’s completion time. Constraint (10) and (11) calculates the completion time of job i. These constraints also ensure that the job i is scheduled at position j then Ci1=Cj2. Constraint (12) is used to determine that if the processing of the job i is finished after its due date, then the job is marked as a tardy. Constraint (13) confirms that the total number of tardy B-type jobs is within the prespecified upper bound Q.


## 3.1. Problem Definition

In all four problems, we consider that we haven number of jobs from agent A and agent B that are to be scheduled at a single machine. Each of the A and the B jobs has a positive processing time and a positive release time. Additionally, A-type jobs also have a positive weight, and B-type jobs have a positive due date. The problems involve assigning jobs to the shared machine and then finding sequence for the assigned job so that the total weighted completion time or total completion time of A-type jobs is as minimum as possible while limiting the number of tardy jobs of B-type jobs within a prespecified limit. We use the following notations to describe and formulate the problems:X: set of agents, X = {A, B}nx: the number of jobs for the agent x∈Xn: total number of jobs, n=nA+nBN: set of all n jobs, N=1,2,3,…,nNB: set of B-type jobs, consisting of nB jobs, NB=nA+1,nA+2,…,n.JX: job set of the agent x∈Xpix: the processing time of ith job for the agent x∈Xrix: release date of ith job for the agent x∈Xwix: weight of ith job for the agent x∈Xδix: the density of ith job for the agent x∈X, δix=wix/pixdix: due date of ith job for the agent x∈XCix: completion time of ith job for the agent x∈Xσ: ordered set of jobs already scheduledfxσ for a given sequence σ, the value of the objective function for the agent x∈XQ: the upper bound, a constant number.bigM: a large numberIn this paper, we consider four problems, denoted as follows:Problem 1:1∑m=1nBUmB≤Q,r∑l=1nAwlAClAProblem 2:1∑m=1nBUmB≤Q,r∑l=1nAClAProblem 3:1∑m=1nBUmB≤Q∑l=1nAwlAClAProblem 4:1∑m=1nBUmB≤Q∑l=1nAClAProblem 1 is a single-machine two-agent scheduling problem. This problem minimizes the total weighted completion time of A-type jobs subjected to an upper bound on the total number of tardy B-type jobs. It also has arbitrary release dates and arbitrary weights. Problem 2 minimizes the total completion time of A-type of jobs. Problem 3 and Problem 4 have the same objective functions as Problem 1 and Problem 2, respectively, but they do not consider release date. Problem 3 focuses on finding such a schedule that minimizes the total weighted completion time of A-type jobs and/or ensures that the maximum number of tardy B-type jobs does not exceed the upper boundQ. Problem 4 is an unweighted case of Problem 3. The objective of Problem 4 is to minimize the total completion time of A-type jobs.


## 3.2. NP-Hardness

Agnetis et al. [11] have proved that the problems 1fmaxB≤Q∑wjACjA and 1∑UjB≤Q∑wjACjA are binary NP-hard. They also reported that problem 1∑UjB≤Q∑CjA is still open. Therefore, Problem 1 is also NP-hard. Recently, Chen et al. [29] proved that problem 1∑m=1nBUmB≤Q∑l=1nAwlAClA is NP-hard.


## 3.3. The General Mathematical Model of Problems

All four problems considered in this paper can be formulated in a common mathematical model. Problem 2 is an unweighted case of Problem 1. By putting weights of all jobs into one, Problem 1 is thereby reduced to Problem 2. By placing all jobs’ release dates to zero, Problem 3 and Problem 4 can be reduced from Problem 1 and Problem 2, respectively. As a result, we can formulate a general mathematical model for all four problems.We use the following decision variables to formulate the problem:Xij: a binary variable for assigning job i at position j, i,j∈1,nYj: a binary variable for starting job at position j just after completion of the job at position j − 1, j∈1,nUi: a binary variable for tardy B-type jobs, i∈nA+1,nCTi1: completion time of job i∈1,nCTi2: completion time of job at position j, j∈1,nSTj: starting time of job at position j, j∈1,nThe mixed-integer linear programming (MILP) formulation for the problem can be described as follows:(1)minimizeZ=∑i=1nACTi1×wiA,subject to(2)∑j=1nXij=1;∀i∈N,(3)∑i=1nXij=1;∀j∈N,(4)CT12=∑i=1nXi1×ri+pi;(5)CTj2=STj+∑i=1nXi1×pi;∀j∈Nj≥2,(6)STj≥CTj−12,∀j∈N,(7)STj≥∑i=1nXij×ri,∀j∈Nj≥2,(8)STj≤CTj−12+bigM×1−Yj;∀j∈Nj≥2,(9)STj≤∑i=1nXij×ri+bigM×Yj;∀j∈Nj≥2,(10)CTi1≥CTj2−bigM×1−Xij;∀i,j∈N,(11)CTi1≤CTj2+bigM×1−Xij;∀i,j∈N,(12)CTi1≤di+bigM×Ui;∀i∈NB,(13)∑i=1NBUi≤Q;(14)CTi1≥0;∀i∈N,(15)CTj2≥0;∀j∈N,(16)STj≥0;∀j∈N.Equation (1) represents the minimization of the objective function of agent A. Constraint (2) and (3) make sure that every job is assigned to only one position of the machine. The completion time of the job at position j will be calculated using constraint (4) and constraint (5). In case a job is scheduled at the first position in the sequence, then constraint (4) is used to calculate the first job’s completion time, while constraint (5) is used to calculate the rest of the jobs’ completion times. Constraints (6)–(9) are used to determine jobs’ starting time. Constraint (6) ensures that any job will not be scheduled at any position before the previous job is completed. Constraint (7) states that any job will not be scheduled at any position before its release date. Constraints (8) and (9) ensure that the job’s starting time is the same as the previous job’s completion time. Constraint (10) and (11) calculates the completion time of job i. These constraints also ensure that the job i is scheduled at position j then Ci1=Cj2. Constraint (12) is used to determine that if the processing of the job i is finished after its due date, then the job is marked as a tardy. Constraint (13) confirms that the total number of tardy B-type jobs is within the prespecified upper bound Q.


## 4. Proposed Algorithms

In a single agent scheduling problem, total weighted completion time is minimized by arranging the jobs in nonincreasing order of density. Simultaneously, the number of tardy jobs is minimized by arranging jobs in nondecreasing order of their due dates. These properties are used in the proposed heuristic.


### 4.1. Heuristic Algorithm

The heuristic first creates partial schedulesσA and σB for A- and B-type of jobs. The jobs in the sequence σA are arranged in nonincreasing order of density δiA. The jobs in the sequence σB are arranged in nonincreasing order of their due dates diB. A complete solution σis then constructed by first sequencing A jobs followed by B jobs. The resultant solution can be infeasible. If the infeasibility is encountered, A jobs are moved towards the end of the sequence to make the solution feasible. The pseudocode of the heuristic is presented below (Algorithm 1).Algorithm 1:Heuristic algorithm.
(1)
/∗ Initial Solution ∗/(2)
Create a partial sequenceσA and σB(3)
Create a solutionσ⟵σA∪σB //combine sequences σA and σB to construct σ(4)
CalculateU⟵fBσ //Calculate the weighted number of tardy job for sequence σ(5)
/∗ Feasibility phase ∗/(6)
fork =  n1 to 1 do(7)
Select jobJ=σk(8)
forl = k+1 to n−k−n1 do(9)
σtemp⟵Create new sequence fromσby reinserting jobJat positionl(10)
Utemp⟵fBσtemp //Calculate the weighted number of tardy job for σtemp(11)
ifUtemp≤Qthen(12)
breakl loop(13)
end if(14)
end for(15)
σ⟵σtemp;U⟵Utemp(16)
ifUtemp≤Q then(17)
breakk loop(18)
end if(19)
end for(20)
return solutionσTo understand the heuristic algorithm, consider an instance with 3 A-type of jobs and 3B jobs. The parameters associated with 6 jobs are provided in Table 1. Consider upper bound Q for the total number of tardy jobs for agent B to be 2.Table 1
A numerical example with 6 jobs.
JobAgentrixpixwixδixdixJ1A31480.57—J2A11280.67—J3A01220.17—J4B36—0.1762J5B012—0.4213J6B216—0.5016The heuristic starts with creating partial sequencesσA=J2−J1−J3 and σB=J5−J6−J4. The initial solution is created by combining these two sequences σ=J2−J1−J3−J5−J6−J4. The start time and completion time of each job for a sequence σare shown in Table 2.Table 2
Completion time of sequenceσ
Sequence (σ)J2J1J3J5J6J4Start time11327395157Completion time132739515763Due date———131662The total weighted completion time of agent A for the sequenceσ is 398 (i.e., U =  13×8+27×8+39×2 = 398. The total number of tardy jobs for agent B for the sequence σ is 3 (i.e., U=3). Since U>Q, the sequence σ is infeasible. Thus, the algorithm calls the feasibility phase for obtaining a feasible solution. When k = 3, job J3 is selected for moving towards the end of the schedule. Job J3 is first reinserted at positions l = 4, to create σtemp=J2−J1−J5−J3−J6−J4 with Utemp=3. Since the number of tardy jobs remains greater than Q, the job is now inserted at position l = 5 and then finally at position l = 6 to create a sequence σtemp=J2−J1−J5−J6−J4−J3. At the end of the l loop, the sequence σis replaced by σtemp to form the sequence σ=J2−J1−J5−J6−J4−J3. When k = 2, job J1 is selected and inserted at positions l = 3, l = 4 and l = 5, and finally sequence σ is updated as σ=J2−J5−J6−J4−J1−J3. When k = 1, job J2 is selected and inserted at position l = 2 to form the sequence σtemp=J5−J2−J6−J4−J1−J3 with Utemp=2. At this time, l loop breaks because the total number of tardy jobs is less than or equal to Q. After the exit of the l loop, the sequence σis replaced by σtemp. Finally, the sequence σ=J5−J2−J6−J4−J1−J3 is reported as the solution of the heuristic algorithm.


### 4.2. Ant Colony Optimization (ACO) Algorithm

Ant colony optimization (ACO) algorithm was designed by [35]. They took their inspiration to develop the algorithm from the foraging behavior of ants. The ants always use the shortest path while seeking food from their nest. The max-min ant system (MMAS) is employed in the proposed algorithm. The fundamental procedures of the proposed ACO algorithm are listed below, followed by a detailed description.Step 1: generate an initial solution using the heuristic algorithm described in Section4.1Step 2: set parameters, trail intensity matrixτip, trail intensities upper bound (τmax) and the trail intensity lower bound (τmin)Step 3: follow the below steps and terminate this step until the condition of termination is not met(i)
Generate solutions using the trail intensities(ii)
Carry out the local search to improve the solution(iii)
Update the trail intensity(iv)
Update the best solution found so farStep 4: report the best solution as a final solution of ACO


#### 4.2.1. Parameter Initialization

The trail intensity is denoted byτip, where τip depicts the trail intensity of the scheduling job i in the position p. In this paper, the initial trail intensity is set τip=1/1−ρ×IniObj. Here, IniObj represents the objective function value of the initial solution. The index ρ indicates the trail persistence.In this paper, we take the max-min ant system (MMAS) into consideration. The MMAS is an improvement plan for the ACO algorithm, and it is designed for fast convergence [36]. In MMAS, the trail intensities are constrained by an upper limit and a lower limit (i.e., τmin≤τip≤τmax). In our proposed ACO algorithm, the lower limit of trail intensity is set to τip/200, and the upper limit of trail intensity is set to τip×200.


#### 4.2.2. Ant-Sequence Generation

We use ten ants to generate ten different solutions in the ant-sequence generation step. An ant solution is generated in the following two phases:Trail intensities are used to determine the job, scheduled at positionp, where p∈1,n. Jobs are selected from the first five unscheduled jobs in the set US from the best solution. First, the cumulative trail intensity Tip=∑q=1pτip;∀i∈US is calculated for each unscheduled job. One of the following three rules is used to select a job randomly. The first rule selects the first unscheduled job from the best sequence found so far. The second rule selects the job with the highest value of cumulative trail intensity Tip. The third rule uses probability ψip=Tip/∑k∈KTkpto select jobs from the set US. The three rules are applied randomly with probabilities 0.4, 0.4, and 0.2, respectively.


#### 4.2.3. Insertion Local Search

The local search procedure is employed to improve the quality of the ant-schedules generated by the last step and improve the solution quality. The local search is evaluation using a modified objective functionf¯σ=fAσ+BigM×max0,Q−fBσ, where BigM is a large number. The modified objective function penalizes the objective function for infeasibility, which forces the solution to move towards feasibility during the search process. We use a simple insertion local search to improve the solution quality. In the local search, a job is rescheduled at all other positions. The best solution is updated if a better schedule is encountered during the process. The procedure is repeated for all the jobs one by one. Once the rescheduling of all the jobs at all the positions is completed, the whole procedure is repeated. The procedure is repeated until the modified objective function f¯σ keeps on improving.


#### 4.2.4. Updating Trail Intensities

The trail intensities are updated based on the best sequence as well as the current sequence. LetObjcurrent and Objbest denote the objective function value for the current sequence and the best sequence, respectively. L is the trail intensity deposit Lipcfrom the current sequence and the trail intensity deposit Lip∗ from the best sequence can be calculated using the following equations:(17)Lipc=1Objcurrent,if job is in thepthposition of current sequence,0,otherwise,Lip∗=1Objbest,if job is in thepthposition of best sequence,0,otherwise.Using the abovementioned expressions, the trail intensities are updated by the following equations:(18)τipnew=ρ×τipold+Lipc+Lip∗.In this paper, ACO is stopped after 100 iterations. We use the values available in the literature to set different parameters for ACO. The trail persistence factorρ is set to 0.95.


### 4.3. Intelligent Water Drop (IWD) Algorithm

The intelligent water drop (IWD) algorithm is a swarm-based method used for solving combinatorial optimization problems [33, 34]. In nature, we often observe that the water takes the path of least resistance, which translates into a water flow, such as a river, choosing the shortest path to their final destination, such as a lake or the sea. The IWD algorithm is based on this natural phenomenon of water flow in a river and its impact on the river bed’s soil. The velocity of the water drops and the amount of the soil on the way mainly affect the river’s flow. The IWD uses these two properties (soil and velocity) to find the combinatorial optimization problem. We consider that the water flows from the first position to the nth position through different jobs while solving a scheduling problem. This paper adopts the IWD algorithm used by Alijla et al. [34], which mainly uses the following variables:soili,j: amount of soil carried at position i, if water flows through job jsoilk: amount of soil carried by water drop kvelkt: the velocity of water drop k at time tiwd: number of water dropsThe fundamental procedures of the IWD algorithm are listed below, followed by a detailed description.Step 1: initialize variablessoili,j, soilk, and velktStep 2: follow the below steps and terminate this step until the termination condition is not met(i)
Generate the solution using the principle of IWD for alliwdwater drops(ii)
Carry out the local search to improve the solution for alliwdwater drops(iii)
Update the best solution found so far(iv)
Update the global soilStep 3: report the best solution as a final solution of ACOThe IWD starts with the initialization of variables. We use the values proposed by Alijla et al. [34] to initialize the variables and to set the parameter values. The variables are initialized as follows:(19)soili,j=1000,soilk=4,velk=100.


#### 4.3.1. Solution Construction

A solution of a single-machine-scheduling problem consists of finding the jobs for each position of the sequence. A water dropk starts with the first position and moves towards the nth position. The sequence of jobs determines the path of the water drop. The IWD algorithm selects the job j from the unscheduled job set Vusjk for sequencing at position i using the following probability distribution formula:(20)pikj=fsoili,j∑l∈Vusjkfsoili,l,where(21)fsoili,j=10.01+gsoili,j,gsoili,j=soili,j,ifminl∈Vusjksoili,l≥0,soili,j−minl∈Vusjksoili,l,else.After selecting the jobj for sequencing at position i, the following variables are updated:(22)velkt+1=velkt+avbv+cv×soili,j,Δsoili,j=asbs+cs×1/velkt+1,soilk=soilk+Δsoili,j,soili,j=1−ρn×soili,j−ρn×Δsoili,j.Here,av,bv,cv,as,bs,cs,andρnare the parameters. We set the value of these parameters according to the value set by Alijla et al. [34] as 1, 0.01, 1, 1, 0.01, 1, and 0.9.Once the complete solution of a water drop is built, the solution is improved using the local search method described in Subsection4.2.3.


#### 4.3.2. Updating the Global Soil

The global soil updating step is referred to as a reinforcement phase. In this step, global soil is updated using the local best solution found amongiwd solutions. Let qTlBrepresent the objective function of the local best solution. The global soil value is updated as follows:(23)soili,j=1+ρiwd×soili,j−ρiwd×soillbk×1qTlb,where ρiwd is a parameter value set as 0.90 according to the value set by Alijla et al. [34].


#### 4.3.3. Termination Phase

In every iteration,iwd number of solutions are created and improved using local search schemes. After generating the solutions, global soil is updated. These two processes are repeated until a prespecified number of iteration, and finally, the best solution found so far is reported. The structure of IWD is similar to the structure of ACO. To make the two algorithms comparable, we used the same local search schemes and ran the algorithm for the same number of prespecified iterations. Thus, the IWD algorithm is stopped after 100 iterations for both IWD and the ACO.


## 4.1. Heuristic Algorithm

The heuristic first creates partial schedulesσA and σB for A- and B-type of jobs. The jobs in the sequence σA are arranged in nonincreasing order of density δiA. The jobs in the sequence σB are arranged in nonincreasing order of their due dates diB. A complete solution σis then constructed by first sequencing A jobs followed by B jobs. The resultant solution can be infeasible. If the infeasibility is encountered, A jobs are moved towards the end of the sequence to make the solution feasible. The pseudocode of the heuristic is presented below (Algorithm 1).Algorithm 1:Heuristic algorithm.
(1)
/∗ Initial Solution ∗/(2)
Create a partial sequenceσA and σB(3)
Create a solutionσ⟵σA∪σB //combine sequences σA and σB to construct σ(4)
CalculateU⟵fBσ //Calculate the weighted number of tardy job for sequence σ(5)
/∗ Feasibility phase ∗/(6)
fork =  n1 to 1 do(7)
Select jobJ=σk(8)
forl = k+1 to n−k−n1 do(9)
σtemp⟵Create new sequence fromσby reinserting jobJat positionl(10)
Utemp⟵fBσtemp //Calculate the weighted number of tardy job for σtemp(11)
ifUtemp≤Qthen(12)
breakl loop(13)
end if(14)
end for(15)
σ⟵σtemp;U⟵Utemp(16)
ifUtemp≤Q then(17)
breakk loop(18)
end if(19)
end for(20)
return solutionσTo understand the heuristic algorithm, consider an instance with 3 A-type of jobs and 3B jobs. The parameters associated with 6 jobs are provided in Table 1. Consider upper bound Q for the total number of tardy jobs for agent B to be 2.Table 1
A numerical example with 6 jobs.
JobAgentrixpixwixδixdixJ1A31480.57—J2A11280.67—J3A01220.17—J4B36—0.1762J5B012—0.4213J6B216—0.5016The heuristic starts with creating partial sequencesσA=J2−J1−J3 and σB=J5−J6−J4. The initial solution is created by combining these two sequences σ=J2−J1−J3−J5−J6−J4. The start time and completion time of each job for a sequence σare shown in Table 2.Table 2
Completion time of sequenceσ
Sequence (σ)J2J1J3J5J6J4Start time11327395157Completion time132739515763Due date———131662The total weighted completion time of agent A for the sequenceσ is 398 (i.e., U =  13×8+27×8+39×2 = 398. The total number of tardy jobs for agent B for the sequence σ is 3 (i.e., U=3). Since U>Q, the sequence σ is infeasible. Thus, the algorithm calls the feasibility phase for obtaining a feasible solution. When k = 3, job J3 is selected for moving towards the end of the schedule. Job J3 is first reinserted at positions l = 4, to create σtemp=J2−J1−J5−J3−J6−J4 with Utemp=3. Since the number of tardy jobs remains greater than Q, the job is now inserted at position l = 5 and then finally at position l = 6 to create a sequence σtemp=J2−J1−J5−J6−J4−J3. At the end of the l loop, the sequence σis replaced by σtemp to form the sequence σ=J2−J1−J5−J6−J4−J3. When k = 2, job J1 is selected and inserted at positions l = 3, l = 4 and l = 5, and finally sequence σ is updated as σ=J2−J5−J6−J4−J1−J3. When k = 1, job J2 is selected and inserted at position l = 2 to form the sequence σtemp=J5−J2−J6−J4−J1−J3 with Utemp=2. At this time, l loop breaks because the total number of tardy jobs is less than or equal to Q. After the exit of the l loop, the sequence σis replaced by σtemp. Finally, the sequence σ=J5−J2−J6−J4−J1−J3 is reported as the solution of the heuristic algorithm.


## 4.2. Ant Colony Optimization (ACO) Algorithm

Ant colony optimization (ACO) algorithm was designed by [35]. They took their inspiration to develop the algorithm from the foraging behavior of ants. The ants always use the shortest path while seeking food from their nest. The max-min ant system (MMAS) is employed in the proposed algorithm. The fundamental procedures of the proposed ACO algorithm are listed below, followed by a detailed description.Step 1: generate an initial solution using the heuristic algorithm described in Section4.1Step 2: set parameters, trail intensity matrixτip, trail intensities upper bound (τmax) and the trail intensity lower bound (τmin)Step 3: follow the below steps and terminate this step until the condition of termination is not met(i)
Generate solutions using the trail intensities(ii)
Carry out the local search to improve the solution(iii)
Update the trail intensity(iv)
Update the best solution found so farStep 4: report the best solution as a final solution of ACO


### 4.2.1. Parameter Initialization

The trail intensity is denoted byτip, where τip depicts the trail intensity of the scheduling job i in the position p. In this paper, the initial trail intensity is set τip=1/1−ρ×IniObj. Here, IniObj represents the objective function value of the initial solution. The index ρ indicates the trail persistence.In this paper, we take the max-min ant system (MMAS) into consideration. The MMAS is an improvement plan for the ACO algorithm, and it is designed for fast convergence [36]. In MMAS, the trail intensities are constrained by an upper limit and a lower limit (i.e., τmin≤τip≤τmax). In our proposed ACO algorithm, the lower limit of trail intensity is set to τip/200, and the upper limit of trail intensity is set to τip×200.


### 4.2.2. Ant-Sequence Generation

We use ten ants to generate ten different solutions in the ant-sequence generation step. An ant solution is generated in the following two phases:Trail intensities are used to determine the job, scheduled at positionp, where p∈1,n. Jobs are selected from the first five unscheduled jobs in the set US from the best solution. First, the cumulative trail intensity Tip=∑q=1pτip;∀i∈US is calculated for each unscheduled job. One of the following three rules is used to select a job randomly. The first rule selects the first unscheduled job from the best sequence found so far. The second rule selects the job with the highest value of cumulative trail intensity Tip. The third rule uses probability ψip=Tip/∑k∈KTkpto select jobs from the set US. The three rules are applied randomly with probabilities 0.4, 0.4, and 0.2, respectively.


### 4.2.3. Insertion Local Search

The local search procedure is employed to improve the quality of the ant-schedules generated by the last step and improve the solution quality. The local search is evaluation using a modified objective functionf¯σ=fAσ+BigM×max0,Q−fBσ, where BigM is a large number. The modified objective function penalizes the objective function for infeasibility, which forces the solution to move towards feasibility during the search process. We use a simple insertion local search to improve the solution quality. In the local search, a job is rescheduled at all other positions. The best solution is updated if a better schedule is encountered during the process. The procedure is repeated for all the jobs one by one. Once the rescheduling of all the jobs at all the positions is completed, the whole procedure is repeated. The procedure is repeated until the modified objective function f¯σ keeps on improving.


### 4.2.4. Updating Trail Intensities

The trail intensities are updated based on the best sequence as well as the current sequence. LetObjcurrent and Objbest denote the objective function value for the current sequence and the best sequence, respectively. L is the trail intensity deposit Lipcfrom the current sequence and the trail intensity deposit Lip∗ from the best sequence can be calculated using the following equations:(17)Lipc=1Objcurrent,if job is in thepthposition of current sequence,0,otherwise,Lip∗=1Objbest,if job is in thepthposition of best sequence,0,otherwise.Using the abovementioned expressions, the trail intensities are updated by the following equations:(18)τipnew=ρ×τipold+Lipc+Lip∗.In this paper, ACO is stopped after 100 iterations. We use the values available in the literature to set different parameters for ACO. The trail persistence factorρ is set to 0.95.


## 4.2.1. Parameter Initialization

The trail intensity is denoted byτip, where τip depicts the trail intensity of the scheduling job i in the position p. In this paper, the initial trail intensity is set τip=1/1−ρ×IniObj. Here, IniObj represents the objective function value of the initial solution. The index ρ indicates the trail persistence.In this paper, we take the max-min ant system (MMAS) into consideration. The MMAS is an improvement plan for the ACO algorithm, and it is designed for fast convergence [36]. In MMAS, the trail intensities are constrained by an upper limit and a lower limit (i.e., τmin≤τip≤τmax). In our proposed ACO algorithm, the lower limit of trail intensity is set to τip/200, and the upper limit of trail intensity is set to τip×200.


## 4.2.2. Ant-Sequence Generation

We use ten ants to generate ten different solutions in the ant-sequence generation step. An ant solution is generated in the following two phases:Trail intensities are used to determine the job, scheduled at positionp, where p∈1,n. Jobs are selected from the first five unscheduled jobs in the set US from the best solution. First, the cumulative trail intensity Tip=∑q=1pτip;∀i∈US is calculated for each unscheduled job. One of the following three rules is used to select a job randomly. The first rule selects the first unscheduled job from the best sequence found so far. The second rule selects the job with the highest value of cumulative trail intensity Tip. The third rule uses probability ψip=Tip/∑k∈KTkpto select jobs from the set US. The three rules are applied randomly with probabilities 0.4, 0.4, and 0.2, respectively.


## 4.2.3. Insertion Local Search

The local search procedure is employed to improve the quality of the ant-schedules generated by the last step and improve the solution quality. The local search is evaluation using a modified objective functionf¯σ=fAσ+BigM×max0,Q−fBσ, where BigM is a large number. The modified objective function penalizes the objective function for infeasibility, which forces the solution to move towards feasibility during the search process. We use a simple insertion local search to improve the solution quality. In the local search, a job is rescheduled at all other positions. The best solution is updated if a better schedule is encountered during the process. The procedure is repeated for all the jobs one by one. Once the rescheduling of all the jobs at all the positions is completed, the whole procedure is repeated. The procedure is repeated until the modified objective function f¯σ keeps on improving.


## 4.2.4. Updating Trail Intensities

The trail intensities are updated based on the best sequence as well as the current sequence. LetObjcurrent and Objbest denote the objective function value for the current sequence and the best sequence, respectively. L is the trail intensity deposit Lipcfrom the current sequence and the trail intensity deposit Lip∗ from the best sequence can be calculated using the following equations:(17)Lipc=1Objcurrent,if job is in thepthposition of current sequence,0,otherwise,Lip∗=1Objbest,if job is in thepthposition of best sequence,0,otherwise.Using the abovementioned expressions, the trail intensities are updated by the following equations:(18)τipnew=ρ×τipold+Lipc+Lip∗.In this paper, ACO is stopped after 100 iterations. We use the values available in the literature to set different parameters for ACO. The trail persistence factorρ is set to 0.95.


## 4.3. Intelligent Water Drop (IWD) Algorithm

The intelligent water drop (IWD) algorithm is a swarm-based method used for solving combinatorial optimization problems [33, 34]. In nature, we often observe that the water takes the path of least resistance, which translates into a water flow, such as a river, choosing the shortest path to their final destination, such as a lake or the sea. The IWD algorithm is based on this natural phenomenon of water flow in a river and its impact on the river bed’s soil. The velocity of the water drops and the amount of the soil on the way mainly affect the river’s flow. The IWD uses these two properties (soil and velocity) to find the combinatorial optimization problem. We consider that the water flows from the first position to the nth position through different jobs while solving a scheduling problem. This paper adopts the IWD algorithm used by Alijla et al. [34], which mainly uses the following variables:soili,j: amount of soil carried at position i, if water flows through job jsoilk: amount of soil carried by water drop kvelkt: the velocity of water drop k at time tiwd: number of water dropsThe fundamental procedures of the IWD algorithm are listed below, followed by a detailed description.Step 1: initialize variablessoili,j, soilk, and velktStep 2: follow the below steps and terminate this step until the termination condition is not met(i)
Generate the solution using the principle of IWD for alliwdwater drops(ii)
Carry out the local search to improve the solution for alliwdwater drops(iii)
Update the best solution found so far(iv)
Update the global soilStep 3: report the best solution as a final solution of ACOThe IWD starts with the initialization of variables. We use the values proposed by Alijla et al. [34] to initialize the variables and to set the parameter values. The variables are initialized as follows:(19)soili,j=1000,soilk=4,velk=100.


### 4.3.1. Solution Construction

A solution of a single-machine-scheduling problem consists of finding the jobs for each position of the sequence. A water dropk starts with the first position and moves towards the nth position. The sequence of jobs determines the path of the water drop. The IWD algorithm selects the job j from the unscheduled job set Vusjk for sequencing at position i using the following probability distribution formula:(20)pikj=fsoili,j∑l∈Vusjkfsoili,l,where(21)fsoili,j=10.01+gsoili,j,gsoili,j=soili,j,ifminl∈Vusjksoili,l≥0,soili,j−minl∈Vusjksoili,l,else.After selecting the jobj for sequencing at position i, the following variables are updated:(22)velkt+1=velkt+avbv+cv×soili,j,Δsoili,j=asbs+cs×1/velkt+1,soilk=soilk+Δsoili,j,soili,j=1−ρn×soili,j−ρn×Δsoili,j.Here,av,bv,cv,as,bs,cs,andρnare the parameters. We set the value of these parameters according to the value set by Alijla et al. [34] as 1, 0.01, 1, 1, 0.01, 1, and 0.9.Once the complete solution of a water drop is built, the solution is improved using the local search method described in Subsection4.2.3.


### 4.3.2. Updating the Global Soil

The global soil updating step is referred to as a reinforcement phase. In this step, global soil is updated using the local best solution found amongiwd solutions. Let qTlBrepresent the objective function of the local best solution. The global soil value is updated as follows:(23)soili,j=1+ρiwd×soili,j−ρiwd×soillbk×1qTlb,where ρiwd is a parameter value set as 0.90 according to the value set by Alijla et al. [34].


### 4.3.3. Termination Phase

In every iteration,iwd number of solutions are created and improved using local search schemes. After generating the solutions, global soil is updated. These two processes are repeated until a prespecified number of iteration, and finally, the best solution found so far is reported. The structure of IWD is similar to the structure of ACO. To make the two algorithms comparable, we used the same local search schemes and ran the algorithm for the same number of prespecified iterations. Thus, the IWD algorithm is stopped after 100 iterations for both IWD and the ACO.


## 4.3.1. Solution Construction

A solution of a single-machine-scheduling problem consists of finding the jobs for each position of the sequence. A water dropk starts with the first position and moves towards the nth position. The sequence of jobs determines the path of the water drop. The IWD algorithm selects the job j from the unscheduled job set Vusjk for sequencing at position i using the following probability distribution formula:(20)pikj=fsoili,j∑l∈Vusjkfsoili,l,where(21)fsoili,j=10.01+gsoili,j,gsoili,j=soili,j,ifminl∈Vusjksoili,l≥0,soili,j−minl∈Vusjksoili,l,else.After selecting the jobj for sequencing at position i, the following variables are updated:(22)velkt+1=velkt+avbv+cv×soili,j,Δsoili,j=asbs+cs×1/velkt+1,soilk=soilk+Δsoili,j,soili,j=1−ρn×soili,j−ρn×Δsoili,j.Here,av,bv,cv,as,bs,cs,andρnare the parameters. We set the value of these parameters according to the value set by Alijla et al. [34] as 1, 0.01, 1, 1, 0.01, 1, and 0.9.Once the complete solution of a water drop is built, the solution is improved using the local search method described in Subsection4.2.3.


## 4.3.2. Updating the Global Soil

The global soil updating step is referred to as a reinforcement phase. In this step, global soil is updated using the local best solution found amongiwd solutions. Let qTlBrepresent the objective function of the local best solution. The global soil value is updated as follows:(23)soili,j=1+ρiwd×soili,j−ρiwd×soillbk×1qTlb,where ρiwd is a parameter value set as 0.90 according to the value set by Alijla et al. [34].


## 4.3.3. Termination Phase

In every iteration,iwd number of solutions are created and improved using local search schemes. After generating the solutions, global soil is updated. These two processes are repeated until a prespecified number of iteration, and finally, the best solution found so far is reported. The structure of IWD is similar to the structure of ACO. To make the two algorithms comparable, we used the same local search schemes and ran the algorithm for the same number of prespecified iterations. Thus, the IWD algorithm is stopped after 100 iterations for both IWD and the ACO.


## 5. Numerical Results Analysis

The performance of the proposed algorithm is evaluated using both small and large size problem instances. The results obtained by the proposed ant colony optimization algorithm are compared with the solutions generated by using the CPLEX solver. The linear programming-based mathematical model is solved by AMPL software with CPLEX solver. The AMPL is running on an iMac desktop with 3.3 GHz with 8 GB of RAM. The coding of the proposed algorithms is done in the C++ programming language and is implemented on AMD Opteron 2.3 GHz with 16 GB RAM.In this paper, we generated 116 problems (4 problems∗ 29 problem instances each). The smallest instance has 5 jobs for each agent, while the largest instance has 150 jobs. The jobs’ processing time and weight are generated using a random number between [1, 15] and [1, 10], respectively. The upper bound value Q is generated as Q=α×nB, where α was assigned randomly between 0.4 and 0.6.The due date of each job is generated in the uniform distribution range of0.1×∑i=1npi,0.9×∑i=1npi. The value of the release date of each job is generated according to the formula, as ri=maxβ×di−pi,0. The experiment uses the following two types of datasets:(1)
Small and medium datasets are used to weigh the proposed algorithms’ results and the CPLEX result(2)
Large datasets are used to evaluate the scalability of the computation time of the proposed algorithmsThe small dataset represents those problem instances, which can be solved optimally by mathematical models within reasonable CPU time. Due to the complexity of the problems, the mathematical model was applied to solve only small- and medium-size problem instances in a specific time, and one hour was set as the time at which the mathematical model will obtain a solution. The developed mathematical model’s optimal solution can be solved using the AMPL software with the CPLEX solver. The quality of results is evaluated by using relative percentage deviation (i.e., RPD). The formula to calculateRPDk of the proposed algorithm or CPLEX result for the kth problem instance is(24)RPDk=Hk−BkBk×100%.Here,Hk represents the proposed metaheuristic solution in thekth problem instance, and Bk represents the best algorithm solution in the kth problem instance.The following notations are used to report and evaluate the numerical results:CPLEX: mathematical model solved by CPLEX solverOBJ: absolute value of objective function generated by algorithmsRPD: relative percentage of deviationCPU: running time of the proposed algorithmACO: ant colony algorithmIWD: intelligent water drop algorithm


### 5.1. Numerical Experiment with a Small and Medium Dataset

We compare the projected ant colony optimization-based metaheuristic results with the result of CPLEX. Tables3–6 show the solution and CPU time of the proposed algorithms and CPLEX result for Problem 1, Problem 2, Problem 3, and Problem 4, respectively. The results with ∗ represent the optimal solution.Table 3
Numerical results of Problem 1 for small and medium problem instances.
InstancenCPLEXACOIWDOBJCPUOBJCPURPDOBJCPURPD110527∗0.385270.070.005270.070.00212902∗1.209020.130.009020.130.003141382∗2.7613820.230.0013820.220.004161105∗35.5011050.340.0011050.320.005182451∗444.8225740.415.0225740.445.026201885∗1777.1218850.670.0018850.610.007223022360030180.90.0030180.870.008243787360037681.070.1337631.070.009263865360038851.430.5238651.490.0010284887360049111.861.9948151.810.0011303738360037382.661.2536922.330.0012324007360039672.890.0039672.920.0013345305360058323.2214.4750953.420.0014366696360066805.060.0066804.570.0015385603360056855.982.1755645.660.0016408560360085426.440.2285236.30.00Average3607.632391.3623650.062.081.613584.812.010.31Table 4
Numerical results of Problem 2 for small and medium problem instances.
InstancenCPLEXACOIWDOBJCPUOBJCPURPDOBJCPURPD110109∗0.3561090.060.001090.050.00212211∗2.3892110.10.002110.10.00314247∗6.0692470.180.002470.160.00416213∗25.2762130.250.002130.250.0051843736004460.312.064370.320.0062026236002620.510.002620.440.0072257136005670.670.005670.670.0082471936007190.850.007250.830.8392667536006731.170.306711.150.0010281044360010281.520.5910221.470.00113073236007202.090.007201.810.00123291936009102.550.009102.340.0013341280360014142.5710.4713092.792.2714361430360013363.80.0013363.330.0015381429∗2288.9114504.692.0414214.630.0016401732360017275.551.5917004.950.00Average750.632620.19752.001.681.07741.251.580.19Table 5
Numerical results of Problem 3 for small and medium problem instances.
InstancenCPLEXACOIWDOBJCPUOBJCPURPDOBJCPURPD110180∗0.1381800.070.001800.060.00212867∗1.1988670.120.008670.110.003141046∗7.71910460.190.0010460.180.00416694∗29.3616940.280.006940.260.005181760360017600.350.0017600.380.006201615360016150.530.0016150.460.007221385360013850.720.0013850.720.008242819360028190.950.0028190.90.009262161360021611.230.0021611.240.0010283317360034341.513.5333171.560.0011302310360023102.270.0023101.930.0012322833360028212.310.0028212.310.0013344015360040632.991.63399830.0014363412360033973.450.0033973.340.0015383794360036874.51.1836444.450.0016406095360060715.170.0060774.910.10Average2393.942702.402394.381.670.402380.691.610.01Table 6
Numerical results of Problem 4 for small and medium problem instances.
InstancenCPLEXACOIWDOBJCPUOBJCPURPDOBJCPURPD11079∗0.42790.060.00790.060.00212193∗1.231930.120.001930.110.00314203∗28.982030.190.002030.180.00416167∗174.681670.260.001670.240.0051828536002850.340.002850.380.0062019936001990.510.001990.450.0072234436003440.710.003440.680.0082458536005770.920.005770.870.0092647936004781.220.004781.220.00102878736008061.432.417911.60.51113056836005682.210.005681.910.00123275436007392.250.007392.310.0013341070360010812.971.2210682.830.00143683336008263.410.008263.320.0015381106360010694.271.4210544.430.0016401263360012424.890.0012564.721.13Average557.192712.83553.501.610.32551.691.580.10The proposed ACO and IWD algorithm can efficiently solve small problem instances and balance CPU time with result quality. It is clear from Tables3–6 that the proposed ACO algorithm and the IWD algorithm can solve all small problem instances in minutes. The average RPD of the two algorithms is summarized and showed in Table 7. The average RPD of IWD is less than 0.4%, which indicates that the solution of IWD is not more than 0.4% of the optimal solution. The RPD of ACO is also less than 2%. It means that our proposed ACO and IWD algorithm has an excellent performance in solving small problem instances.Table 7
The average computation time and average relative percentage deviation of four problems.
ACOIWDAvg. CPUAvg. RPDAvg. CPUAvg. RPDProblem 12.081.612.010.31Problem 21.681.071.580.19Problem 31.670.401.610.01Problem 41.610.321.580.10The experiment’s purpose with small-sized instances is to check the proposed algorithms’ effectiveness by comparing them with the optimal solution. Results indicate that the performance of the proposed metaheuristics is close to the optimal solution. However, the CPU time of proposed metaheuristics does not increase exponentially, unlike with the CPLEX solver used to obtain an optimal solution. Overall, the IWD metaheuristic performance is better than ACO’s performance in terms of both solution quality and the CPU time.


### 5.2. Numerical Experiment with Large Dataset

The large dataset is used to compare the performance of proposed algorithms with each other. The numerical results of four problems for large datasets are reported in Tables8–11.Table 8
Numerical results of Problem 1 for large problem instances.
Ins.nHeuristicACOIWDOBJCPURPDOBJCPURPDOBJCPURPD176035758<0.2146.8114586280.6814488250188073276<0.2148.3330705744.062950767019100130473<0.2119.85615281643.6759347140020120231016<0.2162.94879352710.0987860245021140338574<0.2192.791186914722.64115636438022160337444<0.2154.991405037206.17132336680023180502816<0.2165.5119323110562.04189376996024200583422<0.2182.3621661714074.842066241287025220659063<0.2120.33339253180013.422991251814026240830265<0.2181.5231784425137.7729492223020272601049144<0.2168.9642477430958.8939008130950282801182812<0.2197.5040824440012.6839758039100293001295486<0.2127.9359162648614.0956837048520Average557657.6<0.2159.22226579.815744.70214250.215270Table 9
Numerical results of Problem 2 forl problem instances.
Ins.nHeuristicACOIWDOBJCPURPDOBJCPURPDOBJCPURPD17608113<0.255.313626260.003672221.27188017579<0.264.286452702.6762806201910023074<0.252.22112941432.391102412802012038695<0.261.11150762560.181504922202114054679<0.260.87219664492.592139739102216060634<0.258.53272356947.682514365502318086965<0.260.123612610194.0034680922024200110060<0.265.103994313513.83384141271025220139835<0.256.7169946171913.45605391770026240156011<0.265.825667824505.91533272244027260198803<0.262.4283398297910.43747032869028280211252<0.264.557885039225.01748983762029300238829<0.258.9810444247636.219795646450Average103425.3<0.260.4642694.771526.24.9539775.5414590.10Table 10
Numerical results of Problem 3 for large problem instances.
Ins.nHeuristicACOIWDOBJCPURPDOBJCPURPDOBJCPURPD176025181<0.2167.889448200.519400180188048490<0.2166.4919054524.72181964601910094389<0.2155.98384071294.1636873107020120117355<0.2132.00505841870.0050584151021140173695<0.2125.22781703741.3677123298022160215415<0.2154.97863876212.2584486483023180320249<0.2157.161259428881.13124534805024200317046<0.2143.6313080812010.52130135991025220434938<0.2183.04180184167317.261536681561026240468509<0.2175.2917060422670.241701891889027260592630<0.2190.96229646253212.752036812607028280702472<0.2215.6822426236310.782225273044029300882460<0.2195.3331985145137.0429880641560Average337909.9<0.2166.43127949.81391.44.051215541242.80Table 11
Numerical results of Problem 4 for large problem instances.
Ins.nHeuristicACOIWDOBJCPURPDOBJCPURPDOBJCPURPD17605975<0.2122.202708340.712689330188010659<0.2141.924638865.2744068001910017609<0.2125.7981062153.94779917402012020813<0.2116.5596113230.00961125302114031751<0.2102.17161176392.621570554302216039526<0.2137.09172966493.751667191402318057559<0.2138.70244518991.402411481002420059202<0.2122.632676317690.6426592157202522091178<0.2135.6344615191915.3038696167002624088735<0.2153.623514832720.46349882273027260116397<0.2148.9652314383711.89467534131028280134196<0.2173.214955055840.88491184534029300157294<0.2148.916461158292.256319251220Average63914.9<0.2135.9527379.119273.7826179.5417010The results reported in Tables8–11 exhibit that the performance of IWD is the best followed by the ACO and heuristic algorithm. The IWD produced the best results for almost all instances (55 out of 55 instances). On average, the proposed IWD algorithm’s solutions are 4.70%, 4.85%, 4.05%, and 3.75% better than the solutions of the ACO algorithm for four problems, respectively. At the same time, the CPU time of the IWD algorithm is less than the CPU of ACO. The results indicate the better performance of IWD over ACO. The proposed heuristic algorithm can solve all problems within 0.2 seconds, but the heuristic algorithm’s performance is worst, with on average RPD of 135.95%.If there is a need for an accurate solution and the CPU time is not the priority consideration, the IWD algorithm can be adopted as a solution method. IWD can be imbedded with entrepreneur resource planning (ERP) software for creating a master production schedule. The results indicate that the IWD algorithm has the edge over ACO algorithms for embedding with any ERP software since it provides a better quality solution in shorter CPU time. One of the drawbacks of the metaheuristic algorithm is the excessive CPU time compared to the heuristic algorithm. Therefore, if the solution is quickly required, the heuristic algorithm can be adopted as a solution.


## 5.1. Numerical Experiment with a Small and Medium Dataset

We compare the projected ant colony optimization-based metaheuristic results with the result of CPLEX. Tables3–6 show the solution and CPU time of the proposed algorithms and CPLEX result for Problem 1, Problem 2, Problem 3, and Problem 4, respectively. The results with ∗ represent the optimal solution.Table 3
Numerical results of Problem 1 for small and medium problem instances.
InstancenCPLEXACOIWDOBJCPUOBJCPURPDOBJCPURPD110527∗0.385270.070.005270.070.00212902∗1.209020.130.009020.130.003141382∗2.7613820.230.0013820.220.004161105∗35.5011050.340.0011050.320.005182451∗444.8225740.415.0225740.445.026201885∗1777.1218850.670.0018850.610.007223022360030180.90.0030180.870.008243787360037681.070.1337631.070.009263865360038851.430.5238651.490.0010284887360049111.861.9948151.810.0011303738360037382.661.2536922.330.0012324007360039672.890.0039672.920.0013345305360058323.2214.4750953.420.0014366696360066805.060.0066804.570.0015385603360056855.982.1755645.660.0016408560360085426.440.2285236.30.00Average3607.632391.3623650.062.081.613584.812.010.31Table 4
Numerical results of Problem 2 for small and medium problem instances.
InstancenCPLEXACOIWDOBJCPUOBJCPURPDOBJCPURPD110109∗0.3561090.060.001090.050.00212211∗2.3892110.10.002110.10.00314247∗6.0692470.180.002470.160.00416213∗25.2762130.250.002130.250.0051843736004460.312.064370.320.0062026236002620.510.002620.440.0072257136005670.670.005670.670.0082471936007190.850.007250.830.8392667536006731.170.306711.150.0010281044360010281.520.5910221.470.00113073236007202.090.007201.810.00123291936009102.550.009102.340.0013341280360014142.5710.4713092.792.2714361430360013363.80.0013363.330.0015381429∗2288.9114504.692.0414214.630.0016401732360017275.551.5917004.950.00Average750.632620.19752.001.681.07741.251.580.19Table 5
Numerical results of Problem 3 for small and medium problem instances.
InstancenCPLEXACOIWDOBJCPUOBJCPURPDOBJCPURPD110180∗0.1381800.070.001800.060.00212867∗1.1988670.120.008670.110.003141046∗7.71910460.190.0010460.180.00416694∗29.3616940.280.006940.260.005181760360017600.350.0017600.380.006201615360016150.530.0016150.460.007221385360013850.720.0013850.720.008242819360028190.950.0028190.90.009262161360021611.230.0021611.240.0010283317360034341.513.5333171.560.0011302310360023102.270.0023101.930.0012322833360028212.310.0028212.310.0013344015360040632.991.63399830.0014363412360033973.450.0033973.340.0015383794360036874.51.1836444.450.0016406095360060715.170.0060774.910.10Average2393.942702.402394.381.670.402380.691.610.01Table 6
Numerical results of Problem 4 for small and medium problem instances.
InstancenCPLEXACOIWDOBJCPUOBJCPURPDOBJCPURPD11079∗0.42790.060.00790.060.00212193∗1.231930.120.001930.110.00314203∗28.982030.190.002030.180.00416167∗174.681670.260.001670.240.0051828536002850.340.002850.380.0062019936001990.510.001990.450.0072234436003440.710.003440.680.0082458536005770.920.005770.870.0092647936004781.220.004781.220.00102878736008061.432.417911.60.51113056836005682.210.005681.910.00123275436007392.250.007392.310.0013341070360010812.971.2210682.830.00143683336008263.410.008263.320.0015381106360010694.271.4210544.430.0016401263360012424.890.0012564.721.13Average557.192712.83553.501.610.32551.691.580.10The proposed ACO and IWD algorithm can efficiently solve small problem instances and balance CPU time with result quality. It is clear from Tables3–6 that the proposed ACO algorithm and the IWD algorithm can solve all small problem instances in minutes. The average RPD of the two algorithms is summarized and showed in Table 7. The average RPD of IWD is less than 0.4%, which indicates that the solution of IWD is not more than 0.4% of the optimal solution. The RPD of ACO is also less than 2%. It means that our proposed ACO and IWD algorithm has an excellent performance in solving small problem instances.Table 7
The average computation time and average relative percentage deviation of four problems.
ACOIWDAvg. CPUAvg. RPDAvg. CPUAvg. RPDProblem 12.081.612.010.31Problem 21.681.071.580.19Problem 31.670.401.610.01Problem 41.610.321.580.10The experiment’s purpose with small-sized instances is to check the proposed algorithms’ effectiveness by comparing them with the optimal solution. Results indicate that the performance of the proposed metaheuristics is close to the optimal solution. However, the CPU time of proposed metaheuristics does not increase exponentially, unlike with the CPLEX solver used to obtain an optimal solution. Overall, the IWD metaheuristic performance is better than ACO’s performance in terms of both solution quality and the CPU time.


## 5.2. Numerical Experiment with Large Dataset

The large dataset is used to compare the performance of proposed algorithms with each other. The numerical results of four problems for large datasets are reported in Tables8–11.Table 8
Numerical results of Problem 1 for large problem instances.
Ins.nHeuristicACOIWDOBJCPURPDOBJCPURPDOBJCPURPD176035758<0.2146.8114586280.6814488250188073276<0.2148.3330705744.062950767019100130473<0.2119.85615281643.6759347140020120231016<0.2162.94879352710.0987860245021140338574<0.2192.791186914722.64115636438022160337444<0.2154.991405037206.17132336680023180502816<0.2165.5119323110562.04189376996024200583422<0.2182.3621661714074.842066241287025220659063<0.2120.33339253180013.422991251814026240830265<0.2181.5231784425137.7729492223020272601049144<0.2168.9642477430958.8939008130950282801182812<0.2197.5040824440012.6839758039100293001295486<0.2127.9359162648614.0956837048520Average557657.6<0.2159.22226579.815744.70214250.215270Table 9
Numerical results of Problem 2 forl problem instances.
Ins.nHeuristicACOIWDOBJCPURPDOBJCPURPDOBJCPURPD17608113<0.255.313626260.003672221.27188017579<0.264.286452702.6762806201910023074<0.252.22112941432.391102412802012038695<0.261.11150762560.181504922202114054679<0.260.87219664492.592139739102216060634<0.258.53272356947.682514365502318086965<0.260.123612610194.0034680922024200110060<0.265.103994313513.83384141271025220139835<0.256.7169946171913.45605391770026240156011<0.265.825667824505.91533272244027260198803<0.262.4283398297910.43747032869028280211252<0.264.557885039225.01748983762029300238829<0.258.9810444247636.219795646450Average103425.3<0.260.4642694.771526.24.9539775.5414590.10Table 10
Numerical results of Problem 3 for large problem instances.
Ins.nHeuristicACOIWDOBJCPURPDOBJCPURPDOBJCPURPD176025181<0.2167.889448200.519400180188048490<0.2166.4919054524.72181964601910094389<0.2155.98384071294.1636873107020120117355<0.2132.00505841870.0050584151021140173695<0.2125.22781703741.3677123298022160215415<0.2154.97863876212.2584486483023180320249<0.2157.161259428881.13124534805024200317046<0.2143.6313080812010.52130135991025220434938<0.2183.04180184167317.261536681561026240468509<0.2175.2917060422670.241701891889027260592630<0.2190.96229646253212.752036812607028280702472<0.2215.6822426236310.782225273044029300882460<0.2195.3331985145137.0429880641560Average337909.9<0.2166.43127949.81391.44.051215541242.80Table 11
Numerical results of Problem 4 for large problem instances.
Ins.nHeuristicACOIWDOBJCPURPDOBJCPURPDOBJCPURPD17605975<0.2122.202708340.712689330188010659<0.2141.924638865.2744068001910017609<0.2125.7981062153.94779917402012020813<0.2116.5596113230.00961125302114031751<0.2102.17161176392.621570554302216039526<0.2137.09172966493.751667191402318057559<0.2138.70244518991.402411481002420059202<0.2122.632676317690.6426592157202522091178<0.2135.6344615191915.3038696167002624088735<0.2153.623514832720.46349882273027260116397<0.2148.9652314383711.89467534131028280134196<0.2173.214955055840.88491184534029300157294<0.2148.916461158292.256319251220Average63914.9<0.2135.9527379.119273.7826179.5417010The results reported in Tables8–11 exhibit that the performance of IWD is the best followed by the ACO and heuristic algorithm. The IWD produced the best results for almost all instances (55 out of 55 instances). On average, the proposed IWD algorithm’s solutions are 4.70%, 4.85%, 4.05%, and 3.75% better than the solutions of the ACO algorithm for four problems, respectively. At the same time, the CPU time of the IWD algorithm is less than the CPU of ACO. The results indicate the better performance of IWD over ACO. The proposed heuristic algorithm can solve all problems within 0.2 seconds, but the heuristic algorithm’s performance is worst, with on average RPD of 135.95%.If there is a need for an accurate solution and the CPU time is not the priority consideration, the IWD algorithm can be adopted as a solution method. IWD can be imbedded with entrepreneur resource planning (ERP) software for creating a master production schedule. The results indicate that the IWD algorithm has the edge over ACO algorithms for embedding with any ERP software since it provides a better quality solution in shorter CPU time. One of the drawbacks of the metaheuristic algorithm is the excessive CPU time compared to the heuristic algorithm. Therefore, if the solution is quickly required, the heuristic algorithm can be adopted as a solution.


## 6. Conclusions

This paper evaluates a set of single-machine with two-agent scheduling problem to minimize the total weighted completion time and total completion time of the first agent while keeping the number of tardy jobs of the second agent under a prespecified limit. The service and manufacturing industries find many applications in the problems. In this paper, we proposed a general mathematical model for all four problems and an ACO-based metaheuristic to solve the problems. The proposed mathematical model is solved by using AMPL software with the CPLEX solver.It can be deduced from the results that the proposed metaheuristic has obtained near-optimal solutions, as the reported variation between the proposed metaheuristic and mathematical model’s outcomes are extremely low among four problems. More importantly, the proposed metaheuristic can reach a better solution than the CPLEX solver, and it consumes much less computation time than the CPLEX solver. Subsequent future research directions include developing other metaheuristics to provide even better results for larger sized problem instances in a shorter time.In the future, the algorithm used in this paper can be extended to solve different scheduling problems such as flow shop scheduling problems, job shop scheduling problems, parallel scheduling problem, and disassembly sequencing problems. The results exhibit the excellent performance of the IWD algorithm over the ACO algorithm. The results indicate the call for the application of the IWD algorithm on solving other scheduling problems.



---

*Source: 1385049-2020-12-29.xml*