# Two-Agent Single Machine Order Acceptance Scheduling Problem to Maximize Net Revenue

Authors: Jiaji Li; Yuvraj Gajpal; Amit Kumar Bhardwaj; Huangen Chen; Yuanyuan Liu
Journal: Complexity
 (2021)

---

## Abstract

The paper considers two-agent order acceptance scheduling problems with different scheduling criteria. Two agents have a set of jobs to be processed by a single machine. The processing time and due date of each job are known in advance. In the order accepting scheduling problem, jobs are allowed to be rejected. The objective of the problem is to maximize the net revenue while keeping the weighted number of tardy jobs for the second agent within a predetermined value. A mixed-integer linear programming (MILP) formulation is provided to obtain the optimal solution. The problem is considered as anNP-hard problem. Therefore, MILP can be used to solve small problem instances optimally. To solve the problem instances with realistic size, heuristic and metaheuristic algorithms have been proposed. A heuristic method is used to determine and secure a quick solution while the metaheuristic based on particle swarm optimization (PSO) is designed to obtain the near-optimal solution. A numerical experiment is piloted and conducted on the benchmark instances that could be obtained from the literature. The performances of the proposed algorithms are tested through numerical experiments. The proposed PSO can obtain the solution within 0.1% of the optimal solution for problem instances up to 60 jobs. The performance of the proposed PSO is found to be significantly better than the performance of the heuristic.


---

## Body

## 1. Introduction

Order acceptance scheduling has been studied by researchers for the last few decades. In many cases, the number of orders accepted by a firm is not necessarily positively related to its profit, especially, when the capacity is bounded. Firms need to reject some of the orders to maximize their profit when the associated costs for some of the orders exceed their revenues. Accepting orders without a sensible and logical consideration might have a directly proportionate impact on the increase in workload. When the workload is excessively heavy, compared to the capacity of the firm, it might incur late deliveries of orders, therefore decreasing the level of customer satisfaction or even losing important customers. Hence, the study having order acceptance as its core focus has grabbed the attention of many researchers.In the field of scheduling, researchers considered order acceptance in the last few decades. In the scheduling problem, decision-makers need to decide which jobs to be processed and what will be the sequence of the accepted jobs (Li et al. [1]). There is a trade-off between the revenues and penalty function while deciding acceptance or rejection of the jobs. There are always some penalty functions available, related to the due dates, such as lateness and tardiness, which are worth looking into, depending on the scenario requirement. The order acceptance scheduling problem aims to maximize the profit gained by the revenues of accepted orders minus the specific penalty function.So far, many researchers have tried to apply the study to the order acceptance problems, testing its usefulness in multiagent settings. In the multiagent scheduling problem, the jobs of two agents with conflicting objectives are processed by common resources (Gajpal and Li [2]; Li et al. [3]). The objectives of the order acceptance scheduling problem and multiagent scheduling problem are similar. Both refer to the construction of the settings for more explicitly specified conditions. The paper of Reisi-Nafchi and Moslehi [4] depicts a more practical application portraying the combination of the order acceptance with multiagent scheduling problems. In their research, they formulated a mathematical model for their problem and proposed a hybrid genetic algorithm to solve this problem.Inspired by the work of Reisi-Nafchi and Moslehi [4], this paper extends their study, highlighting the following three perspectives: (1) propose a new variant of the two-agent order acceptance scheduling problem; (2) propose a mathematical model for the new variant of the problem; and (3) design algorithms that can be used to solve both versions of the problem. This paper focuses on two problems named as lateness penalty problem (LPP) and the tardiness penalty problem (TPP). The LPP problem is proposed by Reisi-Nafchi and Moslehi [4]; however, the TPP problem has been introduced in this paper, for the very first time. Both problems are the two-agent single machine order acceptance scheduling problems but their objective functions are different. The objective function of both problems considers how to maximize the net revenue of the first agent, subject to an upper bound on the weighted number of tardy jobs for the second agent. The net revenue is calculated as revenue from the accepted jobs subtracted by the penalty function. Penalty functions take the punishment by decreasing the objective function value when job processes after their due dates. The penalty value of the LPP problem is the weighted lateness of the first agent while the penalty value of the TPP problem is the weighted tardiness of the first agent.To solve these problems, one metaheuristic and one heuristic algorithm have been introduced. A mathematical model based on MILP formulation is developed to find the optimal solution for the problem. The MILP formulation can solve only small size problem instances because the CPU time for solving MILP formulation increases exponentially with the size of the problem. To solve the problem instances with realistic size, heuristic and metaheuristic algorithms have been proposed.The scheduling problem considered in this paper could be applied to the following scenario. A restaurant provides service to two kinds of customers: (1) customers who dine in the restaurant and (2) customers who order take-out services. Jobs in this scheduling problem are the dishes to be served to the customers. The two types of customers are treated as two agents. During the rush hours, the restaurant could not accept all the orders. Thus, it needs to reject some of the orders based on the profitability of the orders. The objective of the restaurant is to maximize the net revenue coming from all the orders while the weighted number of tardy jobs from the take-out customers could not exceed the upper bound. Also, the problem considered in this paper has many practical applications in the manufacturing industry as well as in the service industry. One of the applications that fall under this paper’s criteria is the cloud-computing environment (Bhardwaj et al. [5]). In the cloud-computing environment, the service provider accepts the order of processing jobs from different users along with his own jobs. The service provider can be considered as an agent A and all other users combined can be considered as an agent B. The objective of the cloud-computing service provider is to maximize the net revenue from all the accepted jobs, while the weighted number of tardy jobs from all other users is kept within a predefined limit set by the management.The remainder of the paper is organized as follows. Related work is reviewed inSection 2. A detailed description of the problems and the problem formulation is presented in Sections 3 and 4. The proposed algorithms are described in Section 5. Numerical results performed in Section 6 are used for comparing the effectiveness of the proposed algorithms. Eventually, Section 7 presents a summary of this paper.


## 2. Literature Review

Guerrero and Kern [6] are the pioneers in the study of order acceptance problems. They pointed out the importance of selecting a proper number of orders instead of accepting orders without any sensible cogitation. Pourbabai [7] first developed a mathematical model to help the manufacturers select the orders among all the orders. Slotnick and Morton [8] worked on an order acceptance problem in a single machine environment, of which the objective is the revenues minus weighted lateness penalties. They proposed an exact algorithm (branch and bound) and two heuristics to solve the problem. Ghosh [9] extended the work of Slotnick and Morton [8] by providing the NP-hardness proof of the problem. Also, they provided two pseudopolynomial algorithms to solve the problem, along with a fully polynomial-time approximation scheme. Lewis and Slotnick [10] worked on a multiperiod order acceptance scheduling problem in which decisions on order acceptance are made through different periods. They assume that job rejection leads to the loss of customers, and the profitability of decisions is scrutinized and assessed over each period. They proposed a dynamic programming algorithm and some heuristics to solve the problem. Slotnick and Morton [11] considered another order acceptance scheduling problem by replacing the penalty function with weighted tardiness. Rom and Slotnick [12] applied a genetic algorithm to solve the order acceptance scheduling problem with tardiness revenues.Many researchers added variants to the order acceptance scheduling problem. Charnsirisakskul et al. [13] studied a single machine order acceptance problem with job preemption. Oǧuz et al. [14] considered sequence-dependent setup times in their problem and arbitrarily assigned deadlines to the orders. Zhong et al. [15] added the variant of machine availability to order acceptance scheduling problems, in which jobs could only be processed during specific time intervals due to the availability of the machines. When the workload is heavier than the capacity, manufacturers should decide either to reject or to outsource some of the orders. Xiao et al. [16] worked on an order acceptance scheduling problem in a permutation flow shop environment. They formulated their problem into an integer-programming problem and applied simulated annealing based on partial optimization to solve the problem. Lei and Guo [17] considered an order acceptance problem in a workshop environment. They contrived, putting together this particular problem and blending it into a mixed-integer programming problem, and applied the parallel neighborhood search algorithm to it.There are some studies on order acceptance scheduling with bicriteria objectives. Lei and Guo [17] considered the objective of maximizing total net revenue and minimization of makespan simultaneously. Ou and Zhong [18] worked on a bicriteria order acceptance scheduling problem, with upper bounds on the number of the rejected job as well as the total processing time of accepted jobs. Noroozi et al. [19] considered order accepting criteria in a third-party logistic distribution system. They analyzed the trade-off among accepted orders revenue, delivery cost, and tardiness penalty in integrated production-distribution to maximize benefit. Silva et al. [20] considered an order acceptance scheduling problem with sequence-dependent setup time to maximize profit. They solved the problem using the Lagrangian relaxation and column generation-based branch and bound method. Sarvestani et al. [21] addressed an integrated order acceptance, supplier selection, and scheduling problem to maximize profit. They used genetic algorithm (GA) and variable neighborhood search (VNS) to solve the problem. Li and Ventura [22] considered a single-agent single machine scheduling problem with order acceptance criteria to maximum profit. The profit function considers the revenue minus the tardiness penalty. Recently, order acceptance criteria are combined with different settings/environments such as parallel machine setting (Wang and Ye [23]; Wu et. al [24]; Palakiti et al. [25]); carbon reduction environment (Chen et al. [26]); cluster supply chain environment (Li et al. [27]); production system (Wang et al. [28]; Yavari et al. [29]); and dynamic environment (Li et al. [30]; Melchiors et al. [31]). The increasing number of research articles in the order accepting criteria under different settings shows the importance and popularity of order acceptance scheduling problems.The article by Reisi-Nafchi and Moslehi [4] is the closely related model considered in this paper. They integrated the two-agent scheduling situation into the order acceptance scheduling problem to maximize the net revenues from the first agent, subject to an upper bound of a weighted number of tardy jobs from the second agent. The net revenue is considered as a revenue of accepted orders with a penalty of total weighted lateness of accepted jobs. They provided an integer-programming formulation and hybrid genetic algorithm to solve the problem. This paper extends the work of Reisi-Nafchi and Moslehi [4] by introducing a new variant of the order acceptance criteria in the “two agents scheduling” setting. The literature review also stipulates the common trend of using metaheuristics to solve the scheduling problem. This observation has motivated us to develop and incorporate a metaheuristic algorithm to solve our problem.


