Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem. (English) Zbl 1305.90195
Summary: We study a generalized version of the minimum makespan jobshop problem in which multiple instances of each job are to be processed. The system starts with specified inventory levels in all buffers and finishes with some desired inventory levels of the buffers at the end of the planning horizon. A schedule that minimizes the completion time of all the operations is sought. We develop a polynomial time asymptotic approximation procedure for the problem. That is, the ratio between the value of the delivered solution and the optimal one converge into one, as the multiplicity of the problem increases. Our algorithm uses the solution of the linear relaxation of a time-indexed Mixed-Integer formulation of the problem. In addition, a heuristic method inspired by this approximation algorithm is presented and is numerically shown to out-perform known methods for a large set of standard test problems of moderate job multiplicity.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
Software:
OR-LibraryReferences:
| [1] | Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3), 391-401. · Zbl 0637.90051 · doi:10.1287/mnsc.34.3.391 |
| [2] | Amin, J., Shafia, M. A., & Tavakkoli-Moghaddam, R. (2011). A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 54(1-4), 309-322. |
| [3] | Beasley, J. E. (1990). Or-library, http://people.brunel.ac.uk/ mastjjb/jeb/info.html. |
| [4] | Bertsimas, D., & Gamarnik, D. (1999). Asymptotically optimal algorithm for job shop scheduling and packet routing. Journal of Algorithms, 33(2), 296-318. · Zbl 0944.68006 · doi:10.1006/jagm.1999.1047 |
| [5] | Bertsimas, D., Gamarnik, D., & Sethuraman, J. (2003). From fluid relaxations to practical algorithms for job shop scheduling: The holding cost objective. Operational Research, 51(5), 798-813. · Zbl 1165.90449 · doi:10.1287/opre.51.5.798.16748 |
| [6] | Bertsimas, D., & Sethuraman, J. (2002). From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective. Mathematical Programming, 92(1), 61-102. · Zbl 1040.90014 · doi:10.1007/s101070100272 |
| [7] | Blackstone, J. H., Phillips, D. T., & Hogg, G. L. (1982). A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 20(1), 27-45. · doi:10.1080/00207548208947745 |
| [8] | Boudoukh, T., Penn, M., & Weiss, G. (2001). Scheduling job shop with some identical or similar jobs. Journal of Scheduling, 4, 177-199. · Zbl 0979.90052 · doi:10.1002/jos.72 |
| [9] | Brauner, N., Crama, Y., Grigoriev, A., & van de Klundert, J. (2005). A framework for the complexity of high-multiplicity scheduling problems. Journal of Combinatorial Optimization, 9(3), 313-323. · Zbl 1079.90049 · doi:10.1007/s10878-005-1414-7 |
| [10] | Chekuri, C.; Khanna, S., Handbook of sheduling: Algorithms, models, and performance analysis, No. 33431, 11-1-11-30 (2004), Boca Raton, FL |
| [11] | Correa, J. R., Wagner, M. R. (2005). Lp-based online scheduling: From single to parallel machines. In M. Jnger & V. Kaibel (Eds.), Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol. 3509 (pp. 196-209). Berlin Heidelberg: Springer · Zbl 1119.90314 |
| [12] | Dai, J. G., & Weiss, G. (1996). Stability and instability of fluid models for certain re-entrant lines. Mathematics of Operations Research, 21(1), 115-134. · Zbl 0848.60086 · doi:10.1287/moor.21.1.115 |
| [13] | Dai, J. G., & Weiss, G. (2002). A fluid heuristic for minimizing makespan in job-shops. Operations Research, 50(4), 692-707. · Zbl 1163.90810 · doi:10.1287/opre.50.4.692.2860 |
| [14] | Goemans, M., Queyranne, M., Schulz, A. S., Skutella, M., & Wang, Y. (2002). Single machine scheduling with release dates. SIAM Journal on Discrete Mathematics, 15(2), 165-192. · Zbl 1009.90096 · doi:10.1137/S089548019936223X |
| [15] | Goldberg, L. A., Mike, P., Aravind S., Elizabeth S. (1997). Better approximation guarantees for job-shop scheduling (pp. 599-608). In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: SODA ’97, Society for Industrial and Applied Mathematics. · Zbl 1321.68503 |
| [16] | Hall, N. G., Lee, T. E., & Posner, M. E. (2002). The complexity of cyclic shop scheduling problems. Journal of Scheduling, 5(4), 307-327. · Zbl 1009.90048 · doi:10.1002/jos.100 |
| [17] | Kechadi, M-Tahar, & Low, Kok Seng. (2013). Recurrent neural network approach for cyclic job shop scheduling problem. Journal of Manufacturing Systems, 32(4), 689-699. · doi:10.1016/j.jmsy.2013.02.001 |
| [18] | Kimbrel, T., & Sviridenko, M. (2008). High-multiplicity cyclic job shop scheduling. Operations Research Letters, 36(5), 574-578. · Zbl 1210.90089 · doi:10.1016/j.orl.2008.06.005 |
| [19] | Lee, T. E., & Posner, M. E. (1997). Performance measures and schedule patterns in periodic job shops. Operational Research, 45(1), 72-91. · Zbl 0892.90102 · doi:10.1287/opre.45.1.72 |
| [20] | Lenstra, J. K., & Rinnooy-Kan, A. H. G. (1979). Computational complexity of discrete optimization problems. Annals of Discrete Mathematics, 4(8), 121-140. · Zbl 0411.68042 · doi:10.1016/S0167-5060(08)70821-5 |
| [21] | Leung, J. M. Y., Zhang, G., Yang, X., Mak, R., & Lam, K. (2004). Optimal cyclic multi-hoist scheduling: A mixed integer programming approach. Operations Research, 52(6), 965976. · Zbl 1165.90460 · doi:10.1287/opre.1040.0144 |
| [22] | Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42(6), 797-813. · Zbl 0880.90079 · doi:10.1287/mnsc.42.6.797 |
| [23] | Savelsbergh, Martin W. P., Uma, R. N., Joel W. (1998). An experimental study of Lp-based approximation algorithms for scheduling problems (pp. 453-462). In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: SODA ’98, Society for Industrial and Applied Mathematics. · Zbl 0938.68534 |
| [24] | Sevast’janov, S. V. (1994). On some geometric methods in scheduling theory: A survey. Discrete Applied Mathematics, 55(1), 59-82. · Zbl 0809.90082 · doi:10.1016/0166-218X(94)90036-1 |
| [25] | Shmoys, D. B., Stein, C., & Wein, J. (1994). Improved approximation algorithms for shop scheduling problems. SIAM Journal Computing, 23(3), 617-632. · Zbl 0814.68026 · doi:10.1137/S009753979222676X |
| [26] | Skutella, M. (2006). List scheduling in order of \[\alpha\] α-points on a single machine. Lecture Notes in Computer Science, 3484 250291. · Zbl 1132.90333 |
| [27] | Sotskov, Y. N., & Shakhlevich, N. V. (1995). Np-hardness of shop-scheduling problems with three jobs. Discrete Applied Mathematics, 59(3), 237-266. · Zbl 0837.90072 · doi:10.1016/0166-218X(95)80004-N |
| [28] | Weiss, G. (2008). A simplex based algorithm to solve separated continuous linear programs. Mathematical Programming Series A, 115(1), 151-198. · Zbl 1165.90011 · doi:10.1007/s10107-008-0217-x |
| [29] | Williamson, D. P., Hall, L. A., Hoogeveen, J. A., Hurkens, C. A. J., Lenstra, J. K., Sevast’janov, S. V., et al. (1997). Short shop schedules. Operations Research, 45(2), 288-294. · Zbl 0890.90112 · doi:10.1287/opre.45.2.288 |
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.
