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

Hongwei Li; Yuvraj Gajpal; C. R. Bector

doi:10.3934/jimo.2019005

Article Contents

2020, Volume 16, Issue 3: 1329-1347. Doi: 10.3934/jimo.2019005

This issue Previous Article Multidimensional balanced credibility model with time effect and two level random common effects Next Article Pricing options on investment project contraction and ownership transfer using a finite volume scheme and an interior penalty method

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
^* Corresponding author: Yuvraj Gajpal

Received: October 31, 2017

Revised: August 31, 2018

Early access: March 2019

Published: March 2020

Abstract Full Text(HTML) Figure(1) / Table(7) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90B35; Secondary: 68M20.

Citation:

Full Text(HTML)

Figure 1. Variants of Objective Function

Download: Full-size image PowerPoint slide

Table 1. 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 r_i+p_i≤r_j for any jobs in both agents; (2) C_i^A≤r_i+1^A for the jobs of the first agent and C_j^B-d_j^B≤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-d_j^B
$8.1\|\max \{f_{j}^{B}(C_{j}^{B})\}\le Q,{{r}_{(i/j)}},pmtn\|L_{max}^{A}$	O(n_Anlogn)	Yuan et al. (2015)	Algorithm Pmtn-LS (optimal algorithm); EDD rule.

| Show Table

DownLoad: CSV

Table 2. 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

| Show Table

DownLoad: CSV

