A new multicommodity flow model for the job sequencing and tool switching problem

References

• Agapiou, J. S. 1991. “Sequence of Operations Optimization in Single-stage Multifunctional Systems.” Journal of Manufacturing Systems 10 (3): 194–208.
   Web of Science ®Google Scholar
• Ahmadi, E., B. Goldengorin, G. A. Suer, and H. Mosadegh. 2018. “A Hybrid Method of 2-TSP and Novel Learning-based GA for Job Sequencing and Tool Switching Problem.” Applied Soft Computing65: 214–229.
   Web of Science ®Google Scholar
• Al-Fawzan, M. A., and K. S. Al-Sultan. 2002. “A Tabu Search Based Algorithm for Minimizing the Number of Tool Switches on a Flexible Machine.” Computers & Industrial Engineering 44: 35–47.
   Web of Science ®Google Scholar
• Amaya, J. E., C. Cotta, and A. J. Fernández-Leiva. 2010. “Hybrid Cooperation Models for the Tool Switching Problem.” In Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), edited by J.R. González, D.A. Pelta, C. Cruz, G. Terrazas, and N. Krasnogor, Studies in Computational Intelligence, Vol. 284. Berlin, Heidelberg: Springer.
   Google Scholar
• Amaya, J. E., C. Cotta, and A. J. Fernández-Leiva. 2011. “Memetic Cooperative Models for the Tool Switching Problem.” Memetic Computing 3 (3): 199–216.
   Google Scholar
• Amaya, J. E., C. Cotta, and A. J. Fernández-Leiva. 2012. “Solving the Tool Switching Problem with Memetic Algorithms.” Artificial Intelligence for Engineering Design, Analysis and Manufacturing 26: 221–235.
   Web of Science ®Google Scholar
• Amaya, J. E., C. Cotta, and A. J. Fernández-Leiva. 2013. “Cross Entropy-based Memetic Algorithms: An Application Study Over the Tool Switching Problem.” International Journal of Computational Intelligence Systems 6 (3): 559–584.
   Web of Science ®Google Scholar
• Amaya, J. E., C. Cotta, A. J. Fernández-Leiva, and P. García-Sánchez. 2019. “Deep Memetic Models for Combinatorial Optimization Problems: Application to the Tool Switching Problem.” Memetic Computing 12: 3–22.
   Web of Science ®Google Scholar
• Amaya, J. E., C. Cotta, and A. J. Fernández. 2008. “A Memetic Algorithm for the Tool Switching Problem.” In Hybrid Metaheuristics HM 2008, edited by M. J. Blesa et al., Lecture Notes in Computer Science, Vol. 5296. Berlin, Heidelberg: Springer.
   Google Scholar
• Bard, J. F. 1988. “A Heuristic for Minimizing the Number of Tool Switches on a Flexible Machine.” IIE Transactions 20 (4): 382–391.
   Web of Science ®Google Scholar
• Baykasoy̆lu, A., and F. B. Ozsoydan. 2016. “An Improved Approach for Determination of Index Positions on CNC Magazines with Cutting Tool Duplications by Integrating Shortest Path Algorithm.” International Journal of Production Research 54 (3): 742–760.
   Web of Science ®Google Scholar
• Baykasoy̆lu, A., and F. B. Ozsoydan. 2017. “Minimizing Tool Switching and Indexing Times with Tool Duplications in Automatic Machines.” The International Journal of Advanced Manufacturing Technology 89: 1775–1789.
   Web of Science ®Google Scholar
• Baykasoy̆lu, A., and F. B. Ozsoydan. 2018. “Minimisation of Non-machining Times in Operating Automatic Tool Changers of Machine Tools Under Dynamic Operating Conditions.” International Journal of Production Research 56 (4): 1548–1564.
   Web of Science ®Google Scholar
• Becceneri, J. C., H. H. Yanasse, and N. Y. Soma. 2004. “A Method for Solving the Minimization of the Maximum Number of Open Stacks Problem Within a Cutting Process.” Computers & Operations Research 31 (14): 2315–2332.
   Web of Science ®Google Scholar
• Beezao, A. C. 2016. “O problema de minimização de troca de ferramentas.” PhD thesis, University of São Paulo.
   Google Scholar
• Bentley, J. J. 1992. “Fast Algorithms for Geometric Traveling Salesman Problems.” ORSA Journal on Computing 4 (4): 387–411.
   Google Scholar
• Burger, A. P., C. G. Jacobs, J. H. van Vuuren, and S. E. Visagie. 2015. “Scheduling Multi-colour Print Jobs with Sequence-dependent Setup Times.” Journal of Scheduling 18 (2): 131–145.
   Web of Science ®Google Scholar