## 3. Problem Definition and Notations

This paper considers a single machine scheduling problem with two agents, namely, agentA and agent B. Each of the agents has a job set nx to be processed in a single machine. The processing time pi, weight wi, due date Di , and revenue Ri associated with the job i are known. All the jobs are available at time zero (i.e., the release time is zero). A single machine processes all the jobs and at a time only one job is processed. Once a machine has started processing a job, it will continue running on that job until the job is completed. The problem seeks to determine the sequence of jobs σ. For a given sequence σ, the complete time Ciσ of accepted job i can be calculated by the summation of processing time of all the jobs (including job i) sequenced before job i. The lateness value Li of the job is defined as a difference between completion time and due date (i.e., Li=Ciσ−Di). The lateness value is positive if the job is completed after its due date. On the other hand, the lateness value is negative if the job is completed before the due date. Slotnick and Morton [8] introduced the lateness penalty to capture the penalty and reward in one function. Finishing a job late incurs a penalty in terms of loss of goodwill while finishing the job early incurs an appreciation from the customer. However, in many situations, only late completion incurs a penalty and the early completion does not bring any appreciation. This situation is captured in a tardiness value which only measures the delay in the completion time of a job (i.e., Ti=Max0,Ciσ−Di). The existing literature studies the order acceptance scheduling problem in which lateness penalizes revenue obtained from the accepted jobs. This paper introduces a new order acceptance scheduling problem variant in which tardiness penalizes revenue received from the accepted jobs. The summary of notations used in this paper is summarized as follows:(i)
X: set of agents X = {A, B}(ii)
nx: the number of jobs for agent x∈X(iii)
n: total number of jobs, n=nA+nB(iv)
N: set of all n jobs, N=1,2,…,n(v)
NA: set of A jobs, consisting of nA jobs, NA=1,2,…,nA(vi)
NB: set of B jobs, consisting of nB jobs, NB=nA+1,nA+2,…,n(vii)
pi: the processing time of job i(viii)
Ri: revenue of job i(ix)
wi: weight of job i(x)
Di: due date of job i(xi)
σ: ordered set of jobs already scheduled(xii)
Ciσ: completion time of accepted job i under sequence σ.(xiii)
fxσ: objective function of agent x∈X under sequence σ.(xiv)
Yi: binary decision variable taking value 1 if job i is accepted(xv)
Ui: binary decision variable taking value 1 if job i is tardy(xvi)
Zij: binary decision variable taking value 1 if job i precedes job j(xvii)
Ti: decision variable representing tardiness of the job i(xviii)
Li: decision variable representing lateness of the job i(xix) (xx)
Q: the upper bound, a constant numberbigM: a large numberThis paper showcases an attempt to maximize the net revenue subject to an upper bound of agent B. We consider two versions of the order acceptance two-agent scheduling problems, theLPP problem and the TPP problem. The objective of the LPP problem is to maximize the net revenue from all the accepted orders subtracted by the total weighted lateness from the accepted jobs of agent A, subject to an upper bound of the total weighted number of tardy jobs from agent B. In the scheduling terminology, this problem can be represented as 1|OA,∑i∈NBwiUiYi≤Q|∑i∈NRiYi−∑i∈NAwiLiYi. The term OA is used for order acceptance. The objective of the TPP problem is to maximize the net revenue from all the accepted orders subtracted by the total weighted tardiness from the accepted jobs of agent A, subject to an upper bound of the total weighted number of tardy jobs from agent B. This problem can be represented as 1|OA,∑i∈NBwiUiYi≤Q|∑i∈NRiYi−∑i∈NAwiTiYi.The computational complexity of theLPP problem is proved to be NP-hard by Reisi-Nafchi and Moslehi [4]. They showed that the LPP problem is a special case 1|∑i∈NBwiUi≤Q|∑i∈NAwiLi; therefore, the LPP problem is also an NP-hard problem. The TPP problem reduces to 1|∑i∈NBwiTi when Q is set to infinite. Since 1|∑i∈NBwiTi is NP-hard, the TPP problem is also an NP-hard problem.


## 4. Problem Formulation

Reisi-Nafchi and Moslehi [4] formulated the LPP problem into an integer-programming mathematical model. Based on their formulation, we have brought forward an evolved version of the paper, which is developed as an integer-programming model for the TPP problem.When formulating the mathematical model for theTPP problem, a new binary variable Zij is introduced, which denotes the relative position between jobs i and j. The binary variable Zij takes the value of 1 if job i precedes job j, otherwise zero. It is significant to note here that the precedence here is not the immediate precedence (i.e., Zij takes the value of 1; this does not mean that job i and job j are adjacent to each other). Using the above notations, the TPP problem can be formulated as follows:(1)Max∑i∈NRiYi−∑i∈NAwiTi,(2)subject toYi+Yj≤1+Zij+Zji,i,j∈N,i<j,(3)Yi+Yj≥2Zij+Zji,i,j∈N,i<j,(4)Zik+Zkj+Zjk≤2,i,j,k∈N,i≠j,j≠k,i≠k,(5)Ti≥∑j∈NpjZji+piYi−Di,i∈NA,(6)Ti≥0,i∈NA,(7)∑j∈NpjZji+piYi≤DiYi+BigM×Ui,i∈NB,(8)∑j∈NBwjUj≤Q,(9)Ui∈0,1,i∈NB,(10)Yi∈0,1,i∈N,(11)Zij∈0,1,i,j∈N.Equation (1) represents the objective function of the TPP problem, which is the total revenue of all the accepted orders penalized by the weighted tardiness of agent A orders. Constraints (2)–(4) determines the relative positions of jobs. Constraint (2) requires that a job i must precede another job j if both jobs are accepted. Constraint (3) sets the value of Zij or Zji to zero when job i or j is rejected, preventing the situation that Zij and Zji both are equal to zero. Constraint (4) ensures that there are no job loops in the sequence. Job loop represents a situation in which job i precedes job j, job j precedes job k, and job k precedes job i, which is logically wrong. Constraints (5) and (6) determine the tardiness value for job i. Constraint (7) determines the value of Ui. Constraint (8) ensures that the upper bound of the weighted number of tardy jobs from agent B is not exceeding. Constraints (9)–(11) impose the binary values for binary decision variables Ui,Yi, and Zij.Some of the optimal solution property of theLPP problem also holds true for TPP problem. The TPP problem satisfies the following three lemmas for which proof can be found in the work of Reisi-Nafchi and Moslehi [4].Lemma 1.
There exists an optimal sequence, in which the agent B tardy accepted orders are sequenced arbitrarily at the end of the sequence.Lemma 2.
There exists an optimal sequence, in which the global arrangement of the agent B nontardy accepted orders follows the earliest due date (EDD) order and they are placed at the last possible positions before their due dates.Lemma 3.
There exists an optimal sequence, in which the adjacent orders of agent A follow the weighted shortest processing time (WSPT) order.


## 5. Proposed Algorithms

In this section, algorithms including a heuristic and PSO are the proposed approaches to resolve theLPP and TPP problems.


### 5.1. Heuristic Algorithm

