Complexity, Nonlinear Evolution, Computational Experiments, AgentBased Modeling and Big Data Modeling for Complex Social Systems
View this Special IssueResearch Article  Open Access
Hongwei Li, Yuvraj Gajpal, Chirag Surti, Dongliang Cai, Amit Kumar Bhardwaj, "NatureInspired Metaheuristics for TwoAgent Scheduling with Due Date and Release Time", Complexity, vol. 2020, Article ID 1385049, 13 pages, 2020. https://doi.org/10.1155/2020/1385049
NatureInspired Metaheuristics for TwoAgent Scheduling with Due Date and Release Time
Abstract
This paper delves into a twoagent 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 NPhard 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 naturebased metaheuristic algorithms to solve the problem. The algorithm’s performance was gauged against the optimal solution obtained from the AMPLCPLEX 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 mediumsize problems, whereas the computation times are much less than the CPLEX solvers.
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 machinescheduling 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 machinescheduling problem involves the allocation of resources to process different jobs under different machine settings such as singlemachine setting [4], flowshop machine setting [5], job shop machine setting [6], and parallel machine setting [7]. The classical machinescheduling 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]. Twoagent 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. Twoagent 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 twoagent scheduling models have been studied in recent years, the studies related to the release daterelated twoagent scheduling model are relatively limited [14]. The number of tardy jobs minimization is aimed at only a few papers. Informed about the twoagent scheduling with due date literature, we consider a series of twoagent scheduling problems with due daterelated objective in this paper. We have defined the singlemachinescheduling 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 twoagent single machine which is donated as (Problem 1), (Problem 2), (Problem 3), and (Problem 4) with the following assumptions, where and represent two agents in the problem:(i)The jobs from the two agents have a real release time(ii)The jobs from agent A have positive weight(iii)The jobs from agent B 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 allowed
The paper contributes to the scheduling literature in many ways. In our knowledge, this paper first time develops algorithms to solve the twoagent 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 naturebased 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. Section 2 investigates the single machinescheduling 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 twoagent singlemachinescheduling problem. Twoagent scheduling problem considers two agents in which each agent has a set of jobs for processing in a singlemachine. Generally speaking, the research of a singlemachine and twoagent 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. TwoAgent Scheduling Problem with the Number of Tardy Job Objectives
Agnetis et al. [11] investigated three due date criteria based on twoagent scheduling models to minimize the number of tardy jobs. These problems are denoted by (P1), (P2), and (P3). They have proven the computational complexity of the problems mentioned above. The first problem could be solved in time while the complexity of the second problem is proved to be a binary NPhard. The complexity of the second problem is still unknown. Ng et al. [15] provided many lemmas for problem: the scheduling of all Atype jobs is done in the shortest processing time (SPT) rule and the scheduling of all Btype jobs is done in the earliest due date first rule (EDD) following an optimal schedule. Furthermore, they developed a pseudopolynomialtime algorithm to solve the problem of searching for an optimal solution. Ng et al. [15] studied the complexity of several twoagent scheduling problems to minimize tardy jobs. They also pointed out that the problem is strongly NPhard 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 twoagent 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., ) is binary NPhard. Lee et al. [17] extend Ng et al.’s [15] problem (i.e., ), considering an actual processing time approach. They proposed a branchandbound algorithm and heuristics to solve the problem. Yin et al. [18] studied the singlemachine twoagent 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 twoagent scheduling problem for determining the due dates. The literature studies other variants of the twoagent 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 twoagent scheduling problem with due daterelated 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 twoagent 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 twoagent scheduling model for unrelated parallel machinescheduling problem to minimize the number of total completion time and the number of tardy jobs criteria. They proposed a column generation method embedded with branchandprice algorithms to find the optimal solution. The complexity of the problem considered in this paper is proved to be NPhard 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. NatureInspired Algorithm
This paper uses two natureinspired 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. Natureinspired 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. Decisionmaking 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 decisionmaking involves finding the assignment of receiving and shipping doors. Jia et al. [31] used a bee colony algorithm to solve bike repositioning in bikesharing systems in which decisionmaking 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 have 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, Atype jobs also have a positive weight, and Btype 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 Atype jobs is as minimum as possible while limiting the number of tardy jobs of Btype jobs within a prespecified limit. We use the following notations to describe and formulate the problems: X: set of agents, X = {A, B} : the number of jobs for the agent n: total number of jobs, N: set of all n jobs, : set of Btype jobs, consisting of jobs, . _{:} job set of the agent : the processing time of job for the agent : release date of i^{th} job for the agent : weight of i^{th} job for the agent : the density of i^{th} job for the agent , : due date of i^{th} job for the agent : completion time of i^{th} job for the agent : ordered set of jobs already scheduled for a given sequence , the value of the objective function for the agent Q: the upper bound, a constant number. : a large number
In this paper, we consider four problems, denoted as follows: Problem 1: Problem 2: Problem 3: Problem 4:
Problem 1 is a singlemachine twoagent scheduling problem. This problem minimizes the total weighted completion time of Atype jobs subjected to an upper bound on the total number of tardy Btype jobs. It also has arbitrary release dates and arbitrary weights. Problem 2 minimizes the total completion time of Atype 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 Atype jobs and/or ensures that the maximum number of tardy Btype jobs does not exceed the upper bound . Problem 4 is an unweighted case of Problem 3. The objective of Problem 4 is to minimize the total completion time of Atype jobs.
3.2. NPHardness
Agnetis et al. [11] have proved that the problems and are binary NPhard. They also reported that problem is still open. Therefore, Problem 1 is also NPhard. Recently, Chen et al. [29] proved that problem is NPhard.
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: : a binary variable for assigning job at position , : a binary variable for starting job at position j just after completion of the job at position j − 1, : a binary variable for tardy Btype jobs, : completion time of job : completion time of job at position j, : starting time of job at position j,
The mixedinteger linear programming (MILP) formulation for the problem can be described as follows:subject to
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 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 . These constraints also ensure that the job i is scheduled at position j then . Constraint (12) is used to determine that if the processing of the job is finished after its due date, then the job is marked as a tardy. Constraint (13) confirms that the total number of tardy Btype 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 and for A and Btype of jobs. The jobs in the sequence are arranged in nonincreasing order of density . The jobs in the sequence are arranged in nonincreasing order of their due dates . 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).

