A single-machine bi-criterion scheduling problem with two agents. (English) Zbl 1302.90086
Summary: The multiple-agent scheduling problems have received increasing attention recently. However, most of the research focuses on studying the computational complexity of the intractable cases or examining problems with a single criterion. Often a decision maker has to decide the schedule based on multiple criteria. In this paper, we consider a single machine problem where the objective is to minimize a linear combination of the total completion time and the maximum tardiness of jobs from the first agent given that no tardy jobs are allowed for the second agent. We develop a branch-and-bound algorithm and several simulated annealing algorithms to search for the optimal solution and near-optimal solutions for the problem, respectively. Computational experiments show that the proposed branch-and-bound algorithm could solve problems of up to 24 jobs in a reasonable amount of time and the performance of the combined simulated annealing algorithm is very good with an average error percentage of less than 0.5% for all the tested cases.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2002), Prentice Hall: Prentice Hall New Jersey · Zbl 1145.90394 |
| [2] | Naderi, B.; Fatemi Ghomi, S. M.T.; Aminnayeri, M.; Zandieh, M., Scheduling open shops with parallel machines to minimize total completion time, J. Comput. Appl. Math., 235, 1275-1287 (2011) · Zbl 1200.90083 |
| [3] | Wang, J. B.; Wei, C. M., Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties, Appl. Math. Comput., 217, 8093-8099 (2011) · Zbl 1230.90103 |
| [4] | Rudek, R., The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect, Appl. Math. Comput., 218, 6498-6510 (2012) · Zbl 1237.90096 |
| [5] | Xiao, Y. Y.; Zhang, R. Q.; Zhao, Q. H.; Kaku, I., Permutation flow shop scheduling with order acceptance and weighted tardiness, Appl. Math. Comput., 218, 7911-7916 (2012) · Zbl 1237.90101 |
| [6] | Lee, W. C.; Lu, Z. S., Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs, Appl. Math. Comput., 218, 8750-8757 (2012) · Zbl 1245.90034 |
| [7] | Peha, J. M., Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time, Comput. Oper. Res., 22, 1089-1100 (1995) · Zbl 0838.90067 |
| [9] | Kubzin, M. A.; Strusevich, V. A., Planning machine maintenance in two-machine shop scheduling, Oper. Res., 54, 789-800 (2006) · Zbl 1167.90669 |
| [10] | Balasubramanian, H.; Fowler, J. W.; Keha, A. B.; Pfund, M. E., Scheduling interfering job sets on parallel machines, Eur. J. Oper. Res., 199, 55-67 (2009) · Zbl 1176.90193 |
| [11] | Agnetis, A.; Mirchandani, P. B.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Oper. Res., 52, 229-242 (2004) · Zbl 1165.90446 |
| [12] | Baker, K. R.; Smith, J. C., A multiple-criterion model for machine scheduling, J. Sched., 6, 7-16 (2003) · Zbl 1154.90406 |
| [13] | Yuan, J. J.; Shang, W. P.; Feng, Q., A note on the scheduling with two families of jobs, J. Sched., 8, 537-542 (2005) · Zbl 1123.90040 |
| [14] | 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) · Zbl 1100.68007 |
| [15] | 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) · Zbl 1126.90027 |
| [16] | Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent single machine scheduling, Ann. Oper. Res., 150, 3-15 (2007) · Zbl 1144.90375 |
| [17] | 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 |
| [18] | 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, Inf. Process. Lett., 109, 913-917 (2009) · Zbl 1205.68516 |
| [19] | 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 |
| [20] | Leung, J. Y.T.; Pinedo, M.; Wan, G. H., Competitive two agents scheduling and its applications, Oper. Res., 58, 458-469 (2010) · Zbl 1233.90163 |
| [21] | Wan, G. H.; Vakati, S. R.; Leung, J. Y.T.; Pinedo, M., Scheduling two agents with controllable processing times, Eur. J. Oper. Res., 205, 528-539 (2010) · Zbl 1188.90114 |
| [22] | Liu, P.; Tang, L.; Zhou, X., Two-agent group scheduling with deteriorating jobs on a single machine, Int. J. Adv. Manuf. Technol., 47, 657-664 (2010) |
| [23] | Liu, P.; Zhou, X.; Tang, L., Two-agent single-machine scheduling with position- dependent processing times, Int. J. Adv. Manuf. Technol., 48, 325-331 (2010) |
| [24] | Lee, W. C.; Wang, W. J.; Shiau, Y. R.; Wu, C. C., A single-machine scheduling problem with two-agent and deteriorating jobs, Appl. Math. Modell., 34, 3098-3107 (2010) · Zbl 1201.90080 |
| [25] | Wu, C. C.; Huang, S. K.; Lee, W. C., Two-agent scheduling with learning consideration, Comput. Ind. Eng., 61, 1324-1335 (2011) |
| [26] | Lee, W. C.; Chen, S. K.; Wu, C. C., Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem, Expert Syst. Appl., 37, 6594-6601 (2010) |
| [27] | Cheng, T. C.E.; Wu, W. H.; Cheng, S. R.; Wu, C. C., Two-agent scheduling with position-based deteriorating jobs and learning effects, Appl. Math. Comput., 217, 8804-8824 (2011) · Zbl 1231.90182 |
| [29] | Liu, C. H., Using genetic algorithms for the coordinated scheduling problem of a batching machine and two-stage transportation, Appl. Math. Comput., 217, 10095-10104 (2011) · Zbl 1217.90037 |
| [30] | Gwizdałła, T. M., The role of crossover operator in the genetic optimization of magnetic models, Appl. Math. Comput., 217, 9368-9379 (2011) · Zbl 1219.78148 |
| [31] | Thangaraj, R.; Pant, M.; Abraham, A.; Bouvry, P., Particle swarm optimization: hybridization perspectives and experimental illustrations, Appl. Math. Comput., 217, 5208-5226 (2011) · Zbl 1209.65064 |
| [32] | Low, C. Y.; Hsu, C. J.; Su, C. T., A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance, Expert Syst. Appl., 37, 6429-6643 (2010) |
| [33] | Azadeh, A.; Sangari, M. S.; Amiri, A. S., A particle swarm algorithm for inspection optimization in serial multi-stage processes, Appl. Math. Modell., 36, 1455-1464 (2012) · Zbl 1243.90252 |
| [34] | Kirkpatrick, S.; Gelatt, C.; Vecchi, M., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [35] | Ben-Arieh, D.; Maimon, O., Annealing method for PCB assembly scheduling on two sequential machines, Int. J. Comput. Integr. Manuf., 5, 361-367 (1992) |
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.
