# American Institute of Mathematical Sciences

• Previous Article
Pricing options on investment project contraction and ownership transfer using a finite volume scheme and an interior penalty method
• JIMO Home
• This Issue
• Next Article
Multidimensional balanced credibility model with time effect and two level random common effects
May  2020, 16(3): 1329-1347. doi: 10.3934/jimo.2019005

## A survey of due-date related single-machine with two-agent scheduling problem

 Department of Supply Chain Management, I.H. Asper School of Business, University of Manitoba, Winnipeg, Manitoba, R3T 5V4, Canada

* Corresponding author: Yuvraj Gajpal

Received  November 2017 Revised  September 2018 Published  March 2019

In this paper, we consider due-date related single machine scheduling problems, where two agents compete for utilizing a common processing resource (i.e. a single machine). In this paper, we provide a detailed and a systemic literature review of the two-agent scheduling problem dealing with models with a given due date. We consider the following four main cases: 1) the earliness and tardiness, 2) the maximum lateness, 3) the number of tardy jobs and 4) the late work criteria. To do so, we classify due-date related, two-agent scheduling problems into two categories on the basis of the objective function setting, (i.e. the feasibility model and the minimality model). The feasibility model minimizes the objective function of one agent subject to an upper bound on the objective for the other agent. The minimality model assigns certain weights for two agents and as a result minimizes their weighted objectives. In the present paper, we list the computational complexities and proposed algorithms for the due-date related, two-agent scheduling problem, investigated in the literature since 2003.

Citation: Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1329-1347. doi: 10.3934/jimo.2019005
##### References:

show all references