To understand the heuristic algorithm, consider an instance with 3 Atype of jobs and 3 B 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.

The heuristic starts with creating partial sequences and . The initial solution is created by combining these two sequences . The start time and completion time of each job for a sequence are shown in Table 2.

The total weighted completion time of agent A for the sequence is 398 (i.e., = = 398. The total number of tardy jobs for agent B for the sequence is 3 (i.e., ). Since , 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 with . 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 . At the end of the l loop, the sequence is replaced by to form the sequence . When k = 2, job J1 is selected and inserted at positions l = 3, l = 4 and l = 5, and finally sequence is updated as . When k = 1, job J2 is selected and inserted at position l = 2 to form the sequence with . 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 . Finally, the sequence 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 maxmin 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 Section 4.1 Step 2: set parameters, trail intensity matrix , trail intensities upper bound () and the trail intensity lower bound () 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 far Step 4: report the best solution as a final solution of ACO
4.2.1. Parameter Initialization
The trail intensity is denoted by , where depicts the trail intensity of the scheduling job in the position . In this paper, the initial trail intensity is set . Here, represents the objective function value of the initial solution. The index indicates the trail persistence.
In this paper, we take the maxmin 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., ). In our proposed ACO algorithm, the lower limit of trail intensity is set to , and the upper limit of trail intensity is set to .
4.2.2. AntSequence Generation
We use ten ants to generate ten different solutions in the antsequence generation step. An ant solution is generated in the following two phases:
Trail intensities are used to determine the job, scheduled at position , where . Jobs are selected from the first five unscheduled jobs in the set US from the best solution. First, the cumulative trail intensity 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 . The third rule uses probability to 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 antschedules generated by the last step and improve the solution quality. The local search is evaluation using a modified objective function , 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 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. Let and denote the objective function value for the current sequence and the best sequence, respectively. L is the trail intensity deposit from the current sequence and the trail intensity deposit from the best sequence can be calculated using the following equations:
Using the abovementioned expressions, the trail intensities are updated by the following equations:
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 swarmbased 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 n^{th} 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: : amount of soil carried at position i, if water flows through job j : amount of soil carried by water drop k : the velocity of water drop k at time t iwd: number of water drops
The fundamental procedures of the IWD algorithm are listed below, followed by a detailed description. Step 1: initialize variables , , and Step 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 all water drops(ii)Carry out the local search to improve the solution for all water drops(iii)Update the best solution found so far(iv)Update the global soil Step 3: report the best solution as a final solution of ACO
The 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:
4.3.1. Solution Construction
A solution of a singlemachinescheduling problem consists of finding the jobs for each position of the sequence. A water drop k starts with the first position and moves towards the n^{th} position. The sequence of jobs determines the path of the water drop. The IWD algorithm selects the job j from the unscheduled job set for sequencing at position i using the following probability distribution formula:where
After selecting the job j for sequencing at position i, the following variables are updated:
Here, are 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 Subsection 4.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 among iwd solutions. Let represent the objective function of the local best solution. The global soil value is updated as follows:where 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 programmingbased 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 is generated as , where was assigned randomly between 0.4 and 0.6.
The due date of each job is generated in the uniform distribution range of . The value of the release date of each job is generated according to the formula, as . 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 algorithms
The 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 mediumsize 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 calculate of the proposed algorithm or CPLEX result for the problem instance is
Here, represents the proposed metaheuristic solution in problem instance, and represents the best algorithm solution in the problem instance.
The following notations are used to report and evaluate the numerical results: CPLEX: mathematical model solved by CPLEX solver OBJ: absolute value of objective function generated by algorithms RPD: relative percentage of deviation CPU: running time of the proposed algorithm ACO: ant colony algorithm IWD: intelligent water drop algorithm
5.1. Numerical Experiment with a Small and Medium Dataset
We compare the projected ant colony optimizationbased metaheuristic results with the result of CPLEX. Tables 3–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.




