A Lagrangian approach to single-machine scheduling problems with two competing agents. (English) Zbl 1185.90063

Summary: We develop branch-and-bound algorithms for several hard, two-agent scheduling problems, i.e., problems in which each agent has an objective function which depends on the completion times of its jobs only. Our bounding approach is based on the fact that, for all problems considered, the Lagrangian dual gives a good bound and can be solved exactly in strongly polynomial time. The problems addressed here consist in minimizing the total weighted completion time of the jobs of agent A, subject to a bound on the cost function of agent B, which may be: (i) total weighted completion time, (ii) maximum lateness, (iii) maximum completion time. An extensive computational experience shows the effectiveness of the approach.


90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI


[1] Albino, V., Carbonara, N., & Giannoccaro, I. (2006). Innovation in industrial districts: an agent-based simulation model. International Journal of Production Economics, 104, 30–45.
[2] Arbib, C., Servilio, M., & Smriglio, S. (2004). A competitive scheduling problem and its relevance to UMTS channel assignment. Networks, 44(2), 132–141. · Zbl 1055.90031
[3] Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2000). Nondominated schedules for a job-shop with two competing agents. Computational and Mathematical Organization Theory, 6(2), 191–217.
[4] Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52(2), 229–242. · Zbl 1165.90446
[5] Baker, K. R., & Cole Smith, J. (2003). A multiple-criterion model for machine scheduling. Journal of Scheduling, 6(1), 7–16. · Zbl 1154.90406
[6] Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 362, 273–281. · Zbl 1100.68007
[7] Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2008). Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research, 188, 603–609. · Zbl 1129.90023
[8] Ng, C. T., Cheng, T. C. E., & Yuan, J. J. (2006). A note on the complexity of the problem of two-agent scheduling on a single machine. Journal of Combinatorial Optimization, 12(4), 387–394. · Zbl 1126.90027
[9] Pan, Y. (2003). An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time. Operations Research Letters, 31, 492–496. · Zbl 1052.90037
[10] Peha, J. M. (1995). Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time. Journal of Computers and Operations Research, 22(10), 1089–1100. · Zbl 0838.90067
[11] Posner, M. E. (1985). Minimizing weighted completion times with deadlines. Operations Research, 33(3), 562–574. · Zbl 0575.90030
[12] Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1), 59–66.
[13] Sourd, F. (2008). Private communication.
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.