NP-completeness of cell formation problem with grouping efficacy objective

References

• Ailon, Nir, Noa Avigdor-Elgrabli, Edo Liberty, and Anke van Zuylen. 2011. “Improved Approximation Algorithms for Bipartite Correlation Clustering.” In Algorithms – ESA 2011. 19th Annual European Symposium, edited by Camil Demetrescu, and Magnús M. Halldórsson, Lecture Notes in Computer Science 6942, 25–36. Cham: Springer International.
   Google Scholar
• Alhourani, Farouq. 2016. “Cellular Manufacturing System Design Considering Machines Reliability and Parts Alternative Process Routings.” International Journal of Production Research 54 (3): 846–863.
   Web of Science ®Google Scholar
• Amit, Noga. 2004. “The Bicluster Graph Editing Problem.” MS diss., Tel Aviv University.
   Google Scholar
• Arkat, J., H. Abdollahzadeh, and H. Ghahve. 2012. “A New Branch-and-bound Algorithm for Cell Formation Problem.” Applied Mathematical Modelling 36: 5091–5100.
   Web of Science ®Google Scholar
• Ballakur, A. 1985. “An Investigation of Part Family/Machine Group Formation for Designing Cellular Manufacturing Systems.” PhD diss., University of Wisconsin-Madison.
   Google Scholar
• Ballakur, A., and H. J. Steudel. 1987. “A Within Cell Utilization Based Heuristic for Designing Cellular Manufacturing Systems.” International Journal of Production Research 25: 639–665.
   Web of Science ®Google Scholar
• Battaïa, Olga, Alexandre Dolgui, and Nikolai Guschinsky. 2017. “Decision Support for Design of Reconfigurable Rotary Machining Systems for Family Part Production.” International Journal of Production Research 55 (5): 1368–1385.
   Web of Science ®Google Scholar
• Battaïa, Olga, Alexandre Dolgui, Sunderesh S. Heragu, Semyon M. Meerkov, and Manoj Kumar Tiwari. 2018. “Design for Manufacturing and Assembly/disassembly: Joint Design of Products and Production Systems.” International Journal of Production Research 56 (24): 7181–7189.
   Web of Science ®Google Scholar
• Bonnet, Edouard, Vangelis Paschos, and Florian Sikora. 2016. “Parameterized Exact and Approximation Algorithms for Maximum K -set Cover and Related Satisfiability Problems.” RAIRO – Theoretical Informatics and Applications 50 (3): 227–240.
   Web of Science ®Google Scholar
• Brusco, Michael J. 2015. “An Exact Algorithm for Maximizing Grouping Efficacy in Part-machine Clustering.” IIE Transactions 47 (6): 653–671.
   Web of Science ®Google Scholar
• Burbidge, J. L. 1975. The Introduction of Group Technology. New York: John Wiley & Sons.
   Google Scholar
• Busygin, S., O. Prokopyev, and P. M. Pardalos. 2008. “Biclustering in Data Mining.” Computers & Operations Research 35 (9): 2964–2987.
   Web of Science ®Google Scholar
• Bychkov, Ilya, and Mikhail Batsyn. 2018. “An Efficient Exact Model for the Cell Formation Problem with a Variable Number of Production Cells.” Computers & Operations Research 91: 112–120.
   Web of Science ®Google Scholar
• Bychkov, I., M. Batsyn, and P. M. Pardalos. 2014. “Exact Model for the Cell Formation Problem.” Optimization Letters 8 (8): 2203–2210.
   Web of Science ®Google Scholar
• Chan, F. T. S., K. W. Lau, L. Y. Chan, and V. H. Y. Lo. 2008. “Cell Formation Problem with Consideration of Both Intracellular and Intercellular Movements.” International Journal of Production Research 46 (10): 2589–2620.
   Web of Science ®Google Scholar
• Chung, S.-H., T.-H. Wu, and C.-C. Chang. 2011. “An Efficient Tabu Search Algorithm to the Cell Formation Problem with Alternative Routings and Machine Reliability Considerations.” Computers & Industrial Engineering 60 (1): 7–15.
   Web of Science ®Google Scholar
• De Sousa Filho, Gilberto F., Teobaldo L. Bulhões Júnior, Lucidio A. F. Cabral, Luiz Satoru Ochi, and Fábio Protti. 2017. “New Heuristics for the Bicluster Editing Problem.” Annals of Operations Research 258 (2): 781–814.
   Web of Science ®Google Scholar
• Dimopoulos, C., and A. Zalzala. 2000. “Recent Developments in Evolutionary Computation for Manufacturing Optimization: Problems, Solutions and Comparisons.” IEEE Transactions on Evolutionary Computation 4 (2): 93–113.
   Web of Science ®Google Scholar
