×

Two-agent scheduling with linear deteriorating jobs on a single machine. (English) Zbl 1148.90324

Hu, Xiaodong (ed.) et al., Computing and combinatorics. 14th annual international conference, COCOON 2008, Dalian, China, June 27–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-69732-9/pbk). Lecture Notes in Computer Science 5092, 642-650 (2008).
Summary: This paper considers the two-agent scheduling problems with linear deteriorating jobs to be processed on a single machine. By a deteriorating job we mean that the processing time of the job is a function of its starting time. Two agents compete for the usage of a common single machine and each agent has his own criterion to optimize. There are four objective functions: makespan, maximum lateness, maximum cost, and total completion time. Some basic properties of two different scheduling problems to minimize the objective function for one agent with a constraint on the other agent’s objective function are proved. Based on these properties, the optimal algorithms with polynomial time are presented for two different scheduling problems, respectively.
For the entire collection see [Zbl 1139.68006].

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agnetis, A.; Mirchandani, P. B.; Pacciarelli, D.; Pacifici, A., Scheduling Problems with Two Competing Agents, Operations Research, 52, 229-242 (2004) · Zbl 1165.90446 · doi:10.1287/opre.1030.0092
[2] Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent Single Machine Scheduling, Annals of Operations Research, 150, 3-15 (2007) · Zbl 1144.90375 · doi:10.1007/s10479-006-0164-y
[3] Alidaee, B.; Womer, N. K., Scheduling with Time Dependent Processing Times: Review and Extensions, Journal of the Operational Research Society, 50, 711-720 (1999) · Zbl 1054.90542 · doi:10.1057/palgrave.jors.2600740
[4] Baker, K. R.; Smith, J. C., A multiple-criterion Model for Machine Scheduling, Journal of Scheduling, 6, 7-16 (2003) · Zbl 1154.90406 · doi:10.1023/A:1022231419049
[5] Browne, S.; Yechiali, U., Scheduling Deteriorating Jobs on a Single Processor, Operations Research, 38, 495-498 (1990) · Zbl 0703.90051
[6] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A Concise Survey of Scheduling with Time-Dependent Processing Times, European Journal of Operational Research, 152, 1-13 (2004) · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8
[7] 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 (2006) · Zbl 1100.68007 · doi:10.1016/j.tcs.2006.07.011
[8] 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 · doi:10.1016/j.ejor.2007.04.040
[9] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and Approximation in Deterministic Sequencing and Scheduling Theory: a Survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[10] Gupta, J. N.D.; Gupta, S. K., Single Facility Scheduling with Nonlinear Processing Times, Computers and Industrial Engineering, 14, 387-393 (1988) · doi:10.1016/0360-8352(88)90041-1
[11] Mosheiov, G., Scheduling Jobs under Simple Linear Deterioration, Computers and Operations Research, 21, 653-659 (1994) · Zbl 0810.90074 · doi:10.1016/0305-0548(94)90080-9
[12] Ng, C. T.; Cheng, T. C.E.; Bachman, A.; Janiak, A., Three Scheduling Problems with Deteriorating Jobs to Minimize the Total Completion Time, Information Processing Letters, 81, 327-333 (2002) · doi:10.1016/S0020-0190(01)00244-7
[13] Wu, C. C.; Lee, W. C., Scheduling Linear Deteriorating Jobs to Minimize Makespan with an Availability Constraint on a Single Machien, Information Processing Letters, 87, 89-93 (2003) · Zbl 1161.68367 · doi:10.1016/S0020-0190(03)00262-X
[14] Yuan, J. J.; Shang, W. P.; Feng, Q., A Note on the Scheduling with Two Families of Jobs, Journal of Scheduling, 8, 537-542 (2005) · Zbl 1123.90040 · doi:10.1007/s10951-005-4997-z
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.