##### References:
Variants of Objective Function
Summary of reviewed maximum lateness scheduling problem
 Problem Complexity Reference Approach/Result $1.~1~\ \left| ~L_{max}^{B}\le Q \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard T. E. Cheng et al. (2008) Alessandro Agnetis et al. (2009) Branch-and-Bound method; In an optimal schedule, A-jobs are scheduled in WSPT order, and B-jobs are scheduled in EDD order; B-jobs are scheduled consecutively. $2.~1\ ~\left| ~L_{max}^{B}\le Q,~{{r}_{i/j}} \right|~\mathop{\sum }^{}C_{i}^{A}$ unary NP-hard Yin et al. (2012) A-jobs are scheduled in SPT order, and B-jobs are scheduled in EDD order; $3.~1\ ~\left| ~L_{max}^{B}\le Q,~{{r}_{i/j}} \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard T. E. Cheng et al. (2013)Yin et al. (2015) Branch-and-Bound method; Simulated Annealingalgorithm; Marriage in Honey-bees Optimization algorithm; In an optimal schedule, (1) the job i needs to be scheduled before job j, if ri+pi≤rj for any jobs in both agents; (2) CiA≤ri+1A for the jobs of the first agent and CjB-djB≤Q for the jobs of the second agent. $4.1\ |L_{max}^{B}\le Q,{{r}_{(i/j)}}|\sum{T_{i}^{A}}$ unary NP-hard Yin et al. (2012)Lee et al. (2012)Baptiste et al. (2004) Branch-and-Bound algorithm; Mixed Integer Programming model; Marriage in Honey-Bees Optimization algorithm; In the initialization step, B-jobs are scheduled in EDD order, A-jobs are scheduled in non-decreasing order of their sums of processing time and release time.Genetic Algorithm. \begin{align} &5.\text{ }\!\!~\!\!\text{ }1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }L_{max}^{A}\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }\left( \text{P}1 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}T_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}2 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}w_{i}^{A}T_{i}^{A}\left( \text{P}3 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| L_{max}^{B}\le Q \right|\mathop{\sum }^{}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}4 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| L_{max}^{B}\le Q \right|\mathop{\sum }^{}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}4 \right), \\ &1\text{ }\!\!~\!\!\text{ }|L_{max}^{B}\le Q|\mathop{\sum }^{}w_{i}^{A}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}5 \right) \\ \end{align} NP-hard Wang et al. (2015) There exists an optimal solution, A-jobs are scheduled in SPT-EDD order for P1 and P2; A-jobs are scheduled in SPT order for P3, P4 and P5; B-jobs are scheduled in SPT-EDD order for all five problems. $6.1~|~\mathop{\sum }^{}L_{max}^{B}\le Q,~~~{{r}_{i/j}}~|~\mathop{\sum }^{}U_{i}^{A}$ strongly NP-hard Yin, Cheng, et al. (2013) Branch-and-Bound method; Simulated Annealing algorithm. $7.~1~\left| ~L_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}V_{i}^{A}$ NP-hard Wang et al. (2017) Branch-and-Bound method; Tabu-Search Heuristic; In an optimal schedule, (1) all A-jobs and B-jobs are processed consecutively without idle time and the first job starts at time 0; (2) all early and partially early A-jobs and all B-jobs are scheduled before all tardy A-jobs; (3) the early and partially early A-jobs are scheduled in EDD order; (4) the B-jobs are scheduled in non-decreasing order of Q-djB $8.1|\max \{f_{j}^{B}(C_{j}^{B})\}\le Q,{{r}_{(i/j)}},pmtn|L_{max}^{A}$ O(nAnlogn) Yuan et al. (2015) Algorithm Pmtn-LS (optimal algorithm); EDD rule.
 Problem Complexity Reference Approach/Result $1.~1~\ \left| ~L_{max}^{B}\le Q \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard T. E. Cheng et al. (2008) Alessandro Agnetis et al. (2009) Branch-and-Bound method; In an optimal schedule, A-jobs are scheduled in WSPT order, and B-jobs are scheduled in EDD order; B-jobs are scheduled consecutively. $2.~1\ ~\left| ~L_{max}^{B}\le Q,~{{r}_{i/j}} \right|~\mathop{\sum }^{}C_{i}^{A}$ unary NP-hard Yin et al. (2012) A-jobs are scheduled in SPT order, and B-jobs are scheduled in EDD order; $3.~1\ ~\left| ~L_{max}^{B}\le Q,~{{r}_{i/j}} \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard T. E. Cheng et al. (2013)Yin et al. (2015) Branch-and-Bound method; Simulated Annealingalgorithm; Marriage in Honey-bees Optimization algorithm; In an optimal schedule, (1) the job i needs to be scheduled before job j, if ri+pi≤rj for any jobs in both agents; (2) CiA≤ri+1A for the jobs of the first agent and CjB-djB≤Q for the jobs of the second agent. $4.1\ |L_{max}^{B}\le Q,{{r}_{(i/j)}}|\sum{T_{i}^{A}}$ unary NP-hard Yin et al. (2012)Lee et al. (2012)Baptiste et al. (2004) Branch-and-Bound algorithm; Mixed Integer Programming model; Marriage in Honey-Bees Optimization algorithm; In the initialization step, B-jobs are scheduled in EDD order, A-jobs are scheduled in non-decreasing order of their sums of processing time and release time.Genetic Algorithm. \begin{align} &5.\text{ }\!\!~\!\!\text{ }1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }L_{max}^{A}\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }\left( \text{P}1 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}T_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}2 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}w_{i}^{A}T_{i}^{A}\left( \text{P}3 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| L_{max}^{B}\le Q \right|\mathop{\sum }^{}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}4 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| L_{max}^{B}\le Q \right|\mathop{\sum }^{}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}4 \right), \\ &1\text{ }\!\!~\!\!\text{ }|L_{max}^{B}\le Q|\mathop{\sum }^{}w_{i}^{A}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}5 \right) \\ \end{align} NP-hard Wang et al. (2015) There exists an optimal solution, A-jobs are scheduled in SPT-EDD order for P1 and P2; A-jobs are scheduled in SPT order for P3, P4 and P5; B-jobs are scheduled in SPT-EDD order for all five problems. $6.1~|~\mathop{\sum }^{}L_{max}^{B}\le Q,~~~{{r}_{i/j}}~|~\mathop{\sum }^{}U_{i}^{A}$ strongly NP-hard Yin, Cheng, et al. (2013) Branch-and-Bound method; Simulated Annealing algorithm. $7.~1~\left| ~L_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}V_{i}^{A}$ NP-hard Wang et al. (2017) Branch-and-Bound method; Tabu-Search Heuristic; In an optimal schedule, (1) all A-jobs and B-jobs are processed consecutively without idle time and the first job starts at time 0; (2) all early and partially early A-jobs and all B-jobs are scheduled before all tardy A-jobs; (3) the early and partially early A-jobs are scheduled in EDD order; (4) the B-jobs are scheduled in non-decreasing order of Q-djB $8.1|\max \{f_{j}^{B}(C_{j}^{B})\}\le Q,{{r}_{(i/j)}},pmtn|L_{max}^{A}$ O(nAnlogn) Yuan et al. (2015) Algorithm Pmtn-LS (optimal algorithm); EDD rule.