• Dolgui, Alexandre, and Jean-Marie Proth. 2010. Supply Chain Engineering: Useful Methods and Techniques. London: Springer-Verlag.
   Google Scholar
• Drange, Pål Grønås, Felix Reidl, Fernando Sánchez Villaamil, and Somnath Sikdar. 2015. “Fast Biclustering by Dual Parameterization.” In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), edited by Thore Husfeldt and Iyad Kanj, Leibniz International Proceedings in Informatics, 402–413. Saarbrücken: Dagstuhl.
   Google Scholar
• Egilmez, G., B. Erenay, and G. A. Suer. 2014. “Stochastic Skill-based Manpower Allocation in a Cellular Manufacturing System.” Journal of Manufacturing Systems 33 (4): 578–588.
   Web of Science ®Google Scholar
• Eguia, Ignacio, Jose Carlos Molina, Sebastian Lozano, and Jesus Racero. 2017. “Cell Design and Multi-period Machine Loading in Cellular Reconfigurable Manufacturing Systems with Alternative Routing.” International Journal of Production Research 55 (10): 2775–2790.
   Web of Science ®Google Scholar
• Elbenani, B., and J. A. Ferland. 2012. “An Exact Method for Solving the Manufacturing Cell Formation Problem.” International Journal of Production Research 50 (15): 4038–4045.
   Web of Science ®Google Scholar
• Garey, M. R., and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: Freeman.
   Google Scholar
• Ghosh, S., A. Mahanti, R. Nagi, and D. S. Nau. 1996. “Manufacturing Cell Formation by State-space Search.” Annals of Operations Research 65 (1): 35–54.
   Google Scholar
• Golhar, D. Y., and C. L. Stamm. 1991. “The Just-in-time Philosophy: A Literature Review.” International Journal of Production Research 29 (4): 657–676.
   Web of Science ®Google Scholar
• Goncalves, J. F., and M. G. C. Resende. 2004. “An Evolutionary Algorithm for Manufacturing Cell Formation.” Computers & Industrial Engineering 47: 247–273.
   Web of Science ®Google Scholar
• Gunasekaran, A., S. K. Goyal, I. Virtanen, and P. Yli-Olli. 1994. “An Investigation Into the Application of Group Technology in Advanced Manufacturing Systems.” International Journal of Computer Integrated Manufacturing 7 (4): 215–228.
   Web of Science ®Google Scholar
• Guo, Jiong, Falk Hüffner, Christian Komusiewicz, and Yong Zhang. 2008. “Improved Algorithms for Bicluster Editing.” In Theory and Applications of Models of Computation. 5th International Conference TAMC 2008, edited by Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li, Lecture Notes in Computer Science 4978, 445–456, Cham: Springer International.
   Google Scholar
• James, T. L., E. C. Brown, and K. B. Keeling. 2007. “A Hybrid Grouping Genetic Algorithm for the Cell Formation Problem.” Computers & Operations Research 34 (7): 2059–2079.
   Web of Science ®Google Scholar
• Krushinsky, Dmitry, and Boris Goldengorin. 2012. “An Exact Model for Cell Formation in Group Technology.” Computational Management Science 9 (3): 323–338.
   Google Scholar
• Kumar, K. R., and M. P. Chandrasekharan. 1990. “Grouping Efficacy: A Quantitative Criterion for Goodness of Block Diagonal Forms of Binary Matrices in Group Technology.” International Journal of Production Research 28 (2): 233–243.
   Web of Science ®Google Scholar
• Kuo, Yiyo, Yen-Po Chen, and Yu-Cheng Wang. 2018. “Operator Assignment with Cell Loading and Product Sequencing in Labour-intensive Assembly Cells – A Case Study of a Bicycle Assembly Company.” International Journal of Production Research 56 (16): 5495–5510.
   Web of Science ®Google Scholar
• Kusiak, A., J. W. Boe, and C. Cheng. 1993. “Designing Cellular Manufacturing Systems: Branch-and-bound and A* Approaches.” IIE Transactions 25 (4): 46–56.
   Web of Science ®Google Scholar
• Liu, Chunfeng, Jufeng Wang, Joseph Y.-T. Leung, and Kai Li. 2016. “Solving Cell Formation and Task Scheduling in Cellular Manufacturing System by Discrete Bacteria Foraging Algorithm.” International Journal of Production Research 54 (3): 923–944.
   Web of Science ®Google Scholar
• Mak, K. L., Y. S. Wong, and X. X. Wang. 2000. “An Adaptive Genetic Algorithm for Manufacturing Cell Formation.” The International Journal of Advanced Manufacturing Technology 16 (7): 491–497.
   Web of Science ®Google Scholar
• Mitrofanov, S. P. 1959. Nauchnye Osnovy Gruppovoy Tekhnologii [Scientific Foundations of Group Technology]. Leningrad: Lenizdat.
   Google Scholar
