Abstract
Competitive multi-agent scheduling has attracted increasingly more and more researchers’ attention recently. Inspired by the observation that a machine may not be always available during the whole planning horizon, we study a new category of scheduling problems where competitive two-agent scheduling and flexible periodic maintenance are considered simultaneously. As a start of this new topic, we focus our attention on establishing mathematical programming models for some of these scheduling problems. Specifically, we first present a framework for the general problem, and then construct various constraint blocks, which include common constraint block, constraint block for the relationship between start times and completion times of the jobs, constraint block for the relationship between the jobs and the maintenance activities, constraint block for various regular objective functions of the two agents, constraint block for the ranges of variables, and constraint block for the other constraint factors. One can establish mathematical programming models for at least 512 scheduling scenarios of this category easily based on these constraint blocks. The work presented in this paper is extremely useful for the production managers and software developers who are seeking for optimization models to generate optimal schedules for their problems.
Similar content being viewed by others
References
Agnetis A., Mirchandani P.B., Pacciarelli D., Pacifici A.: Scheduling problems with two competing agents. Oper. Res. 52, 229–242 (2004)
Ng C.T., Cheng T.C.E., Yuan J.J.: A note on the complexity of the problem of two-agent scheduling on a single machine. J. Comb. Optim. 12, 387–394 (2006)
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. Theor. Comput. Sci. 362, 273–281 (2006)
Cheng, T.C.E.; Ng, C.T.; Yuan, J.J.: Multi-agent scheduling on a single machine with max-form criteria. Eur. J. Oper. Res. 188, 603–609 (2008)
Agnetis A., Pacciarelli D., Pacifici A.: Multi-agent single machine scheduling. Ann. Oper. Res. 150, 3–15 (2007)
Baker K.R., Smith J.C.: A multiple-criterion model for machine scheduling. J. Sched. 6, 7–16 (2003)
Yuan, J.J.; Shang, W.P.; Feng, Q.: A note on the scheduling with two families of jobs. J. Sched. 8, 537–542 (2005)
LiuP. Tang L.X.: Two-agent scheduling with linear deteriorating jobs on a single machine. Lect. Notes Comput. Sci. 5092, 642–650 (2008)
Gawiejnowicz, S.; Lee, W.-C.; Lin, C.-L.; Wu, C.-C.: Single-machine scheduling of proportionally deteriorating jobs by two agents. J. Oper. Res. Soc. 62, 1983–1991 (2011)
Agnetis, A.; Pascale, G.; Pacciarelli, D.: A Lagrangian approach to single-machine scheduling problems with two competing agents. J. Sched. 12, 401–415 (2009)
Liu P., Yi N., Zhou X.: Two-agent single-machine scheduling problems under increasing linear deterioration. Appl. Math. Model. 35, 2290–2296 (2011)
Chen J.S.: Single-machine scheduling with flexible and periodic maintenance. J. Oper. Res. Soc. 57, 703–710 (2006)
Chen J.S.: Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan. Eur. J. Oper. Res. 190, 90–102 (2008)
Chen J.S.: Optimization models for the machine scheduling problem with a single flexible maintenance activity. Eng. Optim. 38, 53–71 (2006)
Yang, D.L.; Hung, C.L.; Hsu, C.J.; Chern, M.S.: Minimizing the makespan in a single machine scheduling problem with a flexible maintenance. J. Chin. Inst. Ind. Eng. 19, 63–66 (2002)
Xu, D.; Yin, Y.; Li, H.: A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan”. Eur. J. Oper. Res. 197, 825–827 (2009)
Chen W.J.: Scheduling of jobs and maintenance in a textile company. Int. J. Adv. Manuf. Tech. 31, 737–742 (2007)
Chen W.J.: Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. J. Oper. Res. Soc. 57, 410–415 (2006)
Chen, W.J.: An efficient algorithm for scheduling jobs on a machine with periodic maintenance. Int. J. Adv. Manuf. Tech. 34, 1173–1182 (2007)
Chen W.J.: Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega Int. J. Manage. S. 37, 591–599 (2009)
Liao, C.J.; Chen, W.J.: Single-machine scheduling with periodic maintenance and nonresumable jobs. Comput. Oper. Res. 30, 1335–1347 (2003)
Sbihi, M.; Varnier, C.: Single-machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness. Comput. Ind. Eng. 55, 830–840 (2008)
Xu, D.; Sun, K.; Li, H.: Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan. Comput. Oper. Res. 35, 1344–1349(2008)
Behnamian, J.; Zandieh, M.: Earliness and tardiness minimizing on a realistic hybrid flowshop scheduling with learning effect by advanced metaheuristic. Arab. J. Sci. Eng. 38, 1229–1242 (2013)
Molaei S., Vahdani B., Molaei S.: A molecular algorithm for an operation-based job shop scheduling problem. Arab. J. Sci. Eng. 38, 2993–3003 (2013)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Xu, D., Liu, A. & Yang, DL. Mathematical Programming Models for Competitive Two-Agent Single-Machine Scheduling with Flexible Periodic Maintenance Activities. Arab J Sci Eng 39, 3715–3722 (2014). https://doi.org/10.1007/s13369-014-1003-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13369-014-1003-0