• Calmels, D. 2018. “The Job Sequencing and Tool Switching Problem: State-of-the-art Literature Review, Classification, and Trends.” International Journal of Production Research 57 (15-16): 5005–5025.
   Web of Science ®Google Scholar
• Catanzaro, D., L. Gouveia, and M. Labbé. 2015. “Improved Integer Linear Programming Formulations for the Job Sequencing and Tool Switching Problem.” European Journal of Operational Research 244: 766–777.
   Web of Science ®Google Scholar
• Chaves, A. A., L. A. N. Lorena, E. L. F. Senne, and M. G. C. Resende. 2016. “Hybrid Method with CS and BRKGA Applied to the Minimization of Tool Switches Problem.” Computers & Operations Research 67: 174–183.
   Web of Science ®Google Scholar
• Chaves, A. A., E. L. F. Senne, and H. H. Yanasse. 2012. “Uma Nova Heurística Para O Problema De Minimização De Trocas De Ferramentas.” Gestão & Produção 19 (1): 17–30.
   Google Scholar
• Crama, Y., A. W. Kolen, A. G. Oerlemans, and F. C. R. Spiesksma. 1994. “Minimizing the Number of Tool Switches on a Flexible Machine.” The International Journal of Flexible Manufacturing System 6: 33–54.
   Google Scholar
• Dadashi, H., S. Moslemi, and A. Mirzazadeh. 2016. “Optimization of a New Tool Switching Problem in Flexible Manufacturing Systems with a Tool Life by a Genetic Algorithm.” International Journal of Industrial and Manufacturing Systems Engineering 1 (3): 52–58.
   Google Scholar
• Dantzig, G. B., D. R. Fulkerson, and S. M. Johnson. 1954. “Solution of a Large-scale Traveling Salesman Problem.” Operations Research 2: 393–410.
   Web of Science ®Google Scholar
• Dehaybe, H. 2018. “An Ant Colony System for solving the Job Sequencing and Tool Switching Problem”. Dissertation, Louvain School of Management. Université catholique de Louvain.
   Google Scholar
• Desrochers, M., and G. Laporte. 1991. “Improvements and Extensions to the Miller-Tucker-Zemlin Subtour Elimination Constraints.” Operations Research Letters 10: 27–36.
   Web of Science ®Google Scholar
• Djellab, H., K. Djellab, and M. Gourgand. 2000. “A New Heuristic Based on a Hypergraph Representation for the Tool Switching Problem.” International Journal of Production Economics 64: 165–176.
   Web of Science ®Google Scholar
• Fathi, Y., and K. W. Barnette. 2002. “Heuristic Procedures for the Parallel Machine Problem with Tool Switches.” International Journal of Production Research 40 (1): 151–164.
   Web of Science ®Google Scholar
• Fourer, R., D. M. Gay, and B. W. Kernighan. 2002. AMPL – A Modeling Language for Mathematical Programming. 2nd ed. San Francisco, California: Cengage Learning.
   Google Scholar
• Fulkerson, D. R., and D. A. Gross. 1965. “Incidence Matrices and Interval Graphs.” Pacific Journal of Mathematics 15 (3): 835–855.
   Web of Science ®Google Scholar
• Gamila, M. A., and S. Motavalli. 2003. “A Modeling Technique for Loading and Scheduling Problems in FMS.” Robotics and Computer Integrated Manufacturing 19: 45–54.
   Web of Science ®Google Scholar
• Gao, N., and S. K. Moon. 2019. “An Integrated Two-Stage Optimization Method for Job-Shop Bottleneck Planning and Scheduling.” In IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), 855–859. Macao.
   Google Scholar
• Gendreau, M., and A. Hertz. 1992. “New Insertion and Postoptimization Procedures for the Traveling Salesman Problem.” Operations Research 40: 1086–1094.
   Web of Science ®Google Scholar
• Ghiani, G., A. Grieco, and E. Guerriero. 2007. “An Exact Solution to the TLP Problem in An NC Machine.” Robotics and Computer-Integrated Manufacturing 23: 645–649.
   Web of Science ®Google Scholar
• Ghiani, G., A. Grieco, and E. Guerriero. 2010. “Solving the Job Sequencing and Tool Switching Problem As a Nonlinear Least Cost Hamiltonian Cycle Problem.” Networks 55 (4): 379–385.
   Web of Science ®Google Scholar
• Ghrayeb, O. A., N. Phojanamongkolkij, and P. R. Finch. 2003. “A Mathematical Model and Heuristic Procedure to Schedule Printed Circuit Packs on Sequencers.” International Journal of Production Research 41 (16): 3849–3860.
   Web of Science ®Google Scholar
• Gökgür, B., B. Hnich, and S. Özpeynirci. 2018. “Parallel Machine Scheduling with Tool Loading: A Constraint Programming Approach.” International Journal of Production Research 54: 1–17.
   Google Scholar
