# American Institute of Mathematical Sciences

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, 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] Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219 [2] Muminu O. Adamu, Aderemi O. Adewumi. Minimizing the weighted number of tardy jobs on multiple machines: A review. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1465-1493. doi: 10.3934/jimo.2016.12.1465 [3] Mostafa Abouei Ardakan, A. Kourank Beheshti, S. Hamid Mirmohammadi, Hamed Davari Ardakani. A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 465-480. doi: 10.3934/naco.2017029 [4] Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033 [5] Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691 [6] Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071 [7] Chunlai Liu, Yanpeng Fan, Chuanli Zhao, Jianjun Wang. Multiple common due-dates assignment and optimal maintenance activity scheduling with linear deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 713-720. doi: 10.3934/jimo.2016042 [8] Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017 [9] Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591 [10] Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825 [11] Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial & Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271 [12] Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131 [13] Futoshi Takahashi. On the number of maximum points of least energy solution to a two-dimensional Hénon equation with large exponent. Communications on Pure & Applied Analysis, 2013, 12 (3) : 1237-1241. doi: 10.3934/cpaa.2013.12.1237 [14] Imed Kacem, Eugene Levner. An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs. Journal of Industrial & Management Optimization, 2016, 12 (3) : 811-817. doi: 10.3934/jimo.2016.12.811 [15] Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703 [16] Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71 [17] Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243 [18] Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060 [19] David Auger, Irène Charon, Iiro Honkala, Olivier Hudry, Antoine Lobstein. Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs. Advances in Mathematics of Communications, 2009, 3 (1) : 97-114. doi: 10.3934/amc.2009.3.97 [20] Yibo Zhang, Jinfeng Gao, Jia Ren, Huijiao Wang. A type of new consensus protocol for two-dimension multi-agent systems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 345-357. doi: 10.3934/naco.2017022

2018 Impact Factor: 1.025