The proposed ACO and IWD algorithm can efficiently solve small problem instances and balance CPU time with result quality. It is clear from Tables 3–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.

The experiment’s purpose with smallsized 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 Tables 8–11.




The results reported in Tables 8–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 singlemachine with twoagent 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 ACObased 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 nearoptimal 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.
Data Availability
Data used in this research work are available from Yuvraj Gajpal (yuvraj.gajpal@umanitoba.ca).
Conflicts of Interest
The authors declare that they have no conflicts of interest.
Acknowledgments
This research is partially supported by NSERC, grant 318689.
References
 Y. Feng, M. Zhou, G. Tian et al., “Target disassembly sequencing and scheme evaluation for CNC machine tools using improved multiobjective ant colony algorithm and fuzzy integral,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 49, no. 12, pp. 2438–2451, 2018. View at: Google Scholar
 Y. Feng, Y. Gao, G. Tian, Z. Li, H. Hu, and H. Zheng, “Flexible process planning and endoflife decisionmaking for product recovery optimization based on hybrid disassembly,” IEEE Transactions on Automation Science and Engineering, vol. 16, no. 1, pp. 311–326, 2018. View at: Google Scholar
 Q. Zhu, Y. Qiao, and N. Wu, “Optimal integrated schedule of entire process of dualblade multicluster tools from startup to closedown,” IEEE/CAA Journal of Automatica Sinica, vol. 6, no. 2, pp. 553–565, 2019. View at: Publisher Site  Google Scholar
 K. R. Baker and J. Cole Smith, “A multiplecriterion model for machine scheduling,” Journal of Scheduling, vol. 6, no. 1, pp. 7–16, 2003. View at: Publisher Site  Google Scholar
 B. Yagmahan and M. M. Yenisey, “A multiobjective ant colony system algorithm for flow shop scheduling problem,” Expert Systems with Applications, vol. 37, no. 2, pp. 1361–1368, 2010. View at: Publisher Site  Google Scholar
 K. Gao, Z. Cao, L. Zhang, Z. Chen, Y. Han, and Q. Pan, “A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems,” IEEE/CAA Journal of Automatica Sinica, vol. 6, no. 4, pp. 904–916, 2019. View at: Publisher Site  Google Scholar
 A. K. Bhardwaj, Y. Gajpal, C. Surti, and S. S. Gill, “HEART: unrelated parallel machines problem with precedence constraints for task scheduling in cloud computing using heuristic and meta‐heuristic algorithms,” Software: Practice and Experience, vol. 50, no. 12, pp. 2231–2251, 2020. View at: Publisher Site  Google Scholar
 M. J. Soomer and G. J. Franx, “Scheduling aircraft landings using airlines’ preferences,” European Journal of Operational Research, vol. 190, no. 1, pp. 277–291, 2008. View at: Publisher Site  Google Scholar
 P. J. Brewer and C. R. Plott, “A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks,” International Journal of Industrial Organization, vol. 14, no. 6, pp. 857–886, 1996. View at: Publisher Site  Google Scholar
 J. M. Peha, “Heterogeneouscriteria scheduling: minimizing weighted number of tardy jobs and weighted completion time,” Computers & Operations Research, vol. 22, no. 10, pp. 1089–1100, 1995. View at: Publisher Site  Google Scholar
 A. Agnetis, P. B. Mirchandani, D. Pacciarelli, and A. Pacifici, “Scheduling problems with two competing agents,” Operations Research, vol. 52, no. 2, pp. 229–242, 2004. View at: Publisher Site  Google Scholar
 V. Suresh and D. Chaudhuri, “Bicriteria scheduling problem for unrelated parallel machines,” Computers & Industrial Engineering, vol. 30, no. 1, pp. 77–82, 1996. View at: Publisher Site  Google Scholar
 T. C. E. Cheng, C. T. Ng, and J. J. Yuan, “Multiagent scheduling on a single machine with maxform criteria,” European Journal of Operational Research, vol. 188, no. 2, pp. 603–609, 2008. View at: Publisher Site  Google Scholar
 T. C. E. Cheng, C.Y. Liu, W.C. Lee, and M. Ji, “Twoagent singlemachine scheduling to minimize the weighted sum of the agents’ objective functions,” Computers & Industrial Engineering, vol. 78, pp. 66–73, 2014. View at: Publisher Site  Google Scholar
 C. T. Ng, T. C. E. Cheng, and J. J. Yuan, “A note on the complexity of the problem of twoagent scheduling on a single machine,” Journal of Combinatorial Optimization, vol. 12, no. 4, pp. 387–394, 2006. View at: Publisher Site  Google Scholar
 J. Y.T. Leung, M. Pinedo, and G. Wan, “Competitive twoagent scheduling and its applications,” Operations Research, vol. 58, no. 2, pp. 458–469, 2010. View at: Publisher Site  Google Scholar
 W.C. Lee, W.J. Wang, Y.R. Shiau, and C.C. Wu, “A singlemachine scheduling problem with twoagent and deteriorating jobs,” Applied Mathematical Modelling, vol. 34, no. 10, pp. 3098–3107, 2010. View at: Publisher Site  Google Scholar
 Y. Yin, S. R. Cheng, T. C. E. Cheng, W. H. Wu, and C. C. Wu, “Twoagent singlemachine scheduling with release times and deadlines,” International Journal of Shipping and Transport Logistics, vol. 5, no. 1, pp. 75–94, 2013. View at: Publisher Site  Google Scholar
 J. Yuan, “Multiagent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans,” Journal of Combinatorial Optimization, vol. 34, no. 2, pp. 433–440, 2017. View at: Publisher Site  Google Scholar
 Y. Yin, D.J. Wang, C.C. Wu, and T. C. E. Cheng, “CON/SLKdue date assignment and scheduling on a single machine with two agents,” Naval Research Logistics (NRL), vol. 63, no. 5, pp. 416–429, 2016. View at: Publisher Site  Google Scholar
 L. Wan, J. Yuan, and L. Wei, “Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost,” Applied Mathematics and Computation, vol. 273, pp. 912–923, 2016. View at: Publisher Site  Google Scholar
 B. Mor and G. Mosheiov, “A twoagent single machine scheduling problem with duewindow assignment and a common flowallowance,” Journal of Combinatorial Optimization, vol. 33, no. 4, pp. 1454–1468, 2017. View at: Publisher Site  Google Scholar
 B. Mor and G. Mosheiov, “Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents,” Journal of the Operational Research Society, vol. 65, no. 1, pp. 151–157, 2014. View at: Publisher Site  Google Scholar
 D. Lei, “Variable neighborhood search for twoagent flow shop scheduling problem,” Computers & Industrial Engineering, vol. 80, pp. 125–131, 2015. View at: Publisher Site  Google Scholar
 F. Yu, P. Wen, and S. Yi, “A multiagent scheduling problem for two identical parallel machines to minimize total tardiness time and makespan,” Advances in Mechanical Engineering, vol. 10, no. 2, p. 1687814018756103, 2018. View at: Publisher Site  Google Scholar
 H. Li, Y. Gajpal, and C. R. Bector, “A survey of duedate related singlemachine with twoagent scheduling problem,” Journal of Industrial & Management Optimization, vol. 13, no. 5, p. 1, 2019. View at: Google Scholar
 Y. Yin, D. Wang, and T. C. E. Cheng, Due DateRelated Scheduling with Two Agents, Springer, Singapore, 2020.
 Y. Yin, Y. Chen, K. Qin, and D. Wang, “Twoagent scheduling on unrelated parallel machines with total completion time and weighted number of tardy jobs criteria,” Journal of Scheduling, vol. 22, no. 3, pp. 315–333, 2019. View at: Publisher Site  Google Scholar
 R. Chen, J. Yuan, and Y. Gao, “The complexity of COagent scheduling to minimize the total completion time and total number of tardy jobs,” Journal of Scheduling, vol. 22, no. 5, pp. 581–593, 2019. View at: Publisher Site  Google Scholar
 Y. H. Zhang, Y. J. Gong, W. N. Chen, T. L. Gu, H. Q. Yuan, and J. Zhang, “A dualcolony ant algorithm for the receiving and shipping door assignments in crossdocks,” IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 7, pp. 2523–2539, 2018. View at: Google Scholar
 H. Jia, H. Miao, G. Tian et al., “Multiobjective bike repositioning in bikesharing systems via a modified artificial bee colony algorithm,” IEEE Transactions on Automation Science and Engineering, vol. 17, no. 2, pp. 909–920, 2019. View at: Google Scholar
 H. Li, Y. Gajpal, and C. R. Bector, “Single machine scheduling with twoagent for total weighted completion time objectives,” Applied Soft Computing, vol. 70, pp. 147–156, 2018. View at: Publisher Site  Google Scholar
 H. S. Hosseini, “Problem solving by intelligent water drops,” in Proceedings of the 2007 IEEE Congress on Evolutionary Computation, pp. 3226–3231, IEEE, Singapore, September 2007. View at: Google Scholar
 B. O. Alijla, L.P. Wong, C. P. Lim, A. T. Khader, and M. A. AlBetar, “A modified intelligent water drops algorithm and its application to optimization problems,” Expert Systems with Applications, vol. 41, no. 15, pp. 6555–6569, 2014. View at: Publisher Site  Google Scholar
 M. Dorigo and G. Di Caro, “Ant colony optimization: a new metaheuristic,” in Proceedings of the 1999 Congress on Evolutionary Computation CEC 99, San Diego, CA, USA, July 1999. View at: Google Scholar
 D. Maruthanayagam and D. R. U. Rani, “Enhanced ant colony system based on the RASA algorithm in grid scheduling,” IJCSIT) International Journal of Computer Science and Information Technologies, vol. 2, no. 4, pp. 1659–1674, 2011. View at: Google Scholar
Copyright
Copyright © 2020 Hongwei Li et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.