Summary of problems and their computational complexity studied by S.-R. Cheng (2014)
 Problem Complexity $1~\left| ~f_{max}^{B}\le Q~ \right|\max f_{j}^{X}\left( E_{j}^{X} \right)$ $O\left( {{\left( {{n}_{A}}+{{n}_{B}} \right)}^{2}} \right)$ $1~\left| ~f_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}E_{j}^{X}$ Strongly NP-hard $1~\left| ~f_{max}^{B}\le Q,~AD~ \right|\mathop{\sum }^{}E_{j}^{X}$ $O\left( {{n}_{A}}\log {{n}_{A}}+\left( {{n}_{A}}+{{n}_{B}} \right)\left( {{n}_{B}}+1 \right) \right)$ $1~\left| ~f_{max}^{B}\le Q,~AW~ \right|\mathop{\sum }^{}w_{j}^{X}E_{j}^{X}$ $O\left( {{n}_{A}}\log {{n}_{A}}+\left( {{n}_{A}}+{{n}_{B}} \right)\left( {{n}_{B}}+1 \right) \right)$ $1~\left| ~E_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard $1~\left| ~T_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard $1~\left| ~\mathop{\sum }^{}E_{j}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard $1~\left| ~\mathop{\sum }^{}T_{j}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard $1~\left| ~\mathop{\sum }^{}\left( E_{j}^{B}+T_{j}^{B} \right)\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
 Problem Complexity $1~\left| ~f_{max}^{B}\le Q~ \right|\max f_{j}^{X}\left( E_{j}^{X} \right)$ $O\left( {{\left( {{n}_{A}}+{{n}_{B}} \right)}^{2}} \right)$ $1~\left| ~f_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}E_{j}^{X}$ Strongly NP-hard $1~\left| ~f_{max}^{B}\le Q,~AD~ \right|\mathop{\sum }^{}E_{j}^{X}$ $O\left( {{n}_{A}}\log {{n}_{A}}+\left( {{n}_{A}}+{{n}_{B}} \right)\left( {{n}_{B}}+1 \right) \right)$ $1~\left| ~f_{max}^{B}\le Q,~AW~ \right|\mathop{\sum }^{}w_{j}^{X}E_{j}^{X}$ $O\left( {{n}_{A}}\log {{n}_{A}}+\left( {{n}_{A}}+{{n}_{B}} \right)\left( {{n}_{B}}+1 \right) \right)$ $1~\left| ~E_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard $1~\left| ~T_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard $1~\left| ~\mathop{\sum }^{}E_{j}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard $1~\left| ~\mathop{\sum }^{}T_{j}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard $1~\left| ~\mathop{\sum }^{}\left( E_{j}^{B}+T_{j}^{B} \right)\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
