×

A branch and bound algorithm for the response time variability problem. (English) Zbl 1280.90045

Summary: The response time variability problem (RTVP) is an NP-hard scheduling problem that has been studied intensively recently and has a wide range of real-world applications in mixed-model assembly lines, multithreaded computer systems, network environments and others. The RTVP arises whenever products, clients or jobs need to be sequenced in order to minimise the variability in the time between two successive points at which they receive the necessary resources. To date, the best exact method for solving this problem is a mixed integer linear programming (MILP) model, which solves to optimality most of instances with up to 40 units to be scheduled in a reasonable amount of time. The goal of this paper is to increase the size of the instances that can be solved to optimality. We have designed an algorithm based on the branch and bound (B&B) technique to take advantage of the particular features of the problem. Our computational experiments show that the B&B algorithm is able to solve larger instances with up to 55 units to optimality in a reasonable time.

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adenso-Díaz, B., & Laguna, M. (2006). Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research, 54, 99-114. · Zbl 1167.90654 · doi:10.1287/opre.1050.0243
[2] Anily, S., Glass, C. A., & Hassin, R. (1998). The scheduling of maintenance service. Discrete Applied Mathematics, 82, 27-42. · Zbl 0897.90119 · doi:10.1016/S0166-218X(97)00119-4
[3] Bautista, J., Companys, R., & Corominas, A. (1997). Modelling and solving the production rate variation problem (PRVP). Top, 5, 221-239. · Zbl 0892.90090 · doi:10.1007/BF02568551
[4] Bautista, J., Companys, R., & Corominas, A. (2001). Solving the generalized apportionment problem through the optimization of discrepancy functions. European Journal of Operational Research, 131, 676-684. · Zbl 1014.91024 · doi:10.1016/S0377-2217(00)00110-7
[5] Bollapragada, S., Bussieck, M. R., & Mallik, S. (2004). Scheduling commercial videotapes in broadcast television. Operations Research, 52, 679-689. · Zbl 1165.90450 · doi:10.1287/opre.1040.0119
[6] Brusco, M. J. (2008). Scheduling advertising slots for television. Journal of the Operational Research Society, 59, 1363-1372. · Zbl 1155.90375 · doi:10.1057/palgrave.jors.2602481
[7] Corominas, A., Kubiak, W., & Moreno, N. (2007). Response time variability. Journal of Scheduling, 10, 97-110. · Zbl 1154.90433 · doi:10.1007/s10951-006-0002-8
[8] Corominas, A., García-Villoria, A., & Pastor, R. (2008). Solving the response time variability problem by means of multi-start and GRASP metaheuristics. Frontiers in Artificial Intelligence and Applications on Artificial Intelligence Research and Development, 184, 128-137.
[9] Corominas, A.; García-Villoria, A.; Pastor, R.; Bakhtadze, N. (ed.); Dolgui, A. (ed.), Solving the response time variable problem by means of a variable neighbourhood search algorithm, Moscow, Russia, June 3-5, 2009, Amsterdam
[10] Corominas, A., Kubiak, W., & Pastor, R. (2010). Mathematical programming modeling of the response time variability problem. European Journal of Operational Research, 200, 347-357. · Zbl 1177.90150 · doi:10.1016/j.ejor.2009.01.014
[11] Corominas, A., García-Villoria, A., & Pastor, R. (2011). Metaheuristic algorithms hybridized with variable neighbourhood search for solving the response time variability problem. Top. doi:10.1007/s11750-011-0175-y. · doi:10.1007/s11750-011-0175-y
[12] Dong, L.; Melhem, R.; Mosse, D., Time slot allocation for real-time messages with negotiable distance constrains requirements, Denver, CO
[13] Eiben, A. E., Hinterding, R., & Michalewicz, Z. (1999). Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 3, 124-141. · doi:10.1109/4235.771166
[14] García-Villoria, A., & Pastor, R. (2009). Introducing dynamic diversity into a discrete particle swarm optimization. Computers & Operations Research, 36, 951-966. · Zbl 1157.90563 · doi:10.1016/j.cor.2007.12.001
[15] García-Villoria, A., & Pastor, R. (2010a). Solving the response time variability problem by means of the electromagnetism-like mechanism. International Journal of Production Research, 48, 6701-6714. · doi:10.1080/00207540902862545
[16] García-Villoria, A., & Pastor, R. (2010b). Solving the response time variability problem by means of a psychoclonal approach. Journal of Heuristics, 16, 337-351. · Zbl 1187.90133 · doi:10.1007/s10732-008-9082-2
[17] García-Villoria, A., & Pastor, R. (2010c). Solving the response time variability problem by means of a genetic algorithm. European Journal of Operational Research, 202, 320-327. · Zbl 1175.90165 · doi:10.1016/j.ejor.2009.05.024
[18] García-Villoria, A., Salhi, S., Corominas, A., & Pastor, R. (2011). Hyper-heuristic approaches for the response time variability problem. European Journal of Operational Research, 211, 160-169. · Zbl 1218.90224 · doi:10.1016/j.ejor.2010.12.005
[19] Han, C. C., Lin, K. J., & Hou, C. J. (1996). Distance-constrained scheduling and its applications in real-time systems. IEEE Transactions on Computers, 45, 814-826. · Zbl 1055.68525 · doi:10.1109/12.508320
[20] Herrmann, J. W. (2007). Generating cyclic fair sequences using aggregation and stride scheduling (Technical report tr 2007-12). University of Maryland, USA. · Zbl 0892.90090
[21] Herrmann, J. W. (2011). Using aggregation to reduce response time variability in cyclic fair sequences. Journal of Scheduling, 14, 39-55. · Zbl 1208.90063 · doi:10.1007/s10951-009-0127-7
[22] Inman, R. R., & Bulfin, R. L. (1991). Sequencing JIT mixed-model assembly lines. Management Science, 37, 901-904. · Zbl 0729.90672 · doi:10.1287/mnsc.37.7.901
[23] Kubiak, W. (1993). Minimizing variation of production rates in just-in-time systems: a survey. European Journal of Operational Research, 66, 259-271. · Zbl 0771.90051 · doi:10.1016/0377-2217(93)90215-9
[24] Kubiak, W. (2009). Proportional optimization and fairness. Berlin: Springer. · Zbl 1169.90003
[25] Miltenburg, J. (1989). Level schedules for mixed-model assembly lines in just-in-time production systems. Management Science, 35, 192-207. · Zbl 0666.90040 · doi:10.1287/mnsc.35.2.192
[26] Monden, Y. (1983). Toyota production systems. Norcross: Industrial Engineering and Management Press.
[27] Pastor, R., & Corominas, A. (2004). Branch and win: OR tree search algorithms for solving combinatorial optimisation problems. Top, 12, 169-191. · Zbl 1148.90339 · doi:10.1007/BF02578930
[28] Salhi, S., & García-Villoria, A. (2011). An adaptive search for the response time variability problem. Journal of the Operational Research Society. doi:10.1057/jors.2011.46. · doi:10.1057/jors.2011.46
[29] Steiner, G., & Yeomans, S. (1993). Level schedules for mixed-model, just-in-time processes. Management Science, 39, 728-735. · Zbl 0783.90047 · doi:10.1287/mnsc.39.6.728
[30] Waldspurger, C. A.; Weihl, W. E., Lottery scheduling: flexible proportional-share resource management, Monterey, California, November 14-17, 1994
[31] Waldspurger, C. A., & Weihl, W. E. (1995). Stride scheduling: deterministic proportional-share resource management (Technical Report MIT/LCS/TM-528). Massachusetts Institute of Technology, MIT Laboratory for Computer Science. · Zbl 1155.90375
[32] Wei, W. D., & Liu, C. L. (1983). On a periodic maintenance problem. Operations Research Letters, 2, 90-93. · Zbl 0506.90032 · doi:10.1016/0167-6377(83)90044-5
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.