Two-agent singe-machine scheduling with release times to minimize the total weighted completion time. (English) Zbl 1349.90329
Summary: In many management situations multiple agents pursuing different objectives compete on the usage of common processing resources. In this paper we study a two-agent single-machine scheduling problem with release times where the objective is to minimize the total weighted completion time of the jobs of one agent with the constraint that the maximum lateness of the jobs of the other agent does not exceed a given limit. We propose a branch-and-bound algorithm to solve the problem, and a primary and a secondary simulated annealing algorithm to find near-optimal solutions. We conduct computational experiments to test the effectiveness of the algorithms. The computational results show that the branch-and-bound algorithm can solve most of the problem instances with up to 24 jobs in a reasonable amount of time and the primary simulated annealing algorithm performs well with an average percentage error of less than 0.5% for all the tested cases.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C29 | Multi-objective and goal programming |
References:
| [1] | Baker, K. R.; Smith, J. C., A multiple-criterion model for machine scheduling, Journal of Scheduling, 6, 7-16 (2003) · Zbl 1154.90406 |
| [2] | Kim, K.; Paulson, B. C.; Petrie, C. J.; Lesser, V. R., Compensatory negotiation for agent-based schedule coordination. CIFE working paper #55 (1999), Stanford University: Stanford University Stanford, CA |
| [4] | Agnetis, A.; Mirchandani, P. B.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Operations Research, 52, 229-242 (2004) · Zbl 1165.90446 |
| [5] | 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 |
| [6] | 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, Journal of Combinatorial Optimization, 12, 387-394 (2006) · Zbl 1126.90027 |
| [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 |
| [8] | Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent single machine scheduling, Annals of Operations Research, 150, 3-15 (2007) · Zbl 1144.90375 |
| [9] | 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 |
| [10] | Liu, P.; Tang, L., Two-agent scheduling with linear deteriorating jobs on a single machine, Lecture Notes in Computer Science, 5092, 642-650 (2008) · Zbl 1148.90324 |
| [11] | Lee, K. B.; 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 |
| [12] | Agnetis, A.; Pascale, G.; Pacciarelli, D. A., Lagrangian approach to single-machine scheduling problems with two competing agents, Journal of Scheduling, 12, 401-415 (2009) · Zbl 1185.90063 |
| [13] | 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) |
| [14] | Leung, J. Y.T.; Pinedo, M.; Wan, G. H., Competitive two agents scheduling and its applications, Operations Research, 58, 458-469 (2010) · Zbl 1233.90163 |
| [15] | Lee, W. C.; Wang, W. J.; Shiau, Y. R.; Wu, C. C., A single-machine scheduling problem with two-agent and deteriorating jobs, Applied Mathematical Modelling, 34, 3098-3107 (2010) · Zbl 1201.90080 |
| [16] | Liu, P.; Zhou, X.; Tang, L., Two-agent single-machine scheduling with position-dependent processing times, International Journal of Advanced Manufacturing Technology, 48, 325-331 (2010) |
| [17] | Wan, G.; Vakati, S. R.; 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 |
| [18] | Lee, W. C.; Chen, S. K.; Chen, C. W.; Wu, C. C., A two-machine flowshop problem with two agents, Computers and Operations Research, 38, 98-104 (2011) · Zbl 1231.90204 |
| [19] | Hariri, A. M.A.; Potts, C. N., An algorithm for single machine sequencing with release dates to minimize total weighted completion time, Discrete Applied Mathematics, 5, 99-109 (1983) · Zbl 0498.90044 |
| [20] | Belouadah, H.; Posner, M. E.; Potts, C. N., Scheduling with release dates on a single machine to minimize total weighted completion time, Discrete Applied Mathematics, 36, 213-231 (1992) · Zbl 0757.90032 |
| [21] | Janiak, A., Single machine sequencing with linear models of release dates, Naval Research Logistics, 45, 99-113 (1998) · Zbl 0897.90127 |
| [22] | Eren, T., Minimizing the total weighted completion time on a single machine scheduling with release dates and a learning effect, Applied Mathematics and Computation, 208, 355-358 (2009) · Zbl 1155.90380 |
| [23] | Lee, W. C.; Wu, C. C.; Hsu, P. H., A single-machine learning effect scheduling problem with release times, Omega—The International Journal of Management Science, 38, 3-11 (2010) |
| [24] | Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362 (1977) · Zbl 0353.68067 |
| [25] | Kirkpatrick, S.; Gellat, C. D.; Vecchi, M. P., Optimization by simulated annealing algorithm, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [26] | Ben-Arieh, D.; Maimon, O., Annealing method for PCB assembly scheduling on two sequential machines, International Journal of Computer Integrated Manufacturing, 5, 361-367 (1992) |
| [27] | Chu, C. B., A branch-and-bound algorithm to minimize total flow time with unequal release dates, Naval Research Logistics, 39, 859-875 (1992) · Zbl 0766.90039 |
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.