Summary of reviewed earliness, lateness and tardiness related two-agent scheduling problem
 Problem Complexity Reference Approach/Result \begin{align} &1.\text{ }\!\!~\!\!\text{ }1\text{ }\!\!~\!\!\text{ }\!\!|\!\!\text{ }\max (w_{j}^{B}E_{j}^{B}+w_{j}^{B}T_{j}^{B}\text{)}\le \\ &Q,\text{ }\!\!~\!\!\text{ }p_{i}^{A}=p_{j}^{B}=p,\text{ }\!\!~\!\!\text{ }d_{i}^{A}=d_{j}^{B}= \\ &d\text{ }\!\!~\!\!\text{ }|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}\left( w_{i}^{A}E_{i}^{A}+w_{i}^{A}T_{i}^{A} \right) \\ \end{align} -- Gerstl and Mosheiov (2013) Reduce the problem to a single linear assignment problem (LAP). The global optimum is determined by the minimal-cost LAP.In an optimal solution, (1) the first scheduled job starts at time zero, or (2) at least one B-job has cost value of the upper bound, or (3) a A-job is completed exactly at the due date $2.~1\left| E_{max}^{B}\le Q \right|~\mathop{\sum }^{}w_{i}^{A}E_{i}^{A}+\mathop{\sum }^{}w_{j}^{B}E_{j}^{B}$ strongly NP-hard Yin, Wu, et al. (2013) Mathematical Programming Formulation method; Branch-and-Bound method; Simulated Annealing algorithm. $3.~1~\left| ~E_{max}^{B}\le Q~ \right|~E_{max}^{A}$ binary NP-hard Mor and Mosheiov (2010) A HeuristicThere exists an optimal solution, if (1) the first job starts at time D-(PA+PB), where D represents the common due date, PA and PB represents the total processing time of A-jobs and B-jobs, respectively, (2) B-jobs are scheduled in a non-decreasing order of djB-pjB (i.e. MST order), and (3) A-jobs are scheduled in MST order. $4.~1~\left| ~E_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}E_{i}^{A}$ strongly NP-hard Mor and Mosheiov (2010) A WSPT and MST based Heuristic. $5.1~\left| ~T_{max}^{B}\le Q,~~nr-a~ \right|~\mathop{\sum }^{}C_{i}^{A}$ strongly NP-hard Yazdani and Jolai (2013) Genetic Algorihtm
 Problem Complexity Reference Approach/Result \begin{align} &1.\text{ }\!\!~\!\!\text{ }1\text{ }\!\!~\!\!\text{ }\!\!|\!\!\text{ }\max (w_{j}^{B}E_{j}^{B}+w_{j}^{B}T_{j}^{B}\text{)}\le \\ &Q,\text{ }\!\!~\!\!\text{ }p_{i}^{A}=p_{j}^{B}=p,\text{ }\!\!~\!\!\text{ }d_{i}^{A}=d_{j}^{B}= \\ &d\text{ }\!\!~\!\!\text{ }|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}\left( w_{i}^{A}E_{i}^{A}+w_{i}^{A}T_{i}^{A} \right) \\ \end{align} -- Gerstl and Mosheiov (2013) Reduce the problem to a single linear assignment problem (LAP). The global optimum is determined by the minimal-cost LAP.In an optimal solution, (1) the first scheduled job starts at time zero, or (2) at least one B-job has cost value of the upper bound, or (3) a A-job is completed exactly at the due date $2.~1\left| E_{max}^{B}\le Q \right|~\mathop{\sum }^{}w_{i}^{A}E_{i}^{A}+\mathop{\sum }^{}w_{j}^{B}E_{j}^{B}$ strongly NP-hard Yin, Wu, et al. (2013) Mathematical Programming Formulation method; Branch-and-Bound method; Simulated Annealing algorithm. $3.~1~\left| ~E_{max}^{B}\le Q~ \right|~E_{max}^{A}$ binary NP-hard Mor and Mosheiov (2010) A HeuristicThere exists an optimal solution, if (1) the first job starts at time D-(PA+PB), where D represents the common due date, PA and PB represents the total processing time of A-jobs and B-jobs, respectively, (2) B-jobs are scheduled in a non-decreasing order of djB-pjB (i.e. MST order), and (3) A-jobs are scheduled in MST order. $4.~1~\left| ~E_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}E_{i}^{A}$ strongly NP-hard Mor and Mosheiov (2010) A WSPT and MST based Heuristic. $5.1~\left| ~T_{max}^{B}\le Q,~~nr-a~ \right|~\mathop{\sum }^{}C_{i}^{A}$ strongly NP-hard Yazdani and Jolai (2013) Genetic Algorihtm