The proposed heuristic is based on theWSPT and EDD rule. In the WSPT rule, jobs are sequenced in nondecreasing order of the pi/wi ratio. In the EDD rule, jobs are sequenced in nondecreasing order of their due dates Di. The WSPT rule minimizes the total weighted completion time while the EDD rule minimizes the total tardiness objective for a single machine and a single-agent setting.The heuristic first creates partial schedulesσA and σB for A and B types of jobs according to WSPT and EDD rules, respectively. The sequence σA is modified by removing unprofitable jobs. The sequence σB is divided into two subsequences σBE and σBL for an early and late set of the jobs. The final sequence σ is created by first sequencing σA , then σBE , and finally σBL. If the resultant sequence σ is infeasible, then the jobs from the sequence σ are removed one by one to make the solution feasible. The pseudocode of the proposed heuristic algorithm is presented as follows (Algorithm 1).Algorithm 1: Heuristic algorithm.
(1)
/∗ Initial Solution ∗/(2)
Create a sequenceσA for A jobs according to the WSPT rule(3)
fork = 1 to n1do(4)
Select jobi=σAk(5)
ifRi<wi×Ciσ−Dithen(6)
Remove jobi from sequence σA(7)
end if(8)
end for(9)
Create a sequenceσB for B jobs according to the EDD rule(10)
Create null sequencesσBE=ϕ and σBL=ϕ(11)
fork = 1 to n2do(12)
Select jobi=σBk(13)
ifCiσA+pi<=Dithen(14)
append jobi in sequence σBE(15)
else(16)
append jobi in sequence σBL(17)
end if(18)
end for(19)
UpdateσBL by arranging jobs in nondecreasing order of Ri/wi ratio(20)
Create initial sequenceσ=σA∪σBE∪σBL(21)
/∗ Feasibility phase ∗/(22)
Uσ⟵fBσ //Calculate the weighted number of tardy jobs for σ(23)
fork = 1 to ndo(24)
ifUσ≤Qthen(25)
breakk loop(26)
end if(27)
σ⟵Update sequence by removing first job(28)
Uσ⟵fBσ //Calculate the weighted number of tardy jobs for σ(29)
end for(30)
return solutionσThe computational complexity of the proposed algorithm can be described as follows. The initial solution generation has four separate subprocesses: (1) sequence of A jobs with complexityOn12; (2) sequence of B jobs with complexity On22; (3) split of the sequence of B jobs with complexity On2; and (4) resequencing of late B jobs with complexity On22. Thus, the overall complexity of the initial solution process is On12+On22+On2+On22=On12+On22. The feasibility phase requires the maximum removal of n jobs and after each removal, it requires objective function calculation which can be performed in On time. Thus, the feasibility phase can be performed in On2 time. Therefore, the overall complexity of the heuristic algorithm is On12+On22+On2=On2.


### 5.2. Particle Swarm Optimization

Particle swarm optimization (PSO) is a metaheuristic technique for solving NP-hard problems. PSO is derived from the social behavior of fish and birds. In this algorithm, individual solutions are updated by the other members of the group. Although PSO applies to many scheduling problems, there are some challenges while applying it to solve a specific problem. The main challenge for this algorithm is to design a solution representation mechanism [32, 33] for the particular problem. In other words, this refers to the mechanism, which establishes the rules to interpret the data of particles into an actual schedule. Additional efforts are required to make it pertinent to the order acceptance scheduling problems because two subproblems are residing within it. While the first subproblem determines the set of accepted jobs, the objective of the second subproblem is to find the sequence for the accepted jobs. Therefore, a PSO algorithm containing parallel parameters of position values and velocities has been proposed. It is difficult for the classical PSO with only one group of parameters to solve the problems in this paper; two groups of position values and velocities are embedded in the algorithm. The first group focuses on the selection of accepted jobs, and the second group focuses on finding the sequence of the accepted jobs. Each particle in PSO has n dimensions representing n jobs. Let Xj1 and Xj2 represent the position value vector related to the order acceptance decision making and the job sequencing, respectively. The following are the notations that we have employed to describe the proposed PSO algorithm:(i)
m: number of particles(ii)
k: iterations index(iii)
K: maximum number of iterations(iv)
xij1: position value of ith particle in jth dimension for order acceptance criteria(v)
Xi1: position vector of ith particle for order acceptance criteria(vi)
vij1: velocity value of ith particle in jth dimension for order acceptance criteria(vii)
Vi1: velocity vector of ith particle for order acceptance criteria(viii)
xij2: position value of ith particle in jth dimension for job sequencing criteria(ix)
Xi2: position vector of ith particle for job sequencing criteria(x)
vij2: velocity value of ith particle in jth dimension for job sequencing criteria(xi)
Vi2: velocity vector of ith particle for job sequencing criteria(xii) (xiii)
pbij: personal best position value of ith particle in jth dimension for job sequencing criteriagbj: global best position value in jth dimension for job sequencing criteria(xiv)
SiPB: personal best solution vector for ith particle(xv)
SG: global best solution(xvi)
w: inertia weight(xvii)
c1,c2: social cognitive numbersThe pseudocode of the proposed PSO algorithm is as follows (Algorithm2).Algorithm 2: PSO algorithm.
(1)
Initialization(2)
Setk = 0, m = 50, c1 = 0.8, c2 = 0.8, w=0.9(3)
InitializeXi1,Vi1,Xi2,Vi2(4)
Main phase(5)
do while (k≤K)(6)
k = k + 1(7)
fori = 1 to m do(8)
σi← Generate sequence Xi1,…,Xm1,Xi2,…,Xm2(9)
σi← Local search(σi)(10)
UpdateSG and SiPB, ∀i=1,…,m(11)
UpdateXi1,Xi2,Vi1,Vi2,∀i=1,…,m(12)
end for(13)
end do(14)
return solutionSG


#### 5.2.1. Parameter Initialization

At the beginning, parameters are generated using the following equations:(12)xij1=Xmin1+Xmax1−Xmin1×U0,1,vij1=Vmin1+Vmax1−Vmin1×U0,1,xij2=Xmin2+Xmax2−Xmin2×U0,1,vij2=Vmin2+Vmax2−Vmin2×U0,1,where Xmax1,Vmax1,Xmax2,Vmax2 are equal to 4; Xmin1,Vmin1,Xmin2,Vmin2 are equal to −4. U0,1 is a random number within the range of [0, 1]. Therefore, all these parameters remain within the range of [−4, 4] and the same is maintained throughout the algorithm.


#### 5.2.2. Sequence Generator

As mentioned above, the sequence generating process in the proposed PSO consists of two steps. The first step is to decide and govern the accepted jobs and the second step decides the sequence of the accepted jobs. Jobj in particle i is accepted when xij1 is greater than 0; otherwise, it is rejected. Jobs are sequenced according to the minimum position value (MPV) rule, which specifies that the jobs are ordered in nondecreasing order of their position values xij2.


#### 5.2.3. Updating Parameters

Parameters are updated at the end of each iteration. Before updating the parameter, the personal best solutionSipb and the personal best position value pbij for each particle are updated. If the new solution σi is found to be better than Sipb, then the personal best solution Sipb is replaced by the current solution σiand the personal best position value pbij is replaced by the position value xij2. Similarly, the global best solution and the global best position values are updated. Two different ways are applied for updating job sequencing and order accepting criteria. The order acceptance parameters as updated as follows:(13)vij1=w×vij1+c1×r1×z1+c2×r2×z2,xij1=xij1+vij1.Parameters ofz1 and z2 are variables representing the status of job j. Variable z1 takes the value of 1 when job j in ith particle is accepted in personal best solution; otherwise, it takes the value of −1. Likewise, the value of the variable z2 is determined by whether the job is accepted in the global best solution or not. Parameters of c1 and c2 are the social coefficients quantifying the extent to which an individual relies on its experiment (i.e., to its own personal best or to the global best). Inertia w is the resistance of any physical object to any change in the state of motion. It controls the velocity and direction of all the particles. Variables of r1 and r2 are random numbers within the range of [0, 1]. In this paper, we set c1=0.9,c2=0.9,w=0.9. The job sequencing parameters are updated as follows:(14)vij2=w×vij2+c1×r1×pbij−xij2+c2×r2×gbij−xij2,xij2=xij2+vij2.


#### 5.2.4. Local Search

There are two types of local search schemes proposed to improve the solution of each particle. These two local search schemes are named as anaccepted job insertion local search (AJILS) and a rejected job insertion local search (RJILS). The AJILS tries to improve the solution by repositioning the accepted jobs to a different position. At first, the job is removed from its original position, and then it was reinserted in all the other positions. The best-inserted position is selected for the insertion of the job and the resultant solution is used for further evaluation. All the accepted jobs are selected one by one for possible solution improvement. The RJILS attempts to insert the rejected jobs into the solution. The rejected jobs are inserted in the best feasible position if it improves the objective function value. All the rejected jobs are singled out one by one for possible solution improvement.


#### 5.2.5. Normalization of Parameters

The absolute values of parameters tend to be very large after many iterations, enabling the solutions to get stuck in the local optimum. Thus, the parameters are normalized after each iteration. The parameters exceeding the upper limit are forced to take a value of 4, and the parameters that are less than the lower limit are forced to take the value of −4.


#### 5.2.6. Computational Complexity of the PSO

The three main components of the PSO algorithm are (1) sequence generation step, (2) local search method, and (3) parameter updating step. In the sequence generation step, determining the set of accepted and rejected jobs can be performed inOn time while the sequencing operation can be performed in On2 time. Thus, the overall complexity of the sequence generation step is On2. The local search uses the two schemes with the complexity of n2 for each scheme. Thus, the overall complexity of the local search scheme is On2. The parameter updating can be performed in On time. Thus, the complexity of one iteration of PSO is On2+On2+On=On2. The PSO performs K iterations, which brings the overall complexity of the PSO to be OKn2.


## 5.1. Heuristic Algorithm

