# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. (English) Zbl 1247.90165
Summary: We consider a scheduling environment with two agents and a linear non-increasing deterioration. By the linear non-increasing deterioration we mean that the actual processing time of a job belonging to the two agents is defined as a non-increasing linear function of its starting time. Two agents compete to perform their respective jobs on a common single machine and each agent has his own criterion to be optimized. The goal is to schedule the jobs such that the combined schedule performs well with respect to the measures of both agents. Three different objective functions are considered for one agent, including the maximum earliness cost, total earliness cost and total weighted earliness cost, while keeping the maximum earliness cost of the other agent below or at a fixed level $U$. We propose the optimal (nondominated) properties and present the complexity results for the problems addressed here.
##### MSC:
 90B35 Scheduling theory, deterministic
##### Keywords:
scheduling; single-machine; two agents; deterioration
##### 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-729 (1999) · Zbl 1054.90542 [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] Balin, S.: Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation, Information sciences 181, No. 17, 3551-3569 (2011) [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] Cheng, T. C. E.; Yang, S. J.; Yang, D. L.: Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity, International journal of production economics 135, No. 1, 154-161 (2012) [10] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinnooy: Optimization and heuristic in deterministic sequencing and scheduling: a survey, Annals of discrete mathematics 5, 287-326 (1979) · Zbl 0411.90044 [11] Ho, K. I. J.; Leung, J. Y. T.; Wei, W. -D.: Complexity of scheduling tasks with time-dependent execution times, Information processing letter 48, 315-320 (1993) · Zbl 0942.68508 · doi:10.1016/0020-0190(93)90175-9 [12] Hsu, C. J.; Cheng, T. C. E.; Yang, D. L.: Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time, Information sciences 181, No. 20, 4799-4803 (2011) [13] Inderfurth, K.; Janiak, A.; Kovalyov, M. Y.; Werner, F.: Batching work and rework processes with limited deterioration of reworkables, Computers and operations research 33, 1595-1605 (2006) · Zbl 1087.90008 · doi:10.1016/j.cor.2004.11.009 [14] A. Janiak, M.Y. Kovalyov, Scheduling deteriorating jobs, in: A. Janiak (Ed.), Scheduling in Computer and Manufacturing Systems, Warszawa, WKL, 2006, pp. 12 – 25. [15] Kuo, W. H.; Yang, D. L.: Note on ”single-machine and flowshop scheduling with a general learning effect model” and ”some single-machine and m-machine flowshop scheduling problems with learning considerations, Information sciences 180, No. 19, 3814-3816 (2010) · Zbl 1194.90041 · doi:10.1016/j.ins.2010.05.026 [16] Lee, K.; Choi, B. C.; Leung, J. Y. T.; Pinedo, M. L.: Approximation algorithms for multi-agent scheduling to minimize total weighted completion time, Information processing letters 109, 913-917 (2009) · Zbl 1205.68516 · doi:10.1016/j.ipl.2009.04.018 [17] Lee, W. C.; Chen, S. K.; Chen, W. C.; Wu, C. C.: A two-machine flowshop problem with two agents, Computers and operations research 38, 98-104 (2011) · Zbl 1231.90204 · doi:10.1016/j.cor.2010.04.002 [18] Lee, W. C.; Chen, S. K.; Wu, C. C.: Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem, Expert systems with applications 37, 6594-6601 (2010) [19] Lee, W. C.; Lai, P. J.: Scheduling problems with general effects of deterioration and learning, Information sciences 181, No. 6, 1164-1170 (2011) · Zbl 1208.90072 · doi:10.1016/j.ins.2010.11.026 [20] Li, Y.; Li, G.; Sun, L.; Xu, Z.: Single machine scheduling of deteriorating jobs to minimize total absolute differences in completion times, International journal of production economics 118, 424-429 (2009) [21] Liu, P.; Tang, L. X.; Zhou, X. Y.: Two-agent group scheduling with deteriorating jobs on a single machine, The international journal of advanced manufacturing technology 47, 657-664 (2010) [22] Liu, P.; Yi, N.; Zhou, X. Y.: Two-agent single-machine scheduling problems under increasing linear deterioration, Applied mathematical modelling 35, 2290-2296 (2011) · Zbl 1217.90108 · doi:10.1016/j.apm.2010.11.026 [23] Mazdeh, M. M.; Zaerpour, F.; Zareei, A.; Hajinezhad, A.: Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs, Applied mathematical modelling 34, 1498-1510 (2010) · Zbl 1193.90105 · doi:10.1016/j.apm.2009.08.023 [24] Mor, B.; Mosheiov, G.: Scheduling problems with two competing agents to minimize minmax and minsum earliness measures, European journal of operational research 206, 540-546 (2010) · Zbl 1188.90103 · doi:10.1016/j.ejor.2010.03.003 [25] 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) [26] Ng, C. T.; Cheng, C. T. E.; Yuan, J. J.: A note on the complexity of the two-agent scheduling on a single machine, Journal of combinatorial optimization 12, 387-394 (2006) · Zbl 1126.90027 · doi:10.1007/s10878-006-9001-0 [27] Pan, Q. K.; Tasgetiren, M. Fatih; Suganthan, P. N.; Chua, T. J.: A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem, Information sciences 181, No. 12, 2455-2468 (2011) [28] Qi, X.; Tu, F. S.: Scheduling a single-machine to minimize earliness penalties subject to the SLK due-date determination method, European journal of operational research 105, 502-508 (1998) · Zbl 0955.90031 · doi:10.1016/S0377-2217(97)00075-1 [29] Shabtay, D.: Scheduling and due date assignment to minimize earliness, tardiness, holding, due date assignment and batch delivery costs, International journal of production economics 123, 235-242 (2010) [30] Valente, J. M. S.: Local and global dominance conditions for the weighted earliness scheduling problem with no idle time, Computers & industrial engineering 51, 765-780 (2006) [31] Wan, G.; Vakati, R. S.; Leung, J. Y. T.; Pinedo, M.: Scheduling two agents with controllable processing times, European journal of operational research 205, 528-539 (2010) · Zbl 1188.90114 · doi:10.1016/j.ejor.2010.01.005 [32] Wang, J. B.: A note on single-machine scheduling with decreasing time-dependent job processing times, Applied mathematical modelling 34, 294-300 (2010) · Zbl 1185.90098 · doi:10.1016/j.apm.2009.04.018 [33] Wang, J. B.; Cheng, T. C. E.: Scheduling problems with the effects of deterioration and learning, Asia Pacific journal of operational research 24, 245-261 (2007) · Zbl 1121.90066 · doi:10.1142/S021759590700122X [34] Wang, J. B.; Jiang, Y.; Wang, G.: Single-machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning, The international journal of advanced manufacturing technology 41, 1221-1226 (2009) [35] Wang, X. R.; Huang, X.; Wang, J. B.: Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties, Applied mathematical modelling 35, 3509-3515 (2011) · Zbl 1221.90051 · doi:10.1016/j.apm.2011.01.005 [36] Wang, L. Y.; Wang, J. B.; Gao, W. J.; Huang, X.; Feng, E. M.: Two single-machine scheduling problems with the effects of deterioration and learning, The international journal of advanced manufacturing technology 46, 715-720 (2010) [37] Wang, X. Y.; Wang, M. Z.; Wang, J. B.: Flow shop scheduling to minimize makespan with decreasing linear deterioration, Computers & industrial engineering 60, 840-844 (2011) [38] Wang, J. B.; Wei, C. M.: Parallel machines scheduling with a deteriorating maintenance activity and total absolute differences penalties, Applied mathematics and computation 217, 8093-8099 (2011) · Zbl 1230.90103 · doi:10.1016/j.amc.2011.03.010 [39] Wang, J. B.; Xia, Z. Q.: Scheduling jobs under decreasing linear deterioration, Information processing letter 94, 63-69 (2005) · Zbl 1182.68359 · doi:10.1016/j.ipl.2004.12.018 [40] Wu, C. C.; Lee, W. C.; Shiau, Y. R.: Minimizing the total weighted completion time on a single machine under linear deterioration, International journal of advanced manufacturing technology 33, 1237-1243 (2007) [41] Yin, Y.; Xu, D.; Huang, X.: Notes on ”some single-machine scheduling problems with general position-dependent and time-dependent learning effect, Information sciences 181, No. 11, 2209-2217 (2011) · Zbl 1231.90223 · doi:10.1016/j.ins.2011.01.018 [42] Yang, S. J.; Yang, D. L.: Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities, Omega 38, 528-533 (2010) [43] Zhao, C.; Tang, H.: A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity, Computers and operations research 39, No. 6, 1300-1303 (2012) [44] Zhao, C.; Tang, H.: Rescheduling problems with deteriorating jobs under disruptions, Applied mathematical modelling 34, 238-243 (2010) · Zbl 1185.90114 · doi:10.1016/j.apm.2009.03.037 [45] Zhao, C. L.; Zhang, Q. L.; Tang, H. Y.: Scheduling problems under linear deterioration, Acta automatica sinica 29, 531-535 (2003)