Summary of reviewed number of tardy jobs related two-agent scheduling problem
 Problem Complexity Reference Approach/Result $1.1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}U_{i}^{A}$ $O\left( {{n}^{3}} \right)$ Allesandro Agnetis et al. (2004) Dynamic Programming.In an optimal solution, (1) all early jobs are scheduled consecutively in EDD order at the beginning of the schedule; (2) all tardy jobs are scheduled consecutively at the end of the schedule. $2.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}C_{i}^{A}$ open Allesandro Agnetis et al. (2004)Ng et al. (2006)Leung et al. (2010) A Pseudo Polynomial Time Algorithm.In an optimal solution, all A-jobs are ordered in SPT order, and all B-jobs are scheduled in EDD order. $3.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ binary NP-hard Allesandro Agnetis et al. (2004)Ng et al. (2006) -- $4.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard Allesandro Agnetis et al. (2004)Ng et al. (2006) -- $5.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}T_{i}^{A}$ binary NP-hard Leung et al. (2010) -- $6.1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\theta ~\mathop{\sum }^{}C_{i}^{A}+\left( 1-\theta \right)~L_{max}^{A}$, where 0 < θ < 1 strongly NP-hard Lee et al. (2013) Branch-and-Bound method; A combined simulated annealing (SA) algorithm:EDD rule and SPT rule; Neighborhood Generation Methods: PI, EFSR and EBSR. $7.1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\mathop{\sum }^{}T_{i}^{A}$ NP-hard Wu (2013) Branch-and-Bound method; Genetic Algorithm. $8.~1~\left| ~\mathop{\sum }^{}w_{j}^{B}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}L_{i}^{A}$ NP-hard Wu (2013)Reisi-Nafchi and Moslehi (2015) An Integer Linear Programming model; A hybrid meta-heuristic algorithm:Combing a genetic algorithm and lnear programmingThere exists an optimal solution, (1) A-jobs are scheduled in WSPT order; (2) in which the agent B tardy accepted orders are sequenced arbitrarily at the end of sequence; (3) in which the global arrangement of the agent B non-tardy accepted orders follows the EDD order and they are replced at the last possible positions before their due time. $9.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0,~~r,~~p=\text{ }\!\!\alpha\!\!\text{ }+\beta t \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard Lee et al. (2010) Branch-and-Bound method; A Heuristic algorithm.An optimal schedule exists such that job i is the preceding job of job j when ri+pi≤rj
 Problem Complexity Reference Approach/Result $1.1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}U_{i}^{A}$ $O\left( {{n}^{3}} \right)$ Allesandro Agnetis et al. (2004) Dynamic Programming.In an optimal solution, (1) all early jobs are scheduled consecutively in EDD order at the beginning of the schedule; (2) all tardy jobs are scheduled consecutively at the end of the schedule. $2.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}C_{i}^{A}$ open Allesandro Agnetis et al. (2004)Ng et al. (2006)Leung et al. (2010) A Pseudo Polynomial Time Algorithm.In an optimal solution, all A-jobs are ordered in SPT order, and all B-jobs are scheduled in EDD order. $3.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ binary NP-hard Allesandro Agnetis et al. (2004)Ng et al. (2006) -- $4.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard Allesandro Agnetis et al. (2004)Ng et al. (2006) -- $5.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}T_{i}^{A}$ binary NP-hard Leung et al. (2010) -- $6.1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\theta ~\mathop{\sum }^{}C_{i}^{A}+\left( 1-\theta \right)~L_{max}^{A}$, where 0 < θ < 1 strongly NP-hard Lee et al. (2013) Branch-and-Bound method; A combined simulated annealing (SA) algorithm:EDD rule and SPT rule; Neighborhood Generation Methods: PI, EFSR and EBSR. $7.1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\mathop{\sum }^{}T_{i}^{A}$ NP-hard Wu (2013) Branch-and-Bound method; Genetic Algorithm. $8.~1~\left| ~\mathop{\sum }^{}w_{j}^{B}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}L_{i}^{A}$ NP-hard Wu (2013)Reisi-Nafchi and Moslehi (2015) An Integer Linear Programming model; A hybrid meta-heuristic algorithm:Combing a genetic algorithm and lnear programmingThere exists an optimal solution, (1) A-jobs are scheduled in WSPT order; (2) in which the agent B tardy accepted orders are sequenced arbitrarily at the end of sequence; (3) in which the global arrangement of the agent B non-tardy accepted orders follows the EDD order and they are replced at the last possible positions before their due time. $9.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0,~~r,~~p=\text{ }\!\!\alpha\!\!\text{ }+\beta t \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard Lee et al. (2010) Branch-and-Bound method; A Heuristic algorithm.An optimal schedule exists such that job i is the preceding job of job j when ri+pi≤rj