The proposed heuristic is based on theWSPT and EDD rule. In the WSPT rule, jobs are sequenced in nondecreasing order of the pi/wi ratio. In the EDD rule, jobs are sequenced in nondecreasing order of their due dates Di. The WSPT rule minimizes the total weighted completion time while the EDD rule minimizes the total tardiness objective for a single machine and a single-agent setting.The heuristic first creates partial schedulesσA and σB for A and B types of jobs according to WSPT and EDD rules, respectively. The sequence σA is modified by removing unprofitable jobs. The sequence σB is divided into two subsequences σBE and σBL for an early and late set of the jobs. The final sequence σ is created by first sequencing σA , then σBE , and finally σBL. If the resultant sequence σ is infeasible, then the jobs from the sequence σ are removed one by one to make the solution feasible. The pseudocode of the proposed heuristic algorithm is presented as follows (Algorithm 1).Algorithm 1: Heuristic algorithm.
(1)
/∗ Initial Solution ∗/(2)
Create a sequenceσA for A jobs according to the WSPT rule(3)
fork = 1 to n1do(4)
Select jobi=σAk(5)
ifRi<wi×Ciσ−Dithen(6)
Remove jobi from sequence σA(7)
end if(8)
end for(9)
Create a sequenceσB for B jobs according to the EDD rule(10)
Create null sequencesσBE=ϕ and σBL=ϕ(11)
fork = 1 to n2do(12)
Select jobi=σBk(13)
ifCiσA+pi<=Dithen(14)
append jobi in sequence σBE(15)
else(16)
append jobi in sequence σBL(17)
end if(18)
end for(19)
UpdateσBL by arranging jobs in nondecreasing order of Ri/wi ratio(20)
Create initial sequenceσ=σA∪σBE∪σBL(21)
/∗ Feasibility phase ∗/(22)
Uσ⟵fBσ //Calculate the weighted number of tardy jobs for σ(23)
fork = 1 to ndo(24)
ifUσ≤Qthen(25)
breakk loop(26)
end if(27)
σ⟵Update sequence by removing first job(28)
Uσ⟵fBσ //Calculate the weighted number of tardy jobs for σ(29)
end for(30)
return solutionσThe computational complexity of the proposed algorithm can be described as follows. The initial solution generation has four separate subprocesses: (1) sequence of A jobs with complexityOn12; (2) sequence of B jobs with complexity On22; (3) split of the sequence of B jobs with complexity On2; and (4) resequencing of late B jobs with complexity On22. Thus, the overall complexity of the initial solution process is On12+On22+On2+On22=On12+On22. The feasibility phase requires the maximum removal of n jobs and after each removal, it requires objective function calculation which can be performed in On time. Thus, the feasibility phase can be performed in On2 time. Therefore, the overall complexity of the heuristic algorithm is On12+On22+On2=On2.


## 5.2. Particle Swarm Optimization

Particle swarm optimization (PSO) is a metaheuristic technique for solving NP-hard problems. PSO is derived from the social behavior of fish and birds. In this algorithm, individual solutions are updated by the other members of the group. Although PSO applies to many scheduling problems, there are some challenges while applying it to solve a specific problem. The main challenge for this algorithm is to design a solution representation mechanism [32, 33] for the particular problem. In other words, this refers to the mechanism, which establishes the rules to interpret the data of particles into an actual schedule. Additional efforts are required to make it pertinent to the order acceptance scheduling problems because two subproblems are residing within it. While the first subproblem determines the set of accepted jobs, the objective of the second subproblem is to find the sequence for the accepted jobs. Therefore, a PSO algorithm containing parallel parameters of position values and velocities has been proposed. It is difficult for the classical PSO with only one group of parameters to solve the problems in this paper; two groups of position values and velocities are embedded in the algorithm. The first group focuses on the selection of accepted jobs, and the second group focuses on finding the sequence of the accepted jobs. Each particle in PSO has n dimensions representing n jobs. Let Xj1 and Xj2 represent the position value vector related to the order acceptance decision making and the job sequencing, respectively. The following are the notations that we have employed to describe the proposed PSO algorithm:(i)
m: number of particles(ii)
k: iterations index(iii)
K: maximum number of iterations(iv)
xij1: position value of ith particle in jth dimension for order acceptance criteria(v)
Xi1: position vector of ith particle for order acceptance criteria(vi)
vij1: velocity value of ith particle in jth dimension for order acceptance criteria(vii)
Vi1: velocity vector of ith particle for order acceptance criteria(viii)
xij2: position value of ith particle in jth dimension for job sequencing criteria(ix)
Xi2: position vector of ith particle for job sequencing criteria(x)
vij2: velocity value of ith particle in jth dimension for job sequencing criteria(xi)
Vi2: velocity vector of ith particle for job sequencing criteria(xii) (xiii)
pbij: personal best position value of ith particle in jth dimension for job sequencing criteriagbj: global best position value in jth dimension for job sequencing criteria(xiv)
SiPB: personal best solution vector for ith particle(xv)
SG: global best solution(xvi)
w: inertia weight(xvii)
c1,c2: social cognitive numbersThe pseudocode of the proposed PSO algorithm is as follows (Algorithm2).Algorithm 2: PSO algorithm.
(1)
Initialization(2)
Setk = 0, m = 50, c1 = 0.8, c2 = 0.8, w=0.9(3)
InitializeXi1,Vi1,Xi2,Vi2(4)
Main phase(5)
do while (k≤K)(6)
k = k + 1(7)
fori = 1 to m do(8)
σi← Generate sequence Xi1,…,Xm1,Xi2,…,Xm2(9)
σi← Local search(σi)(10)
UpdateSG and SiPB, ∀i=1,…,m(11)
UpdateXi1,Xi2,Vi1,Vi2,∀i=1,…,m(12)
end for(13)
end do(14)
return solutionSG


### 5.2.1. Parameter Initialization

At the beginning, parameters are generated using the following equations:(12)xij1=Xmin1+Xmax1−Xmin1×U0,1,vij1=Vmin1+Vmax1−Vmin1×U0,1,xij2=Xmin2+Xmax2−Xmin2×U0,1,vij2=Vmin2+Vmax2−Vmin2×U0,1,where Xmax1,Vmax1,Xmax2,Vmax2 are equal to 4; Xmin1,Vmin1,Xmin2,Vmin2 are equal to −4. U0,1 is a random number within the range of [0, 1]. Therefore, all these parameters remain within the range of [−4, 4] and the same is maintained throughout the algorithm.


### 5.2.2. Sequence Generator

As mentioned above, the sequence generating process in the proposed PSO consists of two steps. The first step is to decide and govern the accepted jobs and the second step decides the sequence of the accepted jobs. Jobj in particle i is accepted when xij1 is greater than 0; otherwise, it is rejected. Jobs are sequenced according to the minimum position value (MPV) rule, which specifies that the jobs are ordered in nondecreasing order of their position values xij2.


### 5.2.3. Updating Parameters

Parameters are updated at the end of each iteration. Before updating the parameter, the personal best solutionSipb and the personal best position value pbij for each particle are updated. If the new solution σi is found to be better than Sipb, then the personal best solution Sipb is replaced by the current solution σiand the personal best position value pbij is replaced by the position value xij2. Similarly, the global best solution and the global best position values are updated. Two different ways are applied for updating job sequencing and order accepting criteria. The order acceptance parameters as updated as follows:(13)vij1=w×vij1+c1×r1×z1+c2×r2×z2,xij1=xij1+vij1.Parameters ofz1 and z2 are variables representing the status of job j. Variable z1 takes the value of 1 when job j in ith particle is accepted in personal best solution; otherwise, it takes the value of −1. Likewise, the value of the variable z2 is determined by whether the job is accepted in the global best solution or not. Parameters of c1 and c2 are the social coefficients quantifying the extent to which an individual relies on its experiment (i.e., to its own personal best or to the global best). Inertia w is the resistance of any physical object to any change in the state of motion. It controls the velocity and direction of all the particles. Variables of r1 and r2 are random numbers within the range of [0, 1]. In this paper, we set c1=0.9,c2=0.9,w=0.9. The job sequencing parameters are updated as follows:(14)vij2=w×vij2+c1×r1×pbij−xij2+c2×r2×gbij−xij2,xij2=xij2+vij2.


### 5.2.4. Local Search

There are two types of local search schemes proposed to improve the solution of each particle. These two local search schemes are named as anaccepted job insertion local search (AJILS) and a rejected job insertion local search (RJILS). The AJILS tries to improve the solution by repositioning the accepted jobs to a different position. At first, the job is removed from its original position, and then it was reinserted in all the other positions. The best-inserted position is selected for the insertion of the job and the resultant solution is used for further evaluation. All the accepted jobs are selected one by one for possible solution improvement. The RJILS attempts to insert the rejected jobs into the solution. The rejected jobs are inserted in the best feasible position if it improves the objective function value. All the rejected jobs are singled out one by one for possible solution improvement.


### 5.2.5. Normalization of Parameters

The absolute values of parameters tend to be very large after many iterations, enabling the solutions to get stuck in the local optimum. Thus, the parameters are normalized after each iteration. The parameters exceeding the upper limit are forced to take a value of 4, and the parameters that are less than the lower limit are forced to take the value of −4.


### 5.2.6. Computational Complexity of the PSO

The three main components of the PSO algorithm are (1) sequence generation step, (2) local search method, and (3) parameter updating step. In the sequence generation step, determining the set of accepted and rejected jobs can be performed inOn time while the sequencing operation can be performed in On2 time. Thus, the overall complexity of the sequence generation step is On2. The local search uses the two schemes with the complexity of n2 for each scheme. Thus, the overall complexity of the local search scheme is On2. The parameter updating can be performed in On time. Thus, the complexity of one iteration of PSO is On2+On2+On=On2. The PSO performs K iterations, which brings the overall complexity of the PSO to be OKn2.


## 5.2.1. Parameter Initialization

