×
Qi, Yawei; Wan, Long

A competitive two-agent scheduling problem on parallel machines with release dates and preemption. (English) Zbl 1296.90056

Math. Probl. Eng. 2013, Article ID 124083, 5 p. (2013).

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
65K05 Numerical mathematical programming methods
Cite Review PDF
Full Text: DOI

References:

[1] W. A. Horn, “Some simple scheduling algorithms,” Naval Research Logistics Quarterly, vol. 21, pp. 177-185, 1974. · Zbl 0276.90024 · doi:10.1002/nav.3800210113
[2] S. Sahni, “Preemptive scheduling with due dates,” Operations Research, vol. 27, no. 5, pp. 925-934, 1979. · Zbl 0424.90031 · doi:10.1287/opre.27.5.925
[3] S. Sahni and Y. Cho, “Scheduling independent tasks with due times on a uniform processor system,” Journal of the Association for Computing Machinery, vol. 27, no. 3, pp. 550-563, 1980. · Zbl 0475.68013 · doi:10.1145/322203.322214
[4] E. L. Lawler and J. Labetoulle, “On preemptive scheduling of unrelated parallel processors by linear programming,” Journal of the Association for Computing Machinery, vol. 25, no. 4, pp. 612-619, 1978. · Zbl 0388.68027 · doi:10.1145/322092.322101
[5] J. Labetoulle, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, “Preemptive scheduling of uniform machines subject to release dates,” in Progress in Combinatorial Optimization, pp. 245-261, Academic Press, Toronto, Canada, 1984. · Zbl 0554.90059
[6] E. L. Lawler and C. U. Martel, “Computing maximal “polymatroidal” network flows,” Mathematics of Operations Research, vol. 7, no. 3, pp. 334-347, 1982. · Zbl 0498.90029 · doi:10.1287/moor.7.3.334
[7] C. Martel, “Preemptive scheduling with release times, deadlines and due times,” Journal of the Association for Computing Machinery, vol. 29, no. 3, pp. 812-829, 1982. · Zbl 0485.68033 · doi:10.1145/322326.322337
[8] K. R. Baker and J. C. Smith, “A multiple-criterion model for machine scheduling,” Journal of Scheduling, vol. 6, no. 1, pp. 7-16, 2003. · Zbl 1154.90406 · doi:10.1023/A:1022231419049
[9] A. Agnetis, P. B. Mirchandani, D. Pacciarelli, and A. Pacifici, “Scheduling problems with two competing agents,” Operations Research, vol. 52, no. 2, pp. 229-242, 2004. · Zbl 1165.90446 · doi:10.1287/opre.1030.0092
[10] A. Agnetis, D. Pacciarelli, and A. Pacifici, “Multi-agent single machine scheduling,” Annals of Operations Research, vol. 150, pp. 3-15, 2007. · Zbl 1144.90375 · doi:10.1007/s10479-006-0164-y
[11] T. C. E. Cheng, C. T. Ng, and J. J. Yuan, “Multi-agent scheduling on a single machine with max-form criteria,” European Journal of Operational Research, vol. 188, no. 2, pp. 603-609, 2008. · Zbl 1129.90023 · doi:10.1016/j.ejor.2007.04.040
[12] T. C. E. Cheng, C. T. Ng, and J. J. Yuan, “Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs,” Theoretical Computer Science, vol. 362, no. 1-3, pp. 273-281, 2006. · Zbl 1100.68007 · doi:10.1016/j.tcs.2006.07.011
[13] J. J. Yuan, W. P. Shang, and Q. Feng, “A note on the scheduling with two families of jobs,” Journal of Scheduling, vol. 8, no. 6, pp. 537-542, 2005. · Zbl 1123.90040 · doi:10.1007/s10951-005-4997-z
[14] C. T. Ng, T. C. E. Cheng, and J. J. Yuan, “A note on the complexity of the problem of two-agent scheduling on a single machine,” Journal of Combinatorial Optimization, vol. 12, no. 4, pp. 387-394, 2006. · Zbl 1126.90027 · doi:10.1007/s10878-006-9001-0
[15] B. Mor and G. Mosheiov, “Scheduling problems with two competing agents to minimize minmax and minsum earliness measures,” European Journal of Operational Research, vol. 206, no. 3, pp. 540-546, 2010. · Zbl 1188.90103 · doi:10.1016/j.ejor.2010.03.003
[16] J. Y.-T. Leung, M. Pinedo, and G. Wan, “Competitive two-agent scheduling and its applications,” Operations Research, vol. 58, no. 2, pp. 458-469, 2010. · Zbl 1233.90163 · doi:10.1287/opre.1090.0744
[17] J. J. Yuan, C. T. Ng, and T. C. E. Cheng, “A note on two-agent scheduling on a single machine with release dates and preemption,” Unpublished Manuscript, 2011.
[18] L. Wan, J. J. Yuan, and Z. C. Gen, “A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints,” In Submission, 2012.
[19] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman, San Francisco, Calif, USA, 1979. · Zbl 0411.68039
[20] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, “Optimization and approximation in deterministic sequencing and scheduling: a survey,” Annals of Discrete Mathematics, vol. 5, pp. 287-326, 1979. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[21] R. McNaughton, “Scheduling with deadlines and loss functions,” Management Science, vol. 6, pp. 1-12, 1959. · Zbl 1047.90504 · doi:10.1287/mnsc.6.1.1
[22] A. V. Karzanov, “Determining the maximal flow in a network by the method of preflows,” Soviet Mathematics Doklady, vol. 15, pp. 434-437, 1974. · Zbl 0303.90014
[23] R. E. Tarjan, “A simple version of Karzanov’s blocking flow algorithm,” Operations Research Letters, vol. 2, no. 6, pp. 265-268, 1984. · Zbl 0542.05057 · doi:10.1016/0167-6377(84)90076-2
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.