Summary of reviewed late work criteria related two-agent scheduling problems
 Problem Complexity Reference Approach/Result $1.~~1~\left| ~f_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O({{n}_{A}}^{2}Q\left( \underset{i=1}{\overset{{{n}_{A}}}{\mathop \sum }}\,p_{i}^{A}+\underset{j=1}{\overset{{{n}_{B}}}{\mathop \sum }}\,p_{j}^{B} \right)+{{n}_{B}}\log {{n}_{B}}$ Xingong and Yong (2016) In an optimal schedule, all B-jobs are scheduled in the reserved interval it associated with.The pre-emption constraint does not impact the optimal solution $2.~~1~\left| ~f_{max}^{B}\le Q,~~d_{i}^{A}={{d}^{A}}~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O\left( {{n}_{A}}\log {{n}_{A}}+{{n}_{B}}\log {{n}_{B}} \right)$ $3.~1~\left| ~f_{max}^{B}\le Q,~~p_{i}^{A}={{p}^{A}}~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O\left( {{n}_{A}}^{3}+{{n}_{B}}\log {{n}_{B}} \right)$ $4.~1\left| ~L_{max}^{B}\le Q \right|\mathop{\sum }^{}V_{i}^{A}$ NP-hard Wang et al. (2017) Branch-and-Bound method; Tabu-Search Heuristic; In an optimal schedule, (1) all A-jobs and B-jobs are processed consecutively without idle time and the first job starts at time 0; (2) all early and partially early A-jobs and all B-jobs are scheduled before all tardy A-jobs; (3) the early and partially early A-jobs are scheduled in EDD order; (4) the B-jobs are scheduled in non-decreasing order of Q-djB
 Problem Complexity Reference Approach/Result $1.~~1~\left| ~f_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O({{n}_{A}}^{2}Q\left( \underset{i=1}{\overset{{{n}_{A}}}{\mathop \sum }}\,p_{i}^{A}+\underset{j=1}{\overset{{{n}_{B}}}{\mathop \sum }}\,p_{j}^{B} \right)+{{n}_{B}}\log {{n}_{B}}$ Xingong and Yong (2016) In an optimal schedule, all B-jobs are scheduled in the reserved interval it associated with.The pre-emption constraint does not impact the optimal solution $2.~~1~\left| ~f_{max}^{B}\le Q,~~d_{i}^{A}={{d}^{A}}~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O\left( {{n}_{A}}\log {{n}_{A}}+{{n}_{B}}\log {{n}_{B}} \right)$ $3.~1~\left| ~f_{max}^{B}\le Q,~~p_{i}^{A}={{p}^{A}}~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O\left( {{n}_{A}}^{3}+{{n}_{B}}\log {{n}_{B}} \right)$ $4.~1\left| ~L_{max}^{B}\le Q \right|\mathop{\sum }^{}V_{i}^{A}$ NP-hard Wang et al. (2017) Branch-and-Bound method; Tabu-Search Heuristic; In an optimal schedule, (1) all A-jobs and B-jobs are processed consecutively without idle time and the first job starts at time 0; (2) all early and partially early A-jobs and all B-jobs are scheduled before all tardy A-jobs; (3) the early and partially early A-jobs are scheduled in EDD order; (4) the B-jobs are scheduled in non-decreasing order of Q-djB
Summary of two-agent scheduling problems, computational complexity and approach/result studied by Baker and Smith (2003)
 Problem Complexity Approach/Result $1.~~~1~\left| ~ \right|~\left( L_{max}^{A},~~~L_{max}^{B} \right)$ NP-hard Processing the jobs of two agents in EDD rule; Using dynamic programming to find an optimal solution. $2.~~~1~\left| ~ \right|~\left( C_{max}^{A},~~~L_{max}^{B} \right)$ $O\left( {{n_2}\log \;{n_2}} \right)$ Processing the jobs of the first agent consecutively; Processing the jobs of the other agent in EDD rule; Polynomial time algorithm. $3.~~~1~\left| ~ \right|~\left( \mathop{\sum }^{}w_{i}^{A}C_{i}^{A},~~~L_{max}^{B} \right)$ NP-complete Processing the jobs of the first agent may not in WSPT rule; Processing the jobs of the other agent in EDD rule; For a special case with equal weights, using SPT and EDD rule. It can be solved by using the dynamic programming. $4.~~~1~\left| ~ \right|~\left( C_{max}^{A},~L_{max}^{B},~\mathop{\sum }^{}w_{j}^{C}C_{j}^{C} \right)$ NP-hard Processing the jobs of the first agent consecutively; Combing the contributions of the objectives of the first and third agent;
 Problem Complexity Approach/Result $1.~~~1~\left| ~ \right|~\left( L_{max}^{A},~~~L_{max}^{B} \right)$ NP-hard Processing the jobs of two agents in EDD rule; Using dynamic programming to find an optimal solution. $2.~~~1~\left| ~ \right|~\left( C_{max}^{A},~~~L_{max}^{B} \right)$ $O\left( {{n_2}\log \;{n_2}} \right)$ Processing the jobs of the first agent consecutively; Processing the jobs of the other agent in EDD rule; Polynomial time algorithm. $3.~~~1~\left| ~ \right|~\left( \mathop{\sum }^{}w_{i}^{A}C_{i}^{A},~~~L_{max}^{B} \right)$ NP-complete Processing the jobs of the first agent may not in WSPT rule; Processing the jobs of the other agent in EDD rule; For a special case with equal weights, using SPT and EDD rule. It can be solved by using the dynamic programming. $4.~~~1~\left| ~ \right|~\left( C_{max}^{A},~L_{max}^{B},~\mathop{\sum }^{}w_{j}^{C}C_{j}^{C} \right)$ NP-hard Processing the jobs of the first agent consecutively; Combing the contributions of the objectives of the first and third agent;
Summary of reviewed late work criteria related two-agent scheduling problems (Minimality Model)
 Problem Complexity Reference Approach/Result $1.1~\left| ~ \right|~~\theta \mathop{\sum }^{}C_{i}^{A}+\left( 1-\theta \right)\mathop{\sum }^{}T_{j}^{B}$ NP-hard T. E. Cheng et al. (2014) Branch-and-Bound method; Genetic Algorithm; Simulated Annealing algorithm; In an optimal solution, (1) if jobs i and j are belonging the agent A, pi < pj, then job i should be scheduled before job j; (2) if jobs i and j are belonging the agent B, pi < pj and di < dj, then job i should be scheduled before job j $2.~1~\left| ~ \right|~\mathop{\sum }^{}w_{i}^{A}T_{i}^{A}+\mathop{\sum }^{}w_{j}^{B}T_{j}^{B}$ NP-hard Wu et al. (2014) Branch-and-Bound method; Ant Colony Optimization algorithm; Simulated Annealing algorithm.
 Problem Complexity Reference Approach/Result $1.1~\left| ~ \right|~~\theta \mathop{\sum }^{}C_{i}^{A}+\left( 1-\theta \right)\mathop{\sum }^{}T_{j}^{B}$ NP-hard T. E. Cheng et al. (2014) Branch-and-Bound method; Genetic Algorithm; Simulated Annealing algorithm; In an optimal solution, (1) if jobs i and j are belonging the agent A, pi < pj, then job i should be scheduled before job j; (2) if jobs i and j are belonging the agent B, pi < pj and di < dj, then job i should be scheduled before job j $2.~1~\left| ~ \right|~\mathop{\sum }^{}w_{i}^{A}T_{i}^{A}+\mathop{\sum }^{}w_{j}^{B}T_{j}^{B}$ NP-hard Wu et al. (2014) Branch-and-Bound method; Ant Colony Optimization algorithm; Simulated Annealing algorithm.
 [1] Muberra Allahverdi, Harun Aydilek, Asiye Aydilek, Ali Allahverdi. A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1973-1991. doi: 10.3934/jimo.2020054 [2] Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081 [3] Maha Daoud, El Haj Laamri. Fractional Laplacians : A short survey. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021027 [4] Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365 [5] Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25 [6] Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1693-1716. doi: 10.3934/dcdss.2020450 [7] Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141 [8] Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044 [9] Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011 [10] M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072 [11] Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881 [12] Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009 [13] Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933 [14] Zhigang Pan, Chanh Kieu, Quan Wang. Hopf bifurcations and transitions of two-dimensional Quasi-Geostrophic flows. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021025 [15] Jihoon Lee, Ngocthach Nguyen. Flows with the weak two-sided limit shadowing property. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021040 [16] Markus Harju, Jaakko Kultima, Valery Serov, Teemu Tyni. Two-dimensional inverse scattering for quasi-linear biharmonic operator. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021026 [17] Jinye Shen, Xian-Ming Gu. Two finite difference methods based on an H2N2 interpolation for two-dimensional time fractional mixed diffusion and diffusion-wave equations. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021086 [18] Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182 [19] Ying Yang. Global classical solutions to two-dimensional chemotaxis-shallow water system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2625-2643. doi: 10.3934/dcdsb.2020198 [20] Gaurav Nagpal, Udayan Chanda, Nitant Upasani. Inventory replenishment policies for two successive generations price-sensitive technology products. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021036

2019 Impact Factor: 1.366

## Metrics

• HTML views (811)
• Cited by (3)

• on AIMS