[en] In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting tooling problem is strongly N P-complete, even in case of unit loading and unloading costs. On the other hand, if the capacity of the tool magazine is also given as part of the input, we show that the problem is solvable in polynomial time. These results settle the complexity of a relevant variant of the tool switching problem. (C) 2006 Elsevier B.V. All rights reserved.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Crama, Yves ; Université de Liège - ULiège > HEC - École de gestion de l'ULiège > Recherche opérationnelle et gestion de la production
Albers, S., 2004. New results on Web Caching with Request Reordering. In: Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 04) 84-92.
Albers, S., Arora, S., Khanna, S., 1999. Page replacement for general caching problems. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms 31-40.
Bar-Noy A., Bar-Yehuda R., Freund A., Naor J., and Schieber B. A unified approach to approximating resource allocation and scheduling. Journal of the ACM 48 (2001) 1069-1090
Belady L.A. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal 5 (1966) 78-101
Crama Y. Combinatorial optimization models for production scheduling in automated manufacturing systems. European Journal of Operational Research 99 (1997) 136-153
Crama Y., and van de Klundert J. Worst-case performance of approximation algorithms for tool management problems. Naval Research Logistics 46 (1999) 445-462
Crama Y., Kolen A.W.J., Oerlemans A.G., and Spieksma F.C.R. Minimizing the number of tool switches on a flexible machine. The International Journal of Flexible Manufacturing Systems 6 (1994) 33-54
Djellab H., Djellab K., and Gourgand M. A new heuristic based on a hypergraph representation for the tool switching problem. International Journal of Production Economics 64 (2000) 165-176
Feder T., Motwani R., Panigrahy R., Seiden S., van Stee R., and Zhu A. Combining request scheduling with web caching. Theoretical Computer Science 324 (2004) 201-218
Garey M.R., and Johnson D.S. Computers and intractability. A guide to the theory of NP-completeness. (1979), W.H. Freeman and Company, New York
Irani S., 1997. Page replacement with multi-size pages and applications to web caching. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing 701-710.
Jain S., Johnson M.E., and Safai F. Implementing setup optimization on the shop floor. Operations Research 43 (1996) 843-851
Laporte G., Salazar J.J., and Semet F. Exact algorithms for the job sequencing and the tool switching problem. IIE Transactions 36 (2004) 37-45
Matzliach B., and Tzur M. Storage management of items in two levels of availability. European Journal of Operational Research 121 (2000) 363-379
Privault C., and Finke G. Modelling a tool switching problem on a single NC-machine. Journal of Intelligent Manufacturing 6 (1995) 87-94
Song C.Y., and Hwang H. Optimal tooling policy for a tool switching problem of a flexible machine with automatic tool transporter. International Journal of Production Research 40 (2002) 873-883
Stecke K.E. Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems. Management Science 29 (1983) 273-288
Tang C.S., and Denardo E.V. Models arising from a flexible manufacturing machine, part I: minimization of the number of tool switches. Operations Research 36 (1988) 767-777
Tzur M., and Altman A. Minimization of tool switches for a flexible manufacturing machine with slot assignment of different tool sizes. IIE Transactions 36 (2004) 95-110
Zhou B.H., Xi L.F., and Cao Y.S. A beam-search-based algorithm for the tool switching problem on a flexible machine. International Journal of Advanced Manufacturing Technology 25 (2005) 876-882
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
