Production programming in manufacturing systems (workshop type) with a combined mobile bottleneck and taboo search algorithm
##plugins.themes.bootstrap3.article.details##
Job Shop Scheduling has many applications in real production systems such as metal machining, printing, and textiles, among others. Commonly, in these manufacturing systems the main objective is the delivery of the jobs on time. In this research we present a hybrid approach that uses the Shifting Bottleneck (SB) and Tabu Search (TS) heuristics with the purpose of minimizing the Total Weighted Tardiness. The Shifting Bottleneck algorithm provides a feasible initial solution which is iteratively improved by the TS method. Additionally, several improvements were performed on the classical algorithms SB and TS such as new criteria for the selection of the critical machines and a number of innovative strategies of diversification and intensification. The performance of the proposed heuristic algorithm denominated CBBT was evaluated with 17 classical problems found in the literature. The implemented heuristic algorithm shows very competitive results compared with other approaches found in literature both in quality of the solutions and computational time.
sistemas flexibles de manufactura, programación de la producción, algoritmosFlexible manufacturing systems, production scheduling, algorithms
AKTURK, M. S. and OZDEMIR, D. A New Dominance Rule to Minimize Total Weighted Tardiness with Unequal Release Dates. European Journal of Operational Research, 2001, 135 (2): 394-412.
ANDERSON, E. J. and NYIRENDA, J. C. Two New Rules to Minimize Tardiness in a Job Shop. International Journal of Production Research, 1990, 28 (12): 2277-2292.
ARMENTANO, V. A. and SCRICH, C. R. Taboo Search for minimizing total Tardiness in a Job Shop. International Journal Production Economics, 2000, (63): 131-140.
ASANO, M. and OHTA, H. A Heuristic for Job Shop Scheduling to minimize total weighted Tardiness. Computers and Industrial Engineering, 2002, 42 (11): 137-147.
BAKER, K. R. and HAYYA, J. C. Priority Dispatching with Operation due Dates. Journal of Operations Management, 1982 (2): 167-175.
BARNES, J. W. and LAGUNA, M. A Tabu Search Experience in Production Scheduling. Annals of Operations Research, 1993 (41): 141-156.
CARLIER, J. and PISON, E. An Algorithm for Solving the Job-Shop Problem. Managing Science, 1989, 35: 164-176.
GLOVER, F. and LAGUNA, M. Tabú Search. Amsterdam: Kluwer Academic Publishers, 1997.
GRAHAM, R. L. et al. Optimization and Approximation in Deterministic Sequencing and Scheduling: A survey. Annals of Discrete Mathematics, 1979 (5): 287-326.
HOLSENBACK, J. E. et al. An Improved Heuristic for the Single-Machine, Weighted-Tardiness Problem. Omega, 1999, 27 (4): 485-495.
HOLTSCLAW, H. H. and UZSOY, R. Machine Criticidadity Measures and Subproblem Solution Procedures in Shifting Bottleneck Methods: A Computational Study. Journal of the Operational Research Society, 1996 (47): 666-677.
MASON, S. J., FLOWER, J. W. and CARLYLE, W. M. A Modified Shifting Bottleneck Heuristic for Minimizing Total Weighted Tardiness in Complex Job Shops. Journal of Scheduling, 2002 (5): 247-262.
NOWICKI, E. and SMUTNICKI, C. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 1996 (42): 797-813.
PEZZELLA, F. and MERELLI, E. A Taboo Search Method guided by Shifting Bottleneck for the Job Shop Scheduling Problem. European Journal of Operational Research, 2000, 120 (2): 297-310.
PINEDO M. and CHAO, X. Operations Scheduling with Applications in Manufacturing and Service. Boston: Irwin/McGraw-Hill, 1999.
PINEDO, M. and SINGER, M. A Shifting Bottleneck Heuristic for Minimizing the Total Weighted Tardiness in a Job Shop. Naval Research Logistics, 1999, 46 (1): 1-17.
PONNAMBALAM, S. G.; ARAVINDA, P. and SREENIVASA, R. P. Comparative Evaluation of Genetic Algorithms for Job-Shop Scheduling. Production Planning and Control, 2001, 12 (6): 560-574.
TAILLARD, É. Parallel Taboo Search Techniques for the Job-Shop Scheduling Problem. ORSA Journal on Computing, 1994, 16 (2): 108-117.
VAN LAARHOVEN, O.; AARTS, E. and LENSTRA, J. Job Shop Scheduling by Simulated Annealing. Operations Research, 1992 (40): 113-125.
VEPSALAINEN, V. and MORTON, T. Priority Rules for Job Shops Weighted Tardiness Cost. Management Science, 1987, 33 (8): 1035-1047.
WANG, T. Y. and WU, K. B. A Revised Simulated Annealing Algorithm for Obtaining the Minimum Total Tardiness in Job Shop Scheduling Problems. International Journal of Systems Science, 2000, 31 (4): 537-542.
This work is licensed under a Creative Commons Attribution 4.0 International License.