A two-machine flowshop problem with two agents. (English) Zbl 1231.90204
Summary: The multiple-agent scheduling problems have received increasing attention recently. However, most of the research focuses on deriving feasible/optimal solutions or examining the computational complexity of the intractable cases in a single machine. Often a number of operations have to be done on every job in many manufacturing and assembly facilities. In this paper, we consider a two-machine flowshop problem where the objective is to minimize the total completion time of the first agent with no tardy jobs for the second agent. We develop a branch-and-bound algorithm and simulated annealing heuristic algorithms to search for the optimal solution and near-optimal solutions for the problem, respectively.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Pinedo, M. L., Scheduling theory: algorithms and system (2002), Prentice-Hall: Prentice-Hall New Jersey · Zbl 1145.90394 |
| [2] | Agnetis, A.; Mirchandani, P. B.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Operations Research, 52, 229-242 (2004) · Zbl 1165.90446 |
| [3] | Curiel, I.; Pederzoli, G.; Tijs, S., Sequencing games, European Journal of Operational Research, 40, 344-351 (1989) · Zbl 0674.90107 |
| [4] | Hamers, H.; Borm, P.; Tijs, S., On games corresponding to sequencing situations with ready times, Mathematical Programming, 69, 471-483 (1995) · Zbl 0844.90120 |
| [5] | Kim K, Paulson BC, Petrie CJ, Lesser VR. Compensatory negotiation for agent-based schedule coordination. CIFE working paper #55, Stanford University, Stanford, CA, 1999.; Kim K, Paulson BC, Petrie CJ, Lesser VR. Compensatory negotiation for agent-based schedule coordination. CIFE working paper #55, Stanford University, Stanford, CA, 1999. |
| [6] | Schultz D, OH SH, Grecas CF, Albani M, Sanchez J, Arbib C, et al. A QoS concept for packet oriented SUMTS services. In: Proceedings of the 1st Mobile Summit, Thessaloniki, Greece, 2002.; Schultz D, OH SH, Grecas CF, Albani M, Sanchez J, Arbib C, et al. A QoS concept for packet oriented SUMTS services. In: Proceedings of the 1st Mobile Summit, Thessaloniki, Greece, 2002. |
| [7] | Baker, K. R.; Smith, J. C., A multiple-criterion model for machine scheduling, Journal of Scheduling, 6, 7-16 (2003) · Zbl 1154.90406 |
| [8] | 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 |
| [9] | 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 |
| [10] | 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 |
| [11] | Leung JYT, Pinedo M, Wan GH. Competitive two agents scheduling and its applications. Operations Research, 2009, in press, doi:10.1287/opre.1090.0744; Leung JYT, Pinedo M, Wan GH. Competitive two agents scheduling and its applications. Operations Research, 2009, in press, doi:10.1287/opre.1090.0744 |
| [12] | Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent single machine scheduling, Annals of Operations Research, 150, 3-15 (2007) · Zbl 1144.90375 |
| [13] | 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 |
| [14] | 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 |
| [15] | 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 |
| [16] | 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 |
| [17] | Agnetis, A.; Pacciarelli, D.; Pacifici, A., Combinatorial models for multi-agent scheduling problems, multiprocessor scheduling, theory and applications (2007), I-Tech Education and Publishing: I-Tech Education and Publishing Vienna, Austria |
| [18] | Kohler, W. H.; Steiglitz, K., Exact, approximate, and guaranteed accuracy algorithms for the flow-shop scheduling problem n/\(2/F/ \overline{F} \), Journal of Association for Computing Machinery, 22, 106-114 (1975) · Zbl 0313.68030 |
| [19] | Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flowshop and job shop scheduling, Mathematical Operations Research, 1, 2, 117-129 (1976) · Zbl 0396.90041 |
| [20] | Cadambi, B. V.; Sathe, Y. S., Two-machine flowshop scheduling to minimise mean flow time, Opsearch, 30, 35-41 (1993) · Zbl 0781.90050 |
| [21] | Pan, C. H.; Wu, C. C., An asymptotic two-phase algorithm to minimize total flow time for a two-machine flowshop, International Journal of System Science, 27, 925-930 (1996) · Zbl 0860.90074 |
| [22] | Wang, C.; Chu, C.; Proth, J. M., Efficient heuristic and optimal approaches for \(n/2/F/\sum C_i\) scheduling problems, International Journal of Production Economics, 44, 225-237 (1996) |
| [23] | Croce, F. D.; Narayan, V.; Tadei, R., The two-machine total completion time flow shop problem, European Journal of Operational Research, 90, 227-237 (1996) · Zbl 0916.90148 |
| [24] | Hoogeveen, J. A.; Kawaguchi, T., Minimizing total completion time in a two-machine flowshop: analysis of special cases, Mathematics of Operations Research, 24, 887-910 (1996) · Zbl 0977.90015 |
| [25] | Croce, F. D.; Ghirardi, M.; Tadei, R., An improved branch-and-bound algorithm for the two machine total completion time flow shop problem, European Journal of Operational Research, 139, 293-301 (2002) · Zbl 1001.90065 |
| [26] | Lee, W. C.; Wu, C. C., Minimizing total completion time in a two-machine flowshop with a learning effect, International Journal of Production Economics, 88, 85-93 (2004) |
| [27] | Wu, C. C.; Lee, W. C., Two-machine flowshop scheduling to minimize mean flow time under linear deterioration, International Journal of Production Economics, 103, 572-584 (2006) |
| [28] | Sung, C. S.; Kim, H. A., A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times, International Journal of Production Economics, 113, 1038-1048 (2008) |
| [29] | Huo, Y.; Li, H.; Zhao, H., Minimizing total completion time in two-machine flow shop with exact delays, Computers and Operations Research, 36, 2018-2030 (2009) · Zbl 1179.90136 |
| [30] | Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, studies in integer programming, Annals of Discrete Mathematics, 1, 343-362 (1977) · Zbl 0353.68067 |
| [31] | Kirkpatrick, S.; Gelatt, C.; Vecchi, M., Optimization by simulated annealing, Science, 220/4598, 671-680 (1983) · Zbl 1225.90162 |
| [32] | 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) |
| [33] | Fisher, M. L., A dual algorithm for the one-machine scheduling problem, Mathematical Programming, 11, 229-251 (1976) · Zbl 0359.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.