• Nishino, Masaaki, Norihito Yasuda, Shin-ichi Minato, and Masaaki Nagata. 2017. “Efficient Algorithm for Enumerating All Solutions to An Exact Cover Problem.” NTT Technical Review 15 (11): 1–5.
   Google Scholar
• Norman, Bryan A., Wipawee Tharmmaphornphilas, Kim Lascola Needy, Bopaya Bidanda, and Rona Colosimo Warner. 2002. “Worker Assignment in Cellular Manufacturing Considering Technical and Human Skills.” International Journal of Production Research 40 (6): 1479–1492.
   Web of Science ®Google Scholar
• Paydar, M. M., and M. Saidi-Mehrabad. 2013. “A Hybrid Genetic-variable Neighborhood Search Algorithm for the Cell Formation Problem Based on Grouping Efficacy.” Computers & Operations Research 40 (4): 980–990.
   Web of Science ®Google Scholar
• Pinheiro, R. G. S., I. C. Martins, F. Protti, L. S. Ochi, L. G. Simonetti, and A. Subramanian. 2016. “On Solving Manufacturing Cell Formation Via Bicluster Editing.” European Journal of Operational Research 254 (3): 769–779.
   Web of Science ®Google Scholar
• Protti, Fábio, Maise Dantas da Silva, and Jayme Luiz Szwarcfiter. 2009. “Applying Modular Decomposition to Parameterized Cluster Editing Problems.” Theory of Computing Systems 44 (1): 91–104.
   Web of Science ®Google Scholar
• Rezaei-Malek, Mohammad, Jafar Razmi, Reza Tavakkoli-Moghaddam, and Alireza Taheri-Moghaddam. 2017. “Towards a Psychologically Consistent Cellular Manufacturing System.” International Journal of Production Research 55 (2): 492–518.
   Web of Science ®Google Scholar
• Solimanpur, M., S. Saeedi, and I. Mahdavi. 2010. “Solving Cell Formation Problem in Cellular Manufacturing Using Ant-colony-based Optimization.” The International Journal of Advanced Manufacturing Technology 50: 1135–1144.
   Web of Science ®Google Scholar
• Spiliopoulos, K., and S. Sofianopoulou. 1998. “An Optimal Tree Search Method for the Manufacturing Systems Cell Formation Problem.” European Journal of Operational Research 105: 537–551.
   Web of Science ®Google Scholar
• Sun, Peng, Jiong Guo, and Jan Baumbach. 2014. “Complexity of Dense Bicluster Editing Problems.” In Computing and Combinatorics. 20th International Conference COCOON 2014, edited by Zhipeng Cai, Alex Zelikovsky, Anu Bourgeois, Lecture Notes in Computer Science 8591, 154–165. Cham: Springer International.
   Google Scholar
• Sun, Peng, Nora K. Speicher, Richard Röttger, Jiong Guo, and Jan Baumbach. 2014. “Bi-Force: Large-scale Bicluster Editing and Its Application to Gene Expression Data Biclustering.” Nucleic Acids Research 42 (9): e78.
   PubMed Web of Science ®Google Scholar
• Tunnukij, T., and C. Hicks. 2009. “An Enhanced Grouping Genetic Algorithm for Solving the Cell Formation Problem.” International Journal of Production Research 47 (7): 1989–2007.
   Web of Science ®Google Scholar
• Utkina, I., M. Batsyn, and E. Batsyna. 2016. “A Branch and Bound Algorithm for a Fractional 0-1 Programming Problem.” In Discrete Optimization and Operations Research. 9th International Conference DOOR 2016, edited by Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, and P. Pardalos, Lecture Notes in Computer Science 9869, 244–255, Cham: Springer International.
   Google Scholar
• Utkina, I. E., M. V. Batsyn, and E. K. Batsyna. 2018. “A Branch-and-bound Algorithm for the Cell Formation Problem.” International Journal of Production Research 56 (9): 3262–3273.
   Web of Science ®Google Scholar
• Won, Youkyung, and Rasaratnam Logendran. 2015. “Effective Two-phase P-median Approach for the Balanced Cell Formation in the Design of Cellular Manufacturing System.” International Journal of Production Research 53 (9): 2730–2750.
   Web of Science ®Google Scholar
• Zeng, Chengkuan, Jiafu Tang, and Zhi-Ping Fan. 2019. “Auction-based Cooperation Mechanism for Cell Part Scheduling with Transportation Capacity Constraint.” International Journal of Production Research 57 (12): 3831–3846.
   Web of Science ®Google Scholar
• Žilinskas, Julius, Boris Goldengorin, and Panos M. Pardalos. 2015. “Pareto-optimal Front of Cell Formation Problem in Group Technology.” Journal of Global Optimization 61 (1): 91–108.
   Web of Science ®Google Scholar