Table 3. 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 Heuristic There exists an optimal solution, if (1) the first job starts at time D-(P^A+P^B), where D represents the common due date, P^A and P^B represents the total processing time of A-jobs and B-jobs, respectively, (2) B-jobs are scheduled in a non-decreasing order of d_j^B-p_j^B (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

| Show Table

DownLoad: CSV

Table 4. 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 programming There 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 r_i+p_i≤r_j

| Show Table

DownLoad: CSV

Table 5. 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-d_j^B

| Show Table

DownLoad: CSV

Table 6. 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;

| Show Table

DownLoad: CSV

Table 7. 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, p_i < p_j, then job i should be scheduled before job j; (2) if jobs i and j are belonging the agent B, p_i < p_j and d_i < d_j, 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.

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Agnetis, G. de Pascale and D. Pacciarelli, A Lagrangian approach to single-machine scheduling problems with two competing agents, Journal of Scheduling, 12 (2009), 401-415. doi: 10.1007/s10951-008-0098-0.
[2]	A. Agnetis, P. B. Mirchandani, D. Pacciarelli and A. Pacifici, Scheduling problems with two competing agents, Operations Research, 52 (2004), 229-242. doi: 10.1287/opre.1030.0092.
[3]	K. R. Baker and J. Cole Smith, A multiple-criterion model for machine scheduling, Journal of Scheduling, 6 (2003), 7-16. doi: 10.1023/A:1022231419049.
[4]	P. Baptiste, J. Carlier and A. Jouglet, A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates, European Journal of Operational Research, 158 (2004), 595-608. doi: 10.1016/S0377-2217(03)00378-3.
[5]	J. Blazewicz, Scheduling preemptible tasks on parallel processors with information k s., (1984).
[6]	J. Błazewicz, M. Drozdowski, P. Formanowicz, W. Kubiak and G. Schmidt, Scheduling preemptable tasks on parallel processors with limited availability, Parallel Computing, 26 (2000), 1195-1211. doi: 10.1016/S0167-8191(00)00035-1.
[7]	P. J. Brewer and C. R. Plott, A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks, International Journal of Industrial Organization, 14 (1996), 857-886. doi: 10.1016/0167-7187(96)01014-4.
[8]	S.-R. Cheng, Some new problems on two-agent scheduling to minimize the earliness costs, International Journal of Production Economics, 156 (2014), 24-30. doi: 10.1016/j.ijpe.2014.05.004.
[9]	T. E. Cheng, Y.-H. Chung, S.-C. Liao and W.-C. Lee, Two-agent singe-machine scheduling with release times to minimize the total weighted completion time, Computers & Operations Research, 40 (2013), 353-361. doi: 10.1016/j.cor.2012.07.013.
[10]	T. E. Cheng, C.-Y. Liu, W.-C. Lee and M. Ji, Two-agent single-machine scheduling to minimize the weighted sum of the agents' objective functions, Computers & Industrial Engineering, 78 (2014), 66-73. doi: 10.1016/j.cie.2014.09.028.
[11]	T. E. Cheng, C. Ng and J. Yuan, Multi-agent scheduling on a single machine with max-form criteria, European Journal of Operational Research, 188 (2008), 603-609. doi: 10.1016/j.ejor.2007.04.040.
[12]	D. Elvikis, H. W. Hamacher and V. T'kindt, Scheduling two agents on uniform parallel machines with makespan and cost functions, Journal of Scheduling, 14 (2011), 471-481. doi: 10.1007/s10951-010-0201-1.
[13]	D. Elvikis and V. T'kindt, Two-agent scheduling on uniform parallel machines with min-max criteria, Annals of Operations Research, 213 (2014), 79-94. doi: 10.1007/s10479-012-1099-0.
[14]	E. Gerstl and G. Mosheiov, Scheduling problems with two competing agents to minimized weighted earliness-tardiness, Computers & Operations Research, 40 (2013), 109-116. doi: 10.1016/j.cor.2012.05.019.
[15]	E. Gerstl and G. Mosheiov, Single machine just-in-time scheduling problems with two competing agents, Naval Research Logistics (NRL), 61 (2014), 1-16. doi: 10.1002/nav.21562.
[16]	A. M. Hariri, C. N. Potts and L. N. Van Wassenhove, Single machine scheduling to minimize total weighted late work, ORSA Journal on Computing, 7 (1995), 232-242.
[17]	W. Horn, Some simple scheduling algorithms, Naval Research Logistics (NRL), 21 (1974), 177-185. doi: 10.1002/nav.3800210113.
[18]	R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations(Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N. Y., 1972), , Springer, (1972), 85–103.
[19]	S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680. doi: 10.1126/science.220.4598.671.
[20]	W.-C. Lee, Y.-H. Chung and M.-C. Hu, Genetic algorithms for a two-agent single-machine problem with release time, Applied Soft Computing, 12 (2012), 3580-3589. doi: 10.1016/j.asoc.2012.06.015.
[21]	W.-C. Lee, Y.-H. Chung and Z.-R. Huang, A single-machine bi-criterion scheduling problem with two agents, Applied Mathematics and Computation, 219 (2013), 10831-10841. doi: 10.1016/j.amc.2013.05.025.
[22]	W.-C. Lee, W.-J. Wang, Y.-R. Shiau and C.-C. Wu, A single-machine scheduling problem with two-agent and deteriorating jobs, Applied Mathematical Modelling, 34 (2010), 3098-3107. doi: 10.1016/j.apm.2010.01.015.
[23]	J. Y.-T. Leung, M. Pinedo and G. Wan, Competitive two-agent scheduling and its applications, Operations Research, 58 (2010), 458-469. doi: 10.1287/opre.1090.0744.
[24]	H. Li, Y. Gajpal and C. Bector, Single machine scheduling with two-agent for total weighted completion time objectives, Applied Soft Computing, 70 (2018), 147-156. doi: 10.1016/j.asoc.2018.05.027.
[25]	Y. Lun, K. Lai, C. Ng, C. Wong and T. Cheng, Editorial: Research in Shipping and Transport Logistics, International Journal of Shipping and Transport Logistics, 2011.
[26]	M. Mezmaz, N. Melab, Y. Kessaci, Y. C. Lee, E.-G. Talbi, A. Y. Zomaya and D. Tuyttens, A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems, Journal of Parallel and Distributed Computing, 71 (2011), 1497-1508. doi: 10.1016/j.jpdc.2011.04.007.
[27]	J. M. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15 (1968), 102-109. doi: 10.1287/mnsc.15.1.102.
[28]	B. Mor and G. Mosheiov, Scheduling problems with two competing agents to minimize minmax and minsum earliness measures, European Journal of Operational Research, 206 (2010), 540-546. doi: 10.1016/j.ejor.2010.03.003.
[29]	B. Mor and G. Mosheiov, A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance, Journal of Combinatorial Optimization, 33 (2017), 1454-1468. doi: 10.1007/s10878-016-0049-1.
[30]	C. Ng, T. C. Cheng and J. Yuan, A note on the complexity of the problem of two-agent scheduling on a single machine, Journal of Combinatorial Optimization, 12 (2006), 387-394. doi: 10.1007/s10878-006-9001-0.
[31]	S. Pandey, L. Wu, S. M. Guru and R. Buyya, A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments, Paper presented at the Advanced information networking and applications (AINA), 2010 24th IEEE international conference on, 2010.
[32]	J. M. Peha, Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time, Computers & Operations Research, 22 (1995), 1089-1100. doi: 10.1016/0305-0548(94)00090-U.
[33]	M. Pinedo, Scheduling, Theory, algorithms, and systems. Fourth edition. Springer, New York, 2012. doi: 10.1007/978-1-4614-2361-4.
[34]	C. N. Potts and L. N. Van Wassenhove, Approximation algorithms for scheduling a single machine to minimize total late work, Operations Research Letters, 11 (1992), 261-266. doi: 10.1016/0167-6377(92)90001-J.
[35]	C. N. Potts and L. N. Van Wassenhove, Single machine scheduling to minimize total late work, Operations Research, 40 (1992), 586-595. doi: 10.1287/opre.40.3.586.
[36]	M. Reisi-Nafchi and G. Moslehi, A hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem, Applied Soft Computing, 33 (2015), 37-47. doi: 10.1016/j.asoc.2015.04.027.
[37]	R. Soltani, F. Jolai and M. Zandieh, Two robust meta-heuristics for scheduling multiple job classes on a single machine with multiple criteria, Expert Systems with Applications, 37 (2010), 5951-5959. doi: 10.1016/j.eswa.2010.02.009.
[38]	M. Soomer and G. J. Franx, Scheduling aircraft landings using airlines' preferences, European Journal of Operational Research, 190 (2008), 277-291. doi: 10.1016/j.ejor.2007.06.017.
[39]	M. Sterna, A survey of scheduling problems with late work criteria, Omega, 39 (2011), 120-129. doi: 10.1016/j.omega.2010.06.006.
[40]	V. Suresh and D. Chaudhuri, Bicriteria scheduling problem for unrelated parallel machines, Computers & industrial engineering, 30 (1996), 77-82. doi: 10.1016/0360-8352(95)00028-3.
[41]	L. N. Van Wassenhove and C. N. Potts, Single machine scheduling to minimize total late work, Oper. Res., 40 (1992), 586-595. doi: 10.1287/opre.40.3.586.
[42]	D.-J. Wang, C.-C. Kang, Y.-R. Shiau, C.-C. Wu and P.-H. Hsu, A two-agent single-machine scheduling problem with late work criteria, Soft Computing, 21 (2017), 2015-2033. doi: 10.1007/s00500-015-1900-5.
[43]	D.-J. Wang, Y. Yin, S.-R. Cheng, T. Cheng and C.-C. Wu, Due date assignment and scheduling on a single machine with two competing agents, International Journal of Production Research, 54 (2016), 1152-1169.
[44]	D.-J. Wang, Y. Yin, J. Xu, W.-H. Wu, S.-R. Cheng and C.-C. Wu, Some due date determination scheduling problems with two agents on a single machine, International Journal of Production Economics, 168 (2015), 81-90. doi: 10.1016/j.ijpe.2015.06.018.
[45]	W.-H. Wu, An exact and meta-heuristic approach for two-agent single-machine scheduling problem, Journal of Marine Science and Technology, 21 (2013), 215-221.
[46]	W.-H. Wu, Y. Yin, W.-H. Wu, C.-C. Wu and P.-H. Hsu, A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents, Journal of Industrial & Management Optimization, 10 (2014), 591-611. doi: 10.3934/jimo.2014.10.591.
[47]	Z. Xingong and W. Yong, Two-agent scheduling problems on a single-machine to minimize the total weighted late work, Journal of Combinatorial Optimization, 33 (2017), 945-955. doi: 10.1007/s10878-016-0017-9.
[48]	M. Yazdani and F. Jolai, A Genetic Algorithm with Modified Crossover Operator for a Two-Agent Scheduling Problem, Shiraz Journal of System Management, 1 (2013), 1-13.
[49]	Y. Yin, S.-R. Cheng, T. Cheng, D.-J. Wang and C.-C. Wu, Just-in-time scheduling with two competing agents on unrelated parallel machines, Omega, 63 (2016), 41-47. doi: 10.1016/j.omega.2015.09.010.
[50]	Y. Yin, S.-R. Cheng, T. Cheng, W.-H. Wu and C.-C. Wu, Two-agent single-machine scheduling with release times and deadlines, International Journal of Shipping and Transport Logistics, 5 (2013), 75-94. doi: 10.1504/IJSTL.2013.050590.
[51]	Y. Yin, T. Cheng, D.-J. Wang and C.-C. Wu, Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs, Journal of scheduling, 20 (2017), 313-335. doi: 10.1007/s10951-017-0511-7.
[52]	Y. Yin, W. Wang, D. Wang and T. Cheng, Multi-agent single-machine scheduling and unrestricted due date assignment with a fixed machine unavailability interval, Computers & Industrial Engineering, 111 (2017), 202-215. doi: 10.1016/j.cie.2017.07.013.
[53]	Y. Yin, C.-C. Wu, W.-H. Wu, C.-J. Hsu and W.-H. Wu, A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents, Applied Soft Computing, 13 (2013), 1042-1054. doi: 10.1016/j.asoc.2012.09.026.
[54]	Y. Yin, W.-H. Wu, S.-R. Cheng and C.-C. Wu, An investigation on a two-agent single-machine scheduling problem with unequal release dates, Computers & Operations Research, 39 (2012), 3062-3073. doi: 10.1016/j.cor.2012.03.012.
[55]	Y. Yin, W.-H. Wu, T. Cheng, C.-C. Wu and W.-H. Wu, A honey-bees optimization algorithm for a two-agent single-machine scheduling problem with ready times, Applied Mathematical Modelling, 39 (2015), 2587-2601. doi: 10.1016/j.apm.2014.10.044.
[56]	J. Yuan, C. Ng and T. E. Cheng, Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness, Journal of Scheduling, 18 (2015), 147-153. doi: 10.1007/s10951-013-0360-y.
[57]	F. Zhang, C. Ng, G. Tang, T. Cheng and Y. Lun, Inverse scheduling: Applications in shipping, International Journal of Shipping and Transport Logistics, 3 (2011), 312-322. doi: 10.1504/IJSTL.2011.040800.