Two-agent scheduling to minimize the total cost. (English) Zbl 1237.90094

Summary: Two agents, each having his own set of jobs, compete to perform their own jobs on a common processing resource. Each job of the agents has a weight that specifies its importance. The cost of the first agent is the maximum weighted completion time of his jobs while the cost of the second agent is the total weighted completion time of his jobs. We consider the scheduling problem of determining the sequence of the jobs such that the total cost of the two agents is minimized. We provide a 2-approximation algorithm for the problem, show that the case where the number of jobs of the first agent is fixed is NP-hard, and devise a polynomial time approximation scheme for this case.


90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI


[1] Afrati, F., Chekuri, E.C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M., 1999. Approximation schemes for minimizing average weighted completion time with release dates. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, New York, October, 32-43.
[2] Agnetis, A.; Mirchandani, P.B.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Operations research, 52, 229-242, (2004) · Zbl 1165.90446
[3] Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent single machine scheduling, Annals of operations research, 150, 3-15, (2007) · Zbl 1144.90375
[4] Baker, K.R.; Smith, J.C., A multiple-criterion model for machine scheduling, Journal of scheduling, 6, 7-16, (2003) · Zbl 1154.90406
[5] Cheng, T.C.E.; Ng, C.T.; Yuan, J.J., Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theoretical computer science, 362, 273-281, (2007) · Zbl 1100.68007
[6] Cheng, T.C.E.; Ng, C.T.; Yuan, J.J., Multi-agent scheduling on a single machine with MAX-form criteria, European journal of operational research, 188, 603-609, (2008) · Zbl 1129.90023
[7] Curiel, I.; Pederzoli, G.; Tijs, S., Sequencing games, European journal of operational research, 40, 344-351, (1989) · Zbl 0674.90107
[8] Feng, Q.; Yuan, J.J., NP-hardness of a multicriteria scheduling on two families of jobs, OR transactions, 11:4, 121-126, (2007)
[9] Hamers, H.; Borm, P.; Tijs, S., On games corresponding to sequencing situations with ready times, Mathematical programming, 70, 1-13, (1995) · Zbl 0844.90120
[10] Leung, J.Y.-T.; Pinedo, M.; Wan, G.H., Competitive two-agent scheduling and its applications, Operations research, 58:2, 458-469, (2010) · Zbl 1233.90163
[11] Ng, C.T.; Cheng, T.C.E.; Yuan, J.J., A note on the complexity of the problem of two-agent scheduling on a single machine, Journal of combinatorial optimization, 12, 387-394, (2006) · Zbl 1126.90027
[12] Queyranne, M., Structure of a simple scheduling polyhedron, Mathematical programming, 58, 263-285, (1993) · Zbl 0778.90031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.