At the beginning, parameters are generated using the following equations:(12)xij1=Xmin1+Xmax1−Xmin1×U0,1,vij1=Vmin1+Vmax1−Vmin1×U0,1,xij2=Xmin2+Xmax2−Xmin2×U0,1,vij2=Vmin2+Vmax2−Vmin2×U0,1,where Xmax1,Vmax1,Xmax2,Vmax2 are equal to 4; Xmin1,Vmin1,Xmin2,Vmin2 are equal to −4. U0,1 is a random number within the range of [0, 1]. Therefore, all these parameters remain within the range of [−4, 4] and the same is maintained throughout the algorithm.


## 5.2.2. Sequence Generator

As mentioned above, the sequence generating process in the proposed PSO consists of two steps. The first step is to decide and govern the accepted jobs and the second step decides the sequence of the accepted jobs. Jobj in particle i is accepted when xij1 is greater than 0; otherwise, it is rejected. Jobs are sequenced according to the minimum position value (MPV) rule, which specifies that the jobs are ordered in nondecreasing order of their position values xij2.


## 5.2.3. Updating Parameters

Parameters are updated at the end of each iteration. Before updating the parameter, the personal best solutionSipb and the personal best position value pbij for each particle are updated. If the new solution σi is found to be better than Sipb, then the personal best solution Sipb is replaced by the current solution σiand the personal best position value pbij is replaced by the position value xij2. Similarly, the global best solution and the global best position values are updated. Two different ways are applied for updating job sequencing and order accepting criteria. The order acceptance parameters as updated as follows:(13)vij1=w×vij1+c1×r1×z1+c2×r2×z2,xij1=xij1+vij1.Parameters ofz1 and z2 are variables representing the status of job j. Variable z1 takes the value of 1 when job j in ith particle is accepted in personal best solution; otherwise, it takes the value of −1. Likewise, the value of the variable z2 is determined by whether the job is accepted in the global best solution or not. Parameters of c1 and c2 are the social coefficients quantifying the extent to which an individual relies on its experiment (i.e., to its own personal best or to the global best). Inertia w is the resistance of any physical object to any change in the state of motion. It controls the velocity and direction of all the particles. Variables of r1 and r2 are random numbers within the range of [0, 1]. In this paper, we set c1=0.9,c2=0.9,w=0.9. The job sequencing parameters are updated as follows:(14)vij2=w×vij2+c1×r1×pbij−xij2+c2×r2×gbij−xij2,xij2=xij2+vij2.


## 5.2.4. Local Search

There are two types of local search schemes proposed to improve the solution of each particle. These two local search schemes are named as anaccepted job insertion local search (AJILS) and a rejected job insertion local search (RJILS). The AJILS tries to improve the solution by repositioning the accepted jobs to a different position. At first, the job is removed from its original position, and then it was reinserted in all the other positions. The best-inserted position is selected for the insertion of the job and the resultant solution is used for further evaluation. All the accepted jobs are selected one by one for possible solution improvement. The RJILS attempts to insert the rejected jobs into the solution. The rejected jobs are inserted in the best feasible position if it improves the objective function value. All the rejected jobs are singled out one by one for possible solution improvement.


## 5.2.5. Normalization of Parameters

The absolute values of parameters tend to be very large after many iterations, enabling the solutions to get stuck in the local optimum. Thus, the parameters are normalized after each iteration. The parameters exceeding the upper limit are forced to take a value of 4, and the parameters that are less than the lower limit are forced to take the value of −4.


## 5.2.6. Computational Complexity of the PSO

The three main components of the PSO algorithm are (1) sequence generation step, (2) local search method, and (3) parameter updating step. In the sequence generation step, determining the set of accepted and rejected jobs can be performed inOn time while the sequencing operation can be performed in On2 time. Thus, the overall complexity of the sequence generation step is On2. The local search uses the two schemes with the complexity of n2 for each scheme. Thus, the overall complexity of the local search scheme is On2. The parameter updating can be performed in On time. Thus, the complexity of one iteration of PSO is On2+On2+On=On2. The PSO performs K iterations, which brings the overall complexity of the PSO to be OKn2.


## 6. Numerical Results

This section evaluates the performance of the proposed algorithms, assessing their effectiveness and application utility on two problems. Numerical analysis is provided based on the solution and CPU time of the proposed algorithms. The proposed algorithms are coded in the C++ programming language. The numerical experiments are performed in a computer environment with AMD Opteron 2.3 GHz with 16 GB of RAM on Unix OS. The linear-programming-based mathematical model proposed for theTPP problem is solved by AMPL software with CPLEX solver, in the computer system of iMac desktop with 3.3 GHz 8 GB RAM.There are three sections in this section. The first section explains the settings of the instances used in this paper. The second section aims to test the robustness of proposed algorithms by comparing them with the existing solution of Reisi-Nafchi and Moslehi [4]. The third section evaluates the proposed algorithms on the TPP problem. The following are notations used to report and evaluate the numerical results:(i)
CPLEX: value of objective function generated by the mathematical model(ii)
ABS: absolute value of objective function generated by algorithms(iii)
ABSbest: ABS value generated by the algorithm with the best performance(iv)
APD: absolute percentage of deviation, APD=ABS−CPLEX/CPLEX∗100%(v)
RPD: relative percentage of deviation, RPD=ABS−ABSbest/ABSbest∗100%(vi)
CPU: running time of the proposed algorithmAdditionally,Avg, Min, and Max are used for representing average, minimal, maximal values of corresponding results, respectively. We also performed a paired t-test to compare the performance of the proposed algorithms at the 95% significance level. In the paired t-test, the population mean of the two methods is compared. Let μD=μ1−μ2 denote the true average difference between the average solution values of the comparing algorithms. Here, μ1 and μ2 denote the population mean of the comparing algorithms, respectively. The null hypothesis is given by H0:μD=0, which states that there is no difference between the average solution value of the algorithms. The alternative hypothesis is given by H1:μD>0 stating that the average solution of the first algorithm is greater than the average solution of the second algorithm.


### 6.1. Instance Setting

In this paper, instances generated in the study of Reisi-Nafchi and Moslehi [4] are recognized as the benchmark instances. Different algorithms are evaluated and appraised based on their performance on these benchmark instances. The setting of the benchmark instances is as follows.Processing times and weights are generated randomly from a uniform distribution within the interval of [1, 10]. When generating due dates, two additional parameters are introduced: tardiness factorτ and the range factor r. Due dates are generated randomly within the range of [TPT∗(1−τ−r/2), TPT∗(1−τ−r/2)], in which the TPT denotes the sum of processing times from all the jobs. The revenues are generated from a uniform distribution within the interval of 1,2∗pi; upper bound Q is generated within the range of 0,∑i=n1+1nwi. The instances are sorted into eight groups according to the parameter setting, the sizes of instances ranging from 20 to 150. In the first four groups, n1=2n2; in the remaining groups, 2n1=n2. Parameter of τ takes the value of 0.3 in the groups of G01, G02, G05, and G06, and it takes the value of 0.7 in the groups of G03, G04, G07, and G08. The parameter of r takes the value of 0.2 in groups of G01, G03, G05, and G07. In the benchmark instances, there are 1280 instances in total and 20 instances for each parameter setting. The numerical analysis is primarily focused on the average results, which could be obtained from a varied set of results in different parameter settings.


### 6.2. Numerical Analysis for theLPP Problem