• Hertz, A., G. Laporte, M. Mittaz, and K. E. Stecke. 1998. “Heuristics for Minimizing Tool Switches when Scheduling Part Types on a Flexible Machine.” IIE Transactions 30 (8): 689–694.
   Web of Science ®Google Scholar
• Hoffman, A. J., A. W. J. Kolen, and M. Sakarovitch. 1985. “Totally Balanced and Greedy Matrices.” SIAM Journal on Algebraic and Discrete Methods 6 (4): 721–730.
   Google Scholar
• IBM ILOG CPLEX Optimization Studio. 2016. CPLEX User's Manual, Copyright, ILOG.
   Google Scholar
• Jäger, G., and P. Molitor. 2008. “Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order.” In Combinatorial Optimization and Applications. COCOA 2008, edited by B. Yang, D.Z. Du, C. A. Wang, Lecture Notes in Computer Science, Vol. 5165. Berlin, Heidelberg: Springer.
   Google Scholar
• Karzan, F. K., and M. Azizoglu. 2008. “The Tool Transporter Movements Problem in Flexible Manufacturing Systems.” International Journal of Production Research 46 (11): 3059–3084.
   Web of Science ®Google Scholar
• Kou, L. T. 1977. “Polynomial Complete Consecutive Information Retrieval Problems.” SIAM Journal on Computing 6: 67–75.
   Google Scholar
• Laporte, G., J. J. Salazar-Gonzáles, and F. Semet. 2004. “Exact Algorithms for the Job Sequencing and Tool Switching Problem.” IIE Transactions 36: 37–45.
   Web of Science ®Google Scholar
• Matzliach, B., and M. Tzur. 1998. “The Online Tool Switching Problem with Non-uniform Tool Size.” International Journal of Production Research 36 (12): 3407–3420.
   Web of Science ®Google Scholar
• McGeogh, L., and D. Sleator. 1991. “A Strongly Competitive Randomized Paging Algorithm.” Algorithmica 6: 816–825.
   Web of Science ®Google Scholar
• Melnyk, S. A., S. Ghosh, and G. L. Ragatz. 1989. “Tooling Constraints and Shop Floor Scheduling: a Simulation Study.” Journal of Operations Management 8: 69–89.
   Google Scholar
• Möhring, R. H. 1990. “Graph Problems Related to Gate Matrix Layout and PLA Folding.” In Computational Graph Theory. Computing Supplementum, edited by G. Tinhofer, E. Mayr, H. Noltemeier, M. M. Syslo. Vol. 7. Vienna: Springer.
   Google Scholar
• Oerlemans, A. 1992. “Production Planning for Flexible Manufacturing Systems.” PhD thesis, University of Limburg, Maastricht, Limburg, Netherlands.
   Google Scholar
• Paiva, G. S., and M. A. M. Carvalho. 2017. “Improved Heuristic Algorithms for the Job Sequencing and Tool Switching Problem.” Computers & Operations Research 88: 208–219.
   Web of Science ®Google Scholar
• Privault, C., and G. Finke. 1995. “Modelling a Tool Switching Problem on a Single NC-machine.” Journal of Intelligent Manufacturing 6: 87–94.
   Web of Science ®Google Scholar
• Privault, C., and G. Finke. 2000. “k-server Problems with Bulk Requests: An Application to Tool Switching in Manufacturing.” Annals of Operations Research 96: 255–269.
   Web of Science ®Google Scholar
• Raduly-Baka, C., J. Mäkilä, M. Johnsson, and O. S. Nevalainen. 2018. “Efficient Tool Loading Heuristic for Machines with Modular Feeders.” Procedia Manufacturing 17: 968–975.
   Google Scholar
• Rubinstein, R. 1999. “The Cross-entropy Method for Combinatorial and Continuous Optimization.” Methodology and Computing in Applied Probability 1: 127–190.
   Google Scholar
• Rupe, J., and W. Kuo. 1997. “Solutions to a Modified Tool Loading Problem for a Single FMM.” International Journal of Production Research 35 (8): 2253–2268.
   Web of Science ®Google Scholar
• Salonen, K., C. Raduly-Baka, and O. S. Nevalainen. 2006. “A Note on the Tool Switching Problem of a Flexible Machine.” Computers & Industrial Engineering 50: 458–465.
   Web of Science ®Google Scholar
• Salonen, K., J. Smed, M. Johnsson, and O. Nevalainen. 2006. “Grouping and Sequencing PCB Assembly Jobs with Minimum Feeder Setups.” Robotics and Computer Integrated Manufacturing 22: 297–305.
   Web of Science ®Google Scholar
