A scheduling problem with three competing agents. (English) Zbl 1348.90283
Summary: Scheduling with multiple agents has become a popular topic in recent years. However, most of the research focused on problems with two competing agents. In this article, we consider a single-machine scheduling problem with three agents. The objective is to minimize the total weighted completion time of jobs from the first agent given that the maximum completion time of jobs from the second agent does not exceed an upper bound and the maintenance activity from the third agent must be performed within a specified period of time. A lower bound based on job division and several propositions are developed for the branch-and-bound algorithm, and a genetic algorithm with a local search is constructed to obtain near-optimal solutions. In addition, computational experiments are conducted to test the performance of the algorithms.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
scheduling; total weighted completion time; makespan; multiple-agent; single-machine; maintenance activityReferences:
| [1] | Kubzin, MA; Strusevich, VA., Planning machine maintenance in two-machine shop scheduling, Oper Res, 54, 789-800 (2006) · Zbl 1167.90669 |
| [2] | Baker, KR; Smith, JC., A multiple-criterion model for machine scheduling, J Sched, 6, 7-16 (2003) · Zbl 1154.90406 |
| [3] | Leung, JYT; Pinedo, M.; Wan, GH., Competitive two agents scheduling and its applications, Oper Res, 58, 458-469 (2010) · Zbl 1233.90163 |
| [4] | Agnetis, A.; Mirchandani, PB; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Oper Res, 52, 229-242 (2004) · Zbl 1165.90446 |
| [5] | Yuan, JJ; Shang, WP; Feng, Q., A note on the scheduling with two families of jobs, J Sched, 8, 537-542 (2005) · Zbl 1123.90040 |
| [6] | Cheng, TCE; Ng, CT; Yuan, JJ., Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theor Comput Sci, 362, 273-281 (2006) · Zbl 1100.68007 |
| [7] | Cheng, TCE; Ng, CT; Yuan, JJ., Multi-agent scheduling on a single machine with max-form criteria, Eur J Oper Res, 188, 603-609 (2008) · Zbl 1129.90023 |
| [8] | Ng, CT; Cheng, TCE; Yuan, JJ., A note on the complexity of the problem of two-agent scheduling on a single machine, J Comb Optim, 12, 387-394 (2006) · Zbl 1126.90027 |
| [9] | Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent single machine scheduling, Ann Oper Res, 150, 3-15 (2007) · Zbl 1144.90375 |
| [10] | Agnetis, A.; Pascale, G.; Pacciarelli, D., A Lagrangian approach to single-machine scheduling problems with two competing agents, J Sched, 12, 401-415 (2009) · Zbl 1185.90063 |
| [11] | Lee, WC; Wang, WJ; Shiau, YR; Wu, CC., A single-machine scheduling problem with two-agent and deteriorating jobs, Appl Math Model, 34, 3098-3107 (2010) · Zbl 1201.90080 |
| [12] | Lee, WC; Chen, SK; Chen, CW; Wu, CC., A two-machine flowshop problem with two agents, Comput Oper Res, 38, 98-104 (2011) · Zbl 1231.90204 |
| [13] | Wu, CC; Huang, SK; Lee, WC., Two-agent scheduling with learning consideration, Comput Ind Eng, 61, 1324-1335 (2011) |
| [14] | Wu, CC; Lee, WC; Liou, MJ., Single-machine scheduling with two competing agents and learning consideration, Inf Sci, 251, 136-149 (2013) · Zbl 1320.68054 |
| [15] | Yin, Y.; Cheng, SR; Wu, CC., Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties, Inf Sci, 189, 282-292 (2012) · Zbl 1247.90165 |
| [16] | Schmidt, G., Scheduling on semi-identical processors, Z Oper Res, 28, 153-162 (1984) · Zbl 0551.90044 |
| [17] | Ma, Y.; Chu, C.; Zuo, C., A survey of scheduling with deterministic machine availability constraints, Comput Ind Eng, 58, 199-211 (2010) |
| [18] | Wang, JB; Wei, CM., Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties, Appl Math Comput, 217, 8093-8099 (2011) · Zbl 1230.90103 |
| [19] | Cheng, TCE; Hsu, CJ; Yang, DL., Unrelated parallel-machine scheduling with deteriorating maintenance activities, Comput Ind Eng, 60, 602-605 (2011) |
| [20] | Lee, JY; Kim, YD., Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance, Comput Oper Res, 39, 2196-2205 (2011) · Zbl 1251.90162 |
| [21] | Yang, DL; Cheng, TCE; Yang, S. J.; Hsu, CJ., Unrelated parallel-machine scheduling with aging effects and multi-maintenance activities, Comput Oper Res, 39, 1458-1464 (2012) · Zbl 1251.90202 |
| [22] | Rustogi, K.; Strusevich, VA., Single machine scheduling with general positional deterioration and rate-modifying maintenance, Omega, 40, 791-804 (2012) |
| [23] | Lee, CY., Machine scheduling with an availability constraint, J Glob Optim, 9, 3-4, 395-416 (1996) · Zbl 0870.90071 |
| [25] | Posner, ME., Minimizing weighted completion times with deadlines, Oper Res, 33, 3, 562-574 (1985) · Zbl 0575.90030 |
| [26] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to algorithms (2001), The MIT Press Cambridge: The MIT Press Cambridge Massachusetts London, England · Zbl 1047.68161 |
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.