As mentioned above, the performance of PSO and heuristic is compared and weighed against the results in Reisi-Nafchi and Moslehi [4]. The numerical results of GA and CPLEX solution in Reisi-Nafchi and Moslehi [4] are obtained from the authors. In small instances, the performance of these algorithms along with the GA algorithm is compared with the CPLEX solution, while in large instances, the illustrations include the performance of PSO, heuristic, and GA being compared with each other. It is noteworthy that the CPU time of the heuristic is not shown in the corresponding tables since the proposed heuristic algorithm itself could solve all of the instances within 0.1 seconds.Table1 displays the computational results of integer-programming formulation. According to the results, it could be seen that the existing mathematical model could solve problem instances with up to 60 jobs. It could also be seen that the CPU time of G03 and G07 is significantly longer than other groups, when τ=0.3 and r=0.6. The maximum CPU time in these groups exceeds 1000 seconds, indicating that it is more difficult for the system to search for the optimal solutions in these groups. The results further indicate that the CPU time of the CPLEX solver increases exponentially and thus the larger problem instances cannot be solved using the CPLEX solver. Therefore, heuristic and metaheuristic algorithms are used to solve bigger problem instances.Table 1
CPU time of CPLEX solutions in theLPP problem.
GroupnCPUAvgMinMaxG01200.090.020.98300.370.073.27401.50.187.53601.510.4115.63G02200.030.020.15300.080.060.1400.220.170.3600.40.310.64G03200.390.021.18304.30.0915.074028.780.24121.7560308.440.531314.29G04200.070.020.64300.340.071.464010.174.596011.70.48138.64G05200.060.020.4301.450.1412.28401.160.163.856027.340.76201.91G06200.040.020.11300.40.131.93400.220.120.64601.770.588.1G07200.320.080.98304.510.5516.784035.920.48200.7360519.6223.011442.53G08200.060.020.48300.430.081.88400.830.173.21607.330.5988.78Table2 reports the APD values of the three algorithms for the LPP problem. As shown in the table, the PSO algorithm performs best in small instances in terms of the solution quality. The solutions of PSO are only 0.01 percent away from the CPLEX solutions. Besides, the maximal APD of PSO is lower than 0.1%, which is lower than other algorithms. On the other hand, though the heuristic deviates furthest from CPLEX solutions, the average APD of the heuristic is lower than 1.5%. This observation also indicates the effectiveness of the heuristic algorithm in solving the small problem instances.Table 2
Comparison of algorithms ofLPP problem in small instances.
GroupnGAHeuristicPSOAverage ABSAverage APDAverage CPU timeAverage ABSAverage APDAverage ABSAverage APDAverage CPU timeG01202518.3000.942517.600.032518.3500.56305682.550.021.955680.750.055683.3001.96409663.800.013.99658.30.069664.60056021319.30.018.09213170.0221321.25017.75G022024600.011.012458.550.022460.2500.630516601.665165.1505166.1002.12409784.0503.549784.0509784.4005.3860210930921093.15021093.15019.13G0320920.500.111.94904.702.25921.300.030.47301951.600.213.761940.900.73961954.400.061.89403386.150.337.013370.600.813394.650.054.58607149.850.3415.827119.250.7497168.100.0716.25G0420927.950.271.41921.251.11929.900.010.51302104.650.243.012067.502.0192109.150.041.79403606.200.266.163555.451.813616.100.024.59608228.950.1113.448108.201.568236.500.0216.62G05203945.650.041.743943.600.093947.2500.79309043.750.024.449034.700.139045.2002.904016682.300.038.8416683.300.0316687.7507.736035684.450.0320.7935681.900.0335684.45027.86G06204051.500.091.674035.350.444052.1001.07309087.050.023.3690450.499088.5004.194015829.6006.1015762.450.4415830.40010.506036173.25013.835997.250.536174.90037.70G07201179.80.161.701145.803.201181.6500.38302422.850.973.732335.454.522446.050.021.41405065.500.697.165096.702.534971.400.083.606010551.751.1719.0610276.803.7710674.250.0213.17G08201414.750.020.881361.904.161414.9000.40303572.650.042.763422.104.653573.5001.54406018.050.135.045747.704.62602604.026013176.250.0511.712704.153.6613180.600.0114.58Average8745.690.176.278685.521.398750.010.017.22The pairedt-test between heuristic and GA found the p value to be 0.00105. Since the p value is less than α (i.e., 0.00105 < 0.05), the null hypothesis is rejected. The rejection of the null hypothesis state that the average value performance of the GA is statistically better than the performance of the heuristic algorithm at the 95% significance level. Similarly, the paired t-test between heuristic and PSO found the p value to be 0.0024, which indicates the better performance of PSO over heuristic on average solution value. The paired t-test between and GA found the p value to be 0.1955. This analysis indicates that on average results of GA and PSO are not significantly different statistically. However, the average RPD of PSO is slightly better than the average RPD of GA.Table3 shows the results of numerical experiments for the LPP problem. From Table 3, it could be seen that the PSO also outperforms the algorithms of GA and heuristic for the large instances. The RPD of PSO is lower than those of other algorithms with only a few exceptions. The average RPD of PSO in all groups is only 0.05, indicating the robustness of PSO for solving the LPP problem. Nonetheless, observation from the perspective of CPU time somehow provides a different picture. The average CPU time of PSO is 183.54 seconds, which is longer than the CPU time of GA. The CPU time of both metaheuristics increases significantly as the size of instances increases. Thus, when the size of problem instances becomes larger than the upper bound of 150, the performance of the heuristic algorithm might be more prominent and noteworthy, which is projected through its efficiency. Besides, it is noteworthy to point out that the average value and the maximal value of RPD for the heuristic algorithm are 1.21 percent and 4.61 percent, respectively, which also justify the use of heuristic for solving bigger problem instances.Table 3
Comparison of algorithms forLPP problem in large problem instances.
GroupnGAHeuristicPSOAverage ABSAverage RPDAverage CPU timeAverage ABSAverage RPDAverage ABSAverage RPDAverage CPU timeG018039999.70018.3639996.550.0140001.35047.1710060348.05033.3560344.200.0160351098.5012090745.90053.9990746090747.450175.65150136730.50095.76136730.250136732.450349.23G028040321.55019.0940321.80040322.25050.2410059533.70035.8459533.25059534.450106.8212088112.60055.288112.85088113.200193.73150135944.40093.05135945.200135945.200375.07G038013218.350.1833.0113169.900.5713241.65043.4910021454.100.1051.2421390.300.4121474.45090.1712029716.550.2475.8829621.800.5629772.050.04154.8115045783.900.17144.3945646.400.4745850.050.02333.35G048016005.400.0827.1815764.051.6316017043.5910023260.650.1343.34227562.3923290.40086.8912033656.800.1164.3533128.601.7733688.350.02148.3415055188.400.03113.9354435.751.4055145.450.13297.54G058065441.850.0241.2865444.250.0265454.45072.36100105339.850.0169.83105337.100.01105351.900152.881201442420.01130.24144235.250.01144246.150273.69150224901.750.01201.08224900.700.01224919.100565.53G068067786.35027.9467596.850.3067786.15095.73100102016.45058.30101679.350.33102016.300200.17120142779.90093.90142188.550.41142761.250.02332.17150229024.200151.58228191.400.36228882.650.06663.42G078018552.301.4648.5618146.203.5918823.9501110031254.302.0194.2531044.102.6931896.40064.7012044185.652.16154.3743879.852.8845117.950.10116.4415066529.351.99327.8466258.802.3967843.050.04240.82G0880237720.0224.7522833.254.07237700.0336.5310036552.200.1341.1034912.654.6736548.900.1067.5012055435.10057.59534003.7755273.100.30123.4815085601.850104.0384987.103.9882243.200.74262.19Average72919.860.2880.7772583.701.2172911.290.05183.54The pairedt-test among different algorithms for large problem instances shows a similar indication as to the small problem instances. The PSO and GA are statistically better than the heuristic algorithm. The performances of GA and PSO are not significantly different statistically. However, the average RPD of 0.05 for PSO is better than the average RPD of 0.28 for GA. Based on the discussion above, it could be concluded that both PSO and heuristic could provide reliable solutions. PSO provides better solutions than heuristic and competitive solutions as the GA algorithm, while the heuristic could solve the problem in a shorter CPU time.


### 6.3. Numerical Analysis for TPP Problem

Table4 conveys the CPU time for the mathematical model of the TPP problem. The TPP problem maximizes the net revenue of agent A, subject to an upper bound of the total weighted number of tardy jobs from agent B. As shown in the table, the mathematical model formulation provided in this paper manifests how it could only solve instances with the size limit of 20 jobs, which might be owing to the computational complexity of the problem scenario. In addition to that, the CPU time consumed for the mathematical model is longer than other settings when the tardiness factor takes a value of 0.3 instead of 0.7. In G05, the average CPU time to get the CPLEX solutions is 2089.13 seconds. For one of the instances belonging to this group, it takes more than ten hours (38991.2 seconds) to find the solution.Table 4
CPU time of CPLEX solutions inTPP problem.
GroupnCPUAvgMaxMinG0120202.063001.290.29G02207.46117.490.18G032075.50428.410.20G04205.1927.880.13G05202089.1338991.20.19G06209.69156.750.18G072075.60448.802.80G08209.5349.890.71Table5 displays the results of PSO and the heuristic algorithm for the small instances. As shown in the table, PSO outperforms the heuristic in all groups in terms of the objective function value. It deviates from the CPLEX solutions only by 0.11 percent. Contrarily, the solution quality of the heuristic algorithm is not as good as PSO; the average of the APD values from the five groups (G03, G04, G06, G07, and G08) exceeds 10 percent. Although it appears that the heuristic in this paper does not perform well for the TPP problem, it is noteworthy to mention that the heuristic could still be used as a good comparison for PSO due to its efficiency. The paired t-test between heuristic and PSO for small problem instances found the p value to be 0.00338. The analysis indicates that the average performance of the PSO is statistically better than the average performance of the heuristic algorithm at the 95% significance level.Table 5
Comparison of algorithms inTPP problem in small instances.
GroupnHeuristicPSOAverage ABSAverage APDAverage ABSAverage CPU timeAverage APDG0120116.800.68117.600.300G0220112.502.29115.150.350G032098.3014.21112.850.530.14G042096.7511.46108.500.610.10G0520110.456.02117.450.460G0620107.1510.24119.500.530G072071.3023.5792.600.350.23G082070.2029.5398.150.490.44Average97.9312.25110.230.450.11The numerical results of PSO and heuristic in theTPP problem are presented in Table 6 to showcase larger problem instances. The results indicate that the PSO still shows its superiority over the heuristic. It could be concluded that the PSO can provide a better solution for the problem considered in this paper. The heuristic can generate a solution in a shorter time with an acceptable percentage deviation. The paired t-test between heuristic and PSO for large problem instances found the p value to be 2.3×10−9 . The analysis strongly suggests that the average performance of the PSO is statistically better than the average performance of the heuristic algorithm at the 95% significance level.Table 6
Comparison of algorithms inTPP problem in large instances.
nGroupHeuristicPSOAverage ABSAverage RPDAverage ABSAverage CPU timeAverage RPD30G01173.751.96176.950.89040225.553.05232.602.45060344.051.29348.606.35080463.151.10468.5017.240100608.301.20615.5032.930120726.050.23727.7052.490150892.950.23894.95105.01030G02169.900.61170.850.90040239.550.15239.902.20060363.250363.256.94080485.350.09485.8017.870100601.400.19602.6040.770120723.300.05723.6564.810150903.700903.70113.56030G03146.9011.37164.651.86040204.559.94225.354.10060292.9510.14323.4513.87080414.807.53447.3036.970100537.107.21575.7570.420120581.608.15625.75122.500150807.355.61852.75247.89030G04146.4014.27169.852.41040200.459.95221.755.64060308.909.59341.1518.73080419.958.5045853.930100549.258.75601114.190120633.9510.49705.30203.200150753.0511.06843.50371.27030G05170.256.08180.751.58040234.403.34242.403.72060346.854.61363.1012.29080463.802.58476.4028.420100590.402.65606.3554.210120692.503.94720.1595.590.011508532.75877.15205.54030G06171.557.68185.901.72040211.507.34227.204.01060343.108.22373.8513080431.156.29460.1026.340100570.905.90606.8555.610120647.708.14704.20109.970150822.706.22877.15198.15030G07114.2023.30146.701.14040147.1023.20190.402.75060226.3520.75284.509.13080297.5521.60377.2020.830100368.5520.70462.1040.880120460.1019.7057072.390150559.6018.74685.60142.20030G08131.3523.49171.151.96040158.1026.43214.604.81060243.8024.31321.5018.36080326.8523.24424.5550.35010039624.61525.35101.700120493.0525.71662.35181.650150588.4525.46788.05374.110Average428.189.64468.4963.640The numerical analysis performed forLPP and TPP problem indicates the superior performance of PSO over existing algorithms. The superior performance can be attributed to the hybridization of PSO with local search schemes. The superior performance of the hybrid PSO algorithm indicates that the algorithm has the potential to solve different problems arising in different industries. In past, PSO has been successfully used to solve the option price model (Sharma et al., [34]). In the future, the hybrid PSO can be applied to solve different pricing and index-based models such coupon bond model (Jin et al. [35]), option pricing model (Jin et al., [36]), and risk index model (Jin and Zhu, [37]).


## 6.1. Instance Setting

In this paper, instances generated in the study of Reisi-Nafchi and Moslehi [4] are recognized as the benchmark instances. Different algorithms are evaluated and appraised based on their performance on these benchmark instances. The setting of the benchmark instances is as follows.Processing times and weights are generated randomly from a uniform distribution within the interval of [1, 10]. When generating due dates, two additional parameters are introduced: tardiness factorτ and the range factor r. Due dates are generated randomly within the range of [TPT∗(1−τ−r/2), TPT∗(1−τ−r/2)], in which the TPT denotes the sum of processing times from all the jobs. The revenues are generated from a uniform distribution within the interval of 1,2∗pi; upper bound Q is generated within the range of 0,∑i=n1+1nwi. The instances are sorted into eight groups according to the parameter setting, the sizes of instances ranging from 20 to 150. In the first four groups, n1=2n2; in the remaining groups, 2n1=n2. Parameter of τ takes the value of 0.3 in the groups of G01, G02, G05, and G06, and it takes the value of 0.7 in the groups of G03, G04, G07, and G08. The parameter of r takes the value of 0.2 in groups of G01, G03, G05, and G07. In the benchmark instances, there are 1280 instances in total and 20 instances for each parameter setting. The numerical analysis is primarily focused on the average results, which could be obtained from a varied set of results in different parameter settings.


## 6.2. Numerical Analysis for theLPP Problem

As mentioned above, the performance of PSO and heuristic is compared and weighed against the results in Reisi-Nafchi and Moslehi [4]. The numerical results of GA and CPLEX solution in Reisi-Nafchi and Moslehi [4] are obtained from the authors. In small instances, the performance of these algorithms along with the GA algorithm is compared with the CPLEX solution, while in large instances, the illustrations include the performance of PSO, heuristic, and GA being compared with each other. It is noteworthy that the CPU time of the heuristic is not shown in the corresponding tables since the proposed heuristic algorithm itself could solve all of the instances within 0.1 seconds.Table1 displays the computational results of integer-programming formulation. According to the results, it could be seen that the existing mathematical model could solve problem instances with up to 60 jobs. It could also be seen that the CPU time of G03 and G07 is significantly longer than other groups, when τ=0.3 and r=0.6. The maximum CPU time in these groups exceeds 1000 seconds, indicating that it is more difficult for the system to search for the optimal solutions in these groups. The results further indicate that the CPU time of the CPLEX solver increases exponentially and thus the larger problem instances cannot be solved using the CPLEX solver. Therefore, heuristic and metaheuristic algorithms are used to solve bigger problem instances.Table 1
CPU time of CPLEX solutions in theLPP problem.
GroupnCPUAvgMinMaxG01200.090.020.98300.370.073.27401.50.187.53601.510.4115.63G02200.030.020.15300.080.060.1400.220.170.3600.40.310.64G03200.390.021.18304.30.0915.074028.780.24121.7560308.440.531314.29G04200.070.020.64300.340.071.464010.174.596011.70.48138.64G05200.060.020.4301.450.1412.28401.160.163.856027.340.76201.91G06200.040.020.11300.40.131.93400.220.120.64601.770.588.1G07200.320.080.98304.510.5516.784035.920.48200.7360519.6223.011442.53G08200.060.020.48300.430.081.88400.830.173.21607.330.5988.78Table2 reports the APD values of the three algorithms for the LPP problem. As shown in the table, the PSO algorithm performs best in small instances in terms of the solution quality. The solutions of PSO are only 0.01 percent away from the CPLEX solutions. Besides, the maximal APD of PSO is lower than 0.1%, which is lower than other algorithms. On the other hand, though the heuristic deviates furthest from CPLEX solutions, the average APD of the heuristic is lower than 1.5%. This observation also indicates the effectiveness of the heuristic algorithm in solving the small problem instances.Table 2
Comparison of algorithms ofLPP problem in small instances.
GroupnGAHeuristicPSOAverage ABSAverage APDAverage CPU timeAverage ABSAverage APDAverage ABSAverage APDAverage CPU timeG01202518.3000.942517.600.032518.3500.56305682.550.021.955680.750.055683.3001.96409663.800.013.99658.30.069664.60056021319.30.018.09213170.0221321.25017.75G022024600.011.012458.550.022460.2500.630516601.665165.1505166.1002.12409784.0503.549784.0509784.4005.3860210930921093.15021093.15019.13G0320920.500.111.94904.702.25921.300.030.47301951.600.213.761940.900.73961954.400.061.89403386.150.337.013370.600.813394.650.054.58607149.850.3415.827119.250.7497168.100.0716.25G0420927.950.271.41921.251.11929.900.010.51302104.650.243.012067.502.0192109.150.041.79403606.200.266.163555.451.813616.100.024.59608228.950.1113.448108.201.568236.500.0216.62G05203945.650.041.743943.600.093947.2500.79309043.750.024.449034.700.139045.2002.904016682.300.038.8416683.300.0316687.7507.736035684.450.0320.7935681.900.0335684.45027.86G06204051.500.091.674035.350.444052.1001.07309087.050.023.3690450.499088.5004.194015829.6006.1015762.450.4415830.40010.506036173.25013.835997.250.536174.90037.70G07201179.80.161.701145.803.201181.6500.38302422.850.973.732335.454.522446.050.021.41405065.500.697.165096.702.534971.400.083.606010551.751.1719.0610276.803.7710674.250.0213.17G08201414.750.020.881361.904.161414.9000.40303572.650.042.763422.104.653573.5001.54406018.050.135.045747.704.62602604.026013176.250.0511.712704.153.6613180.600.0114.58Average8745.690.176.278685.521.398750.010.017.22The pairedt-test between heuristic and GA found the p value to be 0.00105. Since the p value is less than α (i.e., 0.00105 < 0.05), the null hypothesis is rejected. The rejection of the null hypothesis state that the average value performance of the GA is statistically better than the performance of the heuristic algorithm at the 95% significance level. Similarly, the paired t-test between heuristic and PSO found the p value to be 0.0024, which indicates the better performance of PSO over heuristic on average solution value. The paired t-test between and GA found the p value to be 0.1955. This analysis indicates that on average results of GA and PSO are not significantly different statistically. However, the average RPD of PSO is slightly better than the average RPD of GA.Table3 shows the results of numerical experiments for the LPP problem. From Table 3, it could be seen that the PSO also outperforms the algorithms of GA and heuristic for the large instances. The RPD of PSO is lower than those of other algorithms with only a few exceptions. The average RPD of PSO in all groups is only 0.05, indicating the robustness of PSO for solving the LPP problem. Nonetheless, observation from the perspective of CPU time somehow provides a different picture. The average CPU time of PSO is 183.54 seconds, which is longer than the CPU time of GA. The CPU time of both metaheuristics increases significantly as the size of instances increases. Thus, when the size of problem instances becomes larger than the upper bound of 150, the performance of the heuristic algorithm might be more prominent and noteworthy, which is projected through its efficiency. Besides, it is noteworthy to point out that the average value and the maximal value of RPD for the heuristic algorithm are 1.21 percent and 4.61 percent, respectively, which also justify the use of heuristic for solving bigger problem instances.Table 3
Comparison of algorithms forLPP problem in large problem instances.
GroupnGAHeuristicPSOAverage ABSAverage RPDAverage CPU timeAverage ABSAverage RPDAverage ABSAverage RPDAverage CPU timeG018039999.70018.3639996.550.0140001.35047.1710060348.05033.3560344.200.0160351098.5012090745.90053.9990746090747.450175.65150136730.50095.76136730.250136732.450349.23G028040321.55019.0940321.80040322.25050.2410059533.70035.8459533.25059534.450106.8212088112.60055.288112.85088113.200193.73150135944.40093.05135945.200135945.200375.07G038013218.350.1833.0113169.900.5713241.65043.4910021454.100.1051.2421390.300.4121474.45090.1712029716.550.2475.8829621.800.5629772.050.04154.8115045783.900.17144.3945646.400.4745850.050.02333.35G048016005.400.0827.1815764.051.6316017043.5910023260.650.1343.34227562.3923290.40086.8912033656.800.1164.3533128.601.7733688.350.02148.3415055188.400.03113.9354435.751.4055145.450.13297.54G058065441.850.0241.2865444.250.0265454.45072.36100105339.850.0169.83105337.100.01105351.900152.881201442420.01130.24144235.250.01144246.150273.69150224901.750.01201.08224900.700.01224919.100565.53G068067786.35027.9467596.850.3067786.15095.73100102016.45058.30101679.350.33102016.300200.17120142779.90093.90142188.550.41142761.250.02332.17150229024.200151.58228191.400.36228882.650.06663.42G078018552.301.4648.5618146.203.5918823.9501110031254.302.0194.2531044.102.6931896.40064.7012044185.652.16154.3743879.852.8845117.950.10116.4415066529.351.99327.8466258.802.3967843.050.04240.82G0880237720.0224.7522833.254.07237700.0336.5310036552.200.1341.1034912.654.6736548.900.1067.5012055435.10057.59534003.7755273.100.30123.4815085601.850104.0384987.103.9882243.200.74262.19Average72919.860.2880.7772583.701.2172911.290.05183.54The pairedt-test among different algorithms for large problem instances shows a similar indication as to the small problem instances. The PSO and GA are statistically better than the heuristic algorithm. The performances of GA and PSO are not significantly different statistically. However, the average RPD of 0.05 for PSO is better than the average RPD of 0.28 for GA. Based on the discussion above, it could be concluded that both PSO and heuristic could provide reliable solutions. PSO provides better solutions than heuristic and competitive solutions as the GA algorithm, while the heuristic could solve the problem in a shorter CPU time.


## 6.3. Numerical Analysis for TPP Problem

Table4 conveys the CPU time for the mathematical model of the TPP problem. The TPP problem maximizes the net revenue of agent A, subject to an upper bound of the total weighted number of tardy jobs from agent B. As shown in the table, the mathematical model formulation provided in this paper manifests how it could only solve instances with the size limit of 20 jobs, which might be owing to the computational complexity of the problem scenario. In addition to that, the CPU time consumed for the mathematical model is longer than other settings when the tardiness factor takes a value of 0.3 instead of 0.7. In G05, the average CPU time to get the CPLEX solutions is 2089.13 seconds. For one of the instances belonging to this group, it takes more than ten hours (38991.2 seconds) to find the solution.Table 4
CPU time of CPLEX solutions inTPP problem.
GroupnCPUAvgMaxMinG0120202.063001.290.29G02207.46117.490.18G032075.50428.410.20G04205.1927.880.13G05202089.1338991.20.19G06209.69156.750.18G072075.60448.802.80G08209.5349.890.71Table5 displays the results of PSO and the heuristic algorithm for the small instances. As shown in the table, PSO outperforms the heuristic in all groups in terms of the objective function value. It deviates from the CPLEX solutions only by 0.11 percent. Contrarily, the solution quality of the heuristic algorithm is not as good as PSO; the average of the APD values from the five groups (G03, G04, G06, G07, and G08) exceeds 10 percent. Although it appears that the heuristic in this paper does not perform well for the TPP problem, it is noteworthy to mention that the heuristic could still be used as a good comparison for PSO due to its efficiency. The paired t-test between heuristic and PSO for small problem instances found the p value to be 0.00338. The analysis indicates that the average performance of the PSO is statistically better than the average performance of the heuristic algorithm at the 95% significance level.Table 5
Comparison of algorithms inTPP problem in small instances.
GroupnHeuristicPSOAverage ABSAverage APDAverage ABSAverage CPU timeAverage APDG0120116.800.68117.600.300G0220112.502.29115.150.350G032098.3014.21112.850.530.14G042096.7511.46108.500.610.10G0520110.456.02117.450.460G0620107.1510.24119.500.530G072071.3023.5792.600.350.23G082070.2029.5398.150.490.44Average97.9312.25110.230.450.11The numerical results of PSO and heuristic in theTPP problem are presented in Table 6 to showcase larger problem instances. The results indicate that the PSO still shows its superiority over the heuristic. It could be concluded that the PSO can provide a better solution for the problem considered in this paper. The heuristic can generate a solution in a shorter time with an acceptable percentage deviation. The paired t-test between heuristic and PSO for large problem instances found the p value to be 2.3×10−9 . The analysis strongly suggests that the average performance of the PSO is statistically better than the average performance of the heuristic algorithm at the 95% significance level.Table 6
Comparison of algorithms inTPP problem in large instances.
nGroupHeuristicPSOAverage ABSAverage RPDAverage ABSAverage CPU timeAverage RPD30G01173.751.96176.950.89040225.553.05232.602.45060344.051.29348.606.35080463.151.10468.5017.240100608.301.20615.5032.930120726.050.23727.7052.490150892.950.23894.95105.01030G02169.900.61170.850.90040239.550.15239.902.20060363.250363.256.94080485.350.09485.8017.870100601.400.19602.6040.770120723.300.05723.6564.810150903.700903.70113.56030G03146.9011.37164.651.86040204.559.94225.354.10060292.9510.14323.4513.87080414.807.53447.3036.970100537.107.21575.7570.420120581.608.15625.75122.500150807.355.61852.75247.89030G04146.4014.27169.852.41040200.459.95221.755.64060308.909.59341.1518.73080419.958.5045853.930100549.258.75601114.190120633.9510.49705.30203.200150753.0511.06843.50371.27030G05170.256.08180.751.58040234.403.34242.403.72060346.854.61363.1012.29080463.802.58476.4028.420100590.402.65606.3554.210120692.503.94720.1595.590.011508532.75877.15205.54030G06171.557.68185.901.72040211.507.34227.204.01060343.108.22373.8513080431.156.29460.1026.340100570.905.90606.8555.610120647.708.14704.20109.970150822.706.22877.15198.15030G07114.2023.30146.701.14040147.1023.20190.402.75060226.3520.75284.509.13080297.5521.60377.2020.830100368.5520.70462.1040.880120460.1019.7057072.390150559.6018.74685.60142.20030G08131.3523.49171.151.96040158.1026.43214.604.81060243.8024.31321.5018.36080326.8523.24424.5550.35010039624.61525.35101.700120493.0525.71662.35181.650150588.4525.46788.05374.110Average428.189.64468.4963.640The numerical analysis performed forLPP and TPP problem indicates the superior performance of PSO over existing algorithms. The superior performance can be attributed to the hybridization of PSO with local search schemes. The superior performance of the hybrid PSO algorithm indicates that the algorithm has the potential to solve different problems arising in different industries. In past, PSO has been successfully used to solve the option price model (Sharma et al., [34]). In the future, the hybrid PSO can be applied to solve different pricing and index-based models such coupon bond model (Jin et al. [35]), option pricing model (Jin et al., [36]), and risk index model (Jin and Zhu, [37]).


## 7. Conclusions

This paper works on the order acceptance two-agent scheduling problems, which are regarded as an NP-hard problem. This paper contemplates and examines the two variants of the problem named theLPP problem and the TPP problem. The objective function of the LPP problem is to maximize the total revenues of accepted orders minus the total weighted lateness of the jobs from agent A. The objective function of the TPP problem is to maximize the total revenues of accepted orders minus the total weighted tardiness of jobs from agent A. Both variants of the problem impose a constraint that the sum of the weighted number of tardy jobs belonging to agent B is not allowed to exceed the given upper bound. Algorithms including a metaheuristic (PSO) and a heuristic are proposed to solve these problems. Additionally, a mathematical model is provided. The proposed algorithms are designed in such a way so that it can decode and find a solution to both problems that are being considered in this paper.The numerical results stipulate that the proposed algorithm is competitive with the existing GA algorithm. The solution produced by the proposed PSO algorithm is within less than 1% of the optimal solution for the small problem instances. The PSO could provide better solutions while the heuristic could provide solutions with an acceptable deviation percentage from the PSO solution in shorter CPU time.In the future, the mathematical model formulation could be improved and tweaked by removing the redundant constraints and decision variables to solve bigger problem instances. Also, experimental efforts could essentially be performed, focusing on the aspects like reducing CPU time of the proposed PSO algorithm.



---

*Source: 6627081-2021-02-08.xml*