• Senne, E. L. F., and H. H. Yanasse. 2009. “Beam Search Algorithms for Minimizing Tool Switches on a Flexible Manufacturing System.” In Proceedings of the XI WSEAS International Conference on Mathematical and Computational Methods in Science and Engineering. Vol. 1, 68–72, Baltimore, USA. WSEAS Press.
   Google Scholar
• Shirazi, R., and G. D. M. Frizelle. 2001. “Minimizing the Number of Tool Switches on a Fexible Machine: An Empirical Study.” International Journal of Production Research 39 (15): 3547–3560.
   Web of Science ®Google Scholar
• Smed, J., M. Johnsson, M. Puranen, T. Leipãlã, and O. Nevalainen. 1999. “Job Grouping in Surface Mounted Component Printing.” Robotics and Computer-Integrated Manufacturing 15 (1): 39–49.
   Web of Science ®Google Scholar
• Song, C. Y., and H. Hwang. 2002. “Optimal Tooling Policy for a Tool Switching Problem of a Flexible Machine with Automatic Tool Transporter.” International Journal of Production Research 40 (4): 873–883.
   Web of Science ®Google Scholar
• Stecke, K. E., and J. J. Solberg. 1981. “Loading and Control Policies for a Flexible Manufacturing System.” International Journal of Production Research 19 (5): 481–190.
   Web of Science ®Google Scholar
• Stützle, T. 1999. “Iterated Local Search for the Quadratic Assignment Problem.” PhD thesis, TU Darmstadt.
   Google Scholar
• Tang, C. S., and E. V. Denardo. 1988a. “Models Arising From a Flexible Manufacturing Machine, Part I: Minimization of the Number of Tool Switches.” Operational Research 36 (5): 767–777.
   Web of Science ®Google Scholar
• Tang, C. S., and E. V. Denardo. 1988b. “Models Arising From a Flexible Manufacturing Machine, Part II: Minimization of the Number of Switching Instants.” Operations Research 36 (5): 778–784.
   Web of Science ®Google Scholar
• Van Hop, N., and N. N. Nagarur. 2004. “The Scheduling Problem of PCBs for Multiple Non-identical Parallel Machines.” European Journal of Operational Research 158: 577–594.
   Web of Science ®Google Scholar
• Widmer, M. 1991. “Job Shop Scheduling with Tooling Constraints: A Tabu Search Approach.” The Journal of the Operational Research Society 42 (1): 75–82.
   Web of Science ®Google Scholar
• Yanasse, H. H. 1997. “A Transformation for Solving a Pattern Sequencing Problem in the Wood Cut Industry.” Pesquisa Operacional 17 (1): 57–70.
   Google Scholar
• Yanasse, H. H. 2009. “Um novo limitante inferior para o problema de minimização de trocas de ferramentas.” In Annals of XLI Simpósio Brasileiro de Pesquisa Operacional, 2841–2848, Porto Seguro, Brasil.
   Google Scholar
• Yanasse, H. H., and M. Lamosa. 2005. “An application of the generalized travelling salesman problem: the minimization of tool switches problem.” In International Annual Scientific Conference of the German Operations Research Society, Bremen, Germany, 90–100.
   Google Scholar
• Yanasse, H., and M. Lamosa. 2006. “On Solving the Minimization of Tool Switches Problem Using Graphs.” In XII ICIEOM – Fortaleza, CE, Brazil, 1–9.
   Google Scholar
• Yanasse, H. H., and M. J. Pinto. 2002. “The Minimization of Tool Switches Problem as a Network Flow Problem with side Constraints.” Annals of XXXIV Simpósio Brasileiro de Pesquisa Operacional, Rio de Janeiro, Brasil.
   Google Scholar
• Yanasse, H. H., R. d. C. M. Rodrigues, and E. L. F. Senne. 2009. “Um Algoritmo Enumerativo Baseado Em Ordenamento Parcial Para Resolução Do Problema De Minimização De Trocas De Ferramentas.” Gestão & Produção 16 (3): 370–381.
   Google Scholar
• Zeballos, L. 2010. “A Constraint Programming Approach to Tool Allocation and Production Scheduling in Flexible Manufacturing Systems.” Robotics and Computer-Integrated Manufacturing 26 (6): 725–743.
   Web of Science ®Google Scholar
• Zhang, J. H., and S. Hinduja. 1995. “Determination of the Optimum Tool Set for a Given Batch of Turned Components.” Annals of the CIRP 44 (1): 445–450.
   Google Scholar
• Zhou, B. H., L. F. Xi, and Y. S. Cao. 2005. “A Beam-search-based Algorithm for the Tool Switching Problem on a Flexible Machine.” The International Journal of Advanced Manufacturing Technology 25: 876–882.
   Web of Science ®Google Scholar