Модели и алгоритмы для задачи о формировании производственных ячеек тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Бычков Илья Сергеевич

• Бычков Илья Сергеевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Бычков Илья Сергеевич

Contents

1 Introduction

2 Problem statement

2.1 General problem statement

2.2 Objective functions

2.3 Mathematical model

3 Existing approaches and models

3.1 State-of-art heuristic algorithms

3.2 State-of-art exact models and approaches

4 Contents

4.1 Problem complexity

4.2 An exact approach based on fixing the value of grouping efficacy denominator

4.3 An exact approach based on the two-index model and Dinkelbach algorithm

4.4 Multi-start variable neighborhood search algorithm

5 Conclusion

6 References

7 Appendices

A Article "An efficient exact model for the cell formation problem with a

variable number of production cells"

B Article "Exact model for the cell formation problem"

C Article "NP-completeness of cell formation problem with grouping efficacy

objective"

D Article "Heuristic Algorithm for the Cell Formation Problem"

E Article "Heuristic for Maximizing Grouping Efficiency in the Cell Formation Problem"

F Article "Pattern-based heuristic for the cell formation problem in Group

Technology"

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы для задачи о формировании производственных ячеек»

1 Introduction

Designing a manufacturing layout is one of the most important stages in the process of building a new manufacturing system or adjusting an existing system to changing environment (new resources allocation, changes in volumes or products etc.). To design a manufacturing layout means to locate manufacturing facilities in order to get different kind of advantages. These advantages include simplifying scheduling, reducing costs of material movement, machines utilization and many others.

Depending on the environment problems static or dynamic manufacturing layout is considered [27]. One of the most popular static layouts is the so-called cellular layout. Cellular manufacturing is a part of Group Technology (GT) concept which was introduced by Russian industrial engineering scientist Sergey Mitrofanov [46, 47] and John Burbidge in the west [9, 10, 11, 12]. GT is a strategy which helps to optimize production process in terms of materials handling and management of a batch-manufacturing system. The key idea of GT is that parts which are similar in terms of manufacturing characteristics should be processed within one unit called manufacturing cell. This idea leads to dividing the manufacturing system into subsystems by determining pars families and machine groups. Each manufacturing cell is associated with a certain physical location, machines set up and responsible for handling particular group of parts. The problem of obtaining such kind of grouping is called the manufacturing Cell Formation Problem (CFP). The goal of designing this cellular layout is to reduce production costs by maximizing loading of machines within cells and minimizing movement of parts from one cell to another. Effective partitions provide reduction in setup and transfer costs and savings in plant space.

In this thesis the CFP with variable number of production cells is considered.In the most general formulation the cell formation problem can be considered as the so-called biclustering problem. This kind of problems was first described by Hartigan [33, 34]. The term "biclustering" was introduced by Mirkin [44]. Later Mirkin also defined the notion of approximate biclusters (together with triclusters and p-clusters) and suggested two biclustering algorithms on binary data [45]. [17] considers the most widely used biclustering techniques and applications. [48] and [18] suggested models and methods for solving feature selection problem using consistent biclustering.

To the best of our knowledge there are no papers providing the proof of complexity (NP status) of the CFP problem. There are many publications, which mention that the problem NP-hard [43, 31, 19]. Some of them [56, 28] refer to the paper of Dimopoulos & Zalzala [26], but this paper does not include the proof of np-hardness.

Many papers including James et al. [35]; Chung et al. [24]; Paydar & Saidi-Mehrabad [51]; Solimanpur et al. [54]; Utkina et al. [57] refer to Ballakur & Steudel [4] when discussing the NP-hardness of the CFP. However Ballakur & Steudel [4] present a heuristic for the CFP with different objective functions and do not state anything about the NP status of these CFP formulations. Moreover, the most important objective function for the CFP, the grouping efficacy, was introduced later by Kumar & Chandrasekharan [41]. At the same time the grouping efficacy is currently widely accepted and considered as the best function successfully joining the both objectives of inter-cell part movement minimization and intra-cell machine loading maximization.

In the current research we provide rigorous proofs of NP-completeness for different

formulations of the CFP with the fractional grouping efficacy objective as well as the linear objective minimizing the total number of exceptions and voids.

Object of Research is the CFP in its formulation with given machines number, parts number and binary matrix describing production process. The number of production cells is not initially defined and can vary with respect to the objective function used.

Ph.D. Thesis Goal is the development of methods for solving the CFP effectively comparing to the existing state-of-art approaches and finding rigorous proofs of NP-completeness for different formulations of the CFP.

Novelties of Ph.D thesis are as follows:

• the proof of NP-completeness for the decision version of the CFP with the fractional grouping efficacy objective and linear E+V objective

• two original exact approaches for solving the CFP with fractional objective function

• an effective variable neighborhood search heuristic

The suggested algorithms have a wide range of practical applications. The first is designing effective cellular manufacturing layout which allows to improve productivity of batch-production systems. In addition, the formulation considered in this thesis can be also used for solving different biclustering problems (e.g. gene expression problems in biology) as well as clustering problems on bigraphs (e.g. bicluster graph editing problem).

Author's contribution includes the development and implementation of models and algorithms, proofs of theorems and propositions, algorithms testing, performing computational experiments and preparing research papers.

The author has the certificate of official registration of computer program with id №2014610434 - "Heuristic algorithm for solving the Cell Formation Problem".

Papers. Results of this work are published in 5 scientific papers in international peer-reviewed journals and conference proceedings.

First-tier publications:

1. Bychkov, I., Batsyn, M. (2018) An efficient exact model for the cell formation problem with a variable number of production cells. Computers & Operations Research, 91, 112-120, Q1 (Ilya Bychkov suggested and developed the exact approach, implemented it, performed computational experiments and prepared the article)

2. Bychkov, I., Batsyn, M., Pardalos, P. M. (2014). Exact model for the cell formation problem. Optimization Letters, 8(8), 2203-2210, Q2 (Ilya Bychkov developed the exact approach, implemented it, performed computational experiments, proved the propositions and prepared the article)

3. Batsyn, M., Batsyna E., Bychkov I. (2019) NP-completeness of cell formation problem with grouping efficacy objective, International Journal of Production Research (Q1), Published online: 26 Sep 2019,

https://doi.org/10.1080/00207543.2019.1668072 (Ilya Bychkov participated in discussing and proving of all theorems and propositions)

4. Bychkov, I., Batsyn, M., Sukhov, P., Pardalos, P.M (2013) Heuristic Algorithm for the Cell Formation Problem. In: Goldengorin et al (eds) Models, Algorithms,

and Technologies for Network Analysis. Springer Proceedings in Mathematics & Statistics 59, 43-69. (Ilya Bychkov suggested and developed the heuristic algorithm, implemented it, performed computational experiments and prepared the article)

Second-tier publications:

5. Bychkov I., Batsyn M., Pardalos P.M. (2017) Heuristic for Maximizing Grouping Efficiency in the Cell Formation Problem. In: Kalyagin et al (eds) Models, Algorithms, and Technologies for Network Analysis. Springer Proceedings in Mathematics & Statistics 197, 11-26. (Ilya Bychkov suggested and developed the heuristic algorithm, implemented it, performed computational experiments and prepared the article)

6. Batsyn, M., Bychkov I., Goldengorin B., Pardalos P., Sukhov P. (2013) Pattern-based heuristic for the cell formation problem in Group Technology. In: Gold-engorin et al (eds) Models, algorithms, and technologies for network analysis. Springer Proceedings in Mathematics & Statistics 32, 11-50 (Ilya Bychkov participated in discussion and implementation of the algorithm, performed computational experiments and prepared the article)

Reports at conferences and seminars:

• The 8th International Conference on Network Analysis (NET 2018), May 18-19, Yandex, Moscow, Russia. From Cell Formation Problem to Biclustering and Graph Editing.

• Research Seminar of the Graduate School of Computer Science, CS HSE, September 29,2017, Computer Science Faculty, Higher School of Economics, Moscow, Russia. An effective exact model for solving the cell formation problem.

• LATNA research seminar, 2016, Nizhny Novgorod, Russia. On solving manufacturing cell formation via bicluster editing.

• The 20th Conference of the International Federation of Operational Research Societies IFORS-2014, July 13-18, 2014, Barcelona, Spain. Multi-start local search heuristic for the cell formation problem.

• Third International Conference on Network Analysis, 2013, Nizhny Novgorod, Russia. An exact model for the cell formation problem.

• Second International Conference on Network Analysis, 2012, Nizhny Novgorod, Russia. "Patterns" for solving the Cell Formation Problem.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Бычков Илья Сергеевич

5 Summary and Future Research Directions

In this chapter we present a new pattern based approach within the classic linear assignment model.The main idea of this approach might be illustrated by means of different classes of COPs which include the maximum weight independent set and its unweighted version, linear ordering, and cell formation problems, just to mention

Table 34 Summary of the comparison with Goncalves and Resende [17]

Number of problems solved

Better Equal Total

No singletons # of cells Singletons # of cells No singletons # of cells Singletons # of cells No singletons Singletons

More Equal Total More Equal Total More Equal Total More Equal Total 35 26

8 5 13 23 3 26 0 22 22 0 0 0

a few. We have successfully applied this approach to design a new heuristic which outperforms all well-known heuristics for the CFP with the grouping efficacy as its objective function. The main distinctions of our PBH are as follows:

1. The PBH is based on a rigorous (even if it is informal) formulation of the CFP as the problem of finding three objects, namely, (a) an optimal pattern, (b) an optimal part permutation, and (c) an optimal machine permutation.

2. Our rigorous formulation might be solved efficiently for any fixed pattern and permutation (either parts or machines) by means of the Jonker-Volgenant's Hungarian algorithm [20] efficient implementation.

3. Based on our formulation of the CFP we have designed an efficient PBH which outperforms all currently known heuristics for the CFP with the grouping efficacy criterion of optimality.

4. We believe that the success of our PBH is due to a wide range of patterns sequentially enumerated under control of the optimality criterion.

5. Since to solve a CFP instance, say 40x100, with a specific pattern by our PBH requires just several milliseconds, we are able to involve much more adjusted patterns than we have done in this study and hence to generate a wider range of high quality CFP solutions.

Our main research direction will be concentrated on the exact mathematical programming formulation of the CFP with the purpose to find out the thresholds for the number of machines and parts which might be treated to optimality within the mathematical programming including fractional programming approach. Another direction of our research will be in finding polynomially solvable special cases of the CFP based either on structural properties of the Boolean input machine-part matrix or the CFP criteria of optimality. Finally we are looking for applications of the pattern based approach to other classes of COPs.

Acknowledgments The authors would like to thank professor Mauricio Resende for the 35 GT instances provided on his web page (http://www2.research.att.com/~mgcr/data/cell-formation/). We are also grateful to professors R. Jonker and A. Volgenant for making available for us their very efficient program implementation of the Hungarian algorithm.

The authors are supported by The LATNA Laboratory, National Research University Higher School of Economics (NRU HSE), and Russian Federation government grant, ag. 11.G34.31.0057. Boris Goldengorin and Mikhail Batsyn are partially supported by NRU HSE Scientific Fund grant "Teachers-Students" #11-04-0008 "Calculus for tolerances in combinatorial optimization: theory and algorithms."

Список литературы диссертационного исследования кандидат наук Бычков Илья Сергеевич, 2020 год

References

1. Askin, R.G., Chiu, K.S.: A graph partitioning procedure for machine assignment and cell formation in group technology. Int. J. Prod. Res. 28(8), 1555-1572 (1990)

2. Askin, R.G., Subramanian, S.: A cost-based heuristic for group technology configuration. Int. J. Prod. Res. 25, 101-113 (1987)

3. Ballakur, A., Steudel, H.J.: A within cell utilization based heuristic for designing cellular manufacturing systems. Int. J. Prod. Res. 25, 639-655 (1987)

4. Boctor, F.: A linear formulation of the machine-part cell formation problem. Int. J. Prod. Res. 29(2), 343-356 (1991)

5. Boe, W., Cheng, C.H.: A close neighbor algorithm for designing cellular manufacturing systems. Int. J. Prod. Res. 29(10), 2097-2116 (1991)

6. Burbidge, J.L.: The new approach to production. Prod. Eng. 40, 3-19 (1961)

7. Burbidge, J.L.: The Introduction of Group Technology. Wiley, New York (1975)

8. Carrie, S.: Numerical taxonomy applied to group technology and plant layout. Int. J. Prod. Res. 11, 399-416 (1973)

9. Chan, H.M., Milner, D.A.: Direct clustering algorithm for group formation in cellular manufacture. J. Manuf. Syst. 1(1), 64-76 (1982)

10. Chandrasekaran, M.P., Rajagopalan, R.: An ideal seed non-hierarchical clustering algorithm for cellular manufacturing. Int. J. Prod. Res. 24, 451-464 (1986)

11. Chandrasekaran, M.P., Rajagopalan, R.: MODROC: An extension of rank order clustering of group technology. Int. J. Prod. Res. 24(5), 1221-1233 (1986)

12. Chandrasekharan, M.P., Rajagopalan, R.: ZODIAC—An algorithm for concurrent formation of part families and machine cells. Int. J. Prod. Res. 25(6), 835-850 (1987)

13. Chandrasekharan, M.P., Rajagopalan, R.: Groupability: Analysis of the properties of binary data matrices for group technology. Int. J. Prod. Res. 27(6), 1,035-1,052 (1989)

14. Cheng, C.H., Gupta, Y.P., Lee, W.H., Wong, K.F.: A TSP-based heuristic for forming machine groups and part families. Int. J. Prod. Res. 36(5), 1325-1337 (1998)

15. Dimopoulos, C., Mort, N.: A hierarchical clustering methodology based on genetic programming for the solution of simple cell-formation problems. Int. J. Prod. Res. 39(1), 1-19 (2001)

16. Goldengorin, B., Krushinsky, D., Slomp, J.: Flexible PMP approach for large size cell formation, Oper. Res. 60(5), 1157-1166 (2012)

17. Goncalves, J.F., Resende, M.G.C.: An evolutionary algorithm for manufacturing cell formation. Comput. Ind. Eng. 47, 247-273 (2004)

18. Hsu, C.P.: Similarity coefficient approaches to machine-component cell formation in cellular manufacturing: A comparative study. PhD Thesis, Department of Industrial and Manufacturing Engineering, University of Wisconsin Milwaukee (1990)

19. Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38(4), 325-340 (1987)

20. King, J.R.: Machine-component grouping in production flow analysis: An approach using a rank order clustering algorithm. Int. J. Prod. Res. 18(2), 213-232 (1980)

21. King, J.R., Nakornchai, V.: Machine-component group formation in group technology: Review and extension. Int. J. Prod. Res. 20(2), 117-133 (1982)

22. Krushinsky, D., Goldengorin, B.: An exact model for cell formation in group technology. Comp. Manag. Sci. (2012). DOI 10.1007/s10287-012-0146-2, available at http://www. springerlink.com/content/ug2l55m46t554564/fulltext.pdf within open access at Springer-link.com

23. Kumar, K.R., Chandrasekharan, M.P.: Grouping efficacy: A quantitative criterion for goodness of block diagonal forms of binary matrices in group technology. Int. J. Prod. Res. 28(2), 233-243 (1990)

24. Kumar K.R., Kusiak A., Vannelli A.: Grouping of parts and components in flexible manufacturing systems. Eur. J. Oper. Res. 24, 387-97 (1986)

25. Kumar, K.R., Vannelli, A.: Strategic subcontracting for efficient disaggregated manufacturing. Int. J. Prod. Res. 25(12), 1715-1728 (1987)

26. Kusiak, A.: The generalized group technology concept. Int. J. Prod. Res. 25(4), 561-569 (1987)

27. Kusiak, A., Chow, W.: Efficient solving of the group technology problem. J. Manuf. Syst. 6(2), 117-124(1987)

28. Kusiak, A., Cho, M.: Similarity coefficient algorithm for solving the group technology problem. Int. J. Prod. Res. 30, 2633-2646 (1992)

29. Lei, D., Wu, Z.: Tabu search for multiple-criteria manufacturing cell design. Int. J. Adv. Manuf. Tech. 28, 950-956 (2006)

30. Liang, M., Zolfaghari, S.: Machine cell formation considering processing times and machine capacities: an ortho-synapse Hopfield neural network approach. J. Intell. Manuf. 10, 437-447 (1999)

31. McAuley, J.: Machine grouping for efficient production. Prod. Engineer. 51(2), 53-57 (1972)

32. McCormick, W.T., Schweitzer, P.J., White, T.W.: Problem decomposition and data reorganization by a clustering technique. Oper. Res. 20(5), 993-1009 (1972)

33. Mitrofanov, S.P.: Nauchnye Osnovy Gruppovoy Tekhnologii, p. 435. Lenizdat, Leningrad, Russia (1959) (in Russian)

34. Mitrofanov, S.P.: The Scientific Principles of Group Technology. Boston Spa, Yorkshire: National Lending Library Translation (1966) Translation of Mitrofanov (1959)

35. Mosier, C.T.: An experiment investigating the application of clustering procedures and similarity coefficients to the GT machine cell formation problem. Int. J. Prod. Res. 27(10), 1811-1835 (1989)

36. Mosier, C.T., Taube, L.: The facets of group technology and their impact on implementation. OMEGA 13(6), 381-391 (1985)

37. Mosier, C.T., Taube, L.: Weighted similarity measure heuristics for the group technology machine clustering problem. OMEGA 13(6), 577-583 (1985)

38. Ng, S.: Worst-case analysis of an algorithm for cellular manufacturing. Eur. J. Oper. Res. 69(3), 384-398 (1993)

39. Ng, S.: On the characterization and measure of machine cells in group technology. Oper. Res. 44(5), 735-744 (1996)

40. Onwubolu, G.C., Mutingi, M.: A genetic algorithm approach to cellular manufacturing systems. Comput. Ind. Eng. 39(1-2), 125-144 (2001)

41. Rajagopalan, R., Batra, J.L.: Design of cellular production systems: a graph-theoretic approach. Int. J. Prod. Res. 13(6), 567-579 (1975)

42. Seifoddini, H.: Single linkage versus average linkage clustering in machine cells formation applications. Comput. Ind. Eng. 16(3), 419-426 (1989)

43. Seifoddini, H., Wolfe, P.M.: Application of the similarity coefficient method in group technology. IIE Trans. 18(3), 271-277 (1986)

44. Shtub, A.: Modelling group technology cell formation as a generalized assignment problem. Int. J. Prod. Res. 27(5), 775-782 (1989)

45. Srinivasan, G.: A clustering algorithm for machine cell formation in group technology using minimum spanning trees. Int. J. Prod. Res. 32, 2149-2158 (1994)

46. Srinivasan, G., Narendran, T.T.: GRAFICS-A nonhierarchical clustering-algorithm for group technology. Int. J. Prod. Res. 29(3), 463-478 (1991)

47. Srinivasan G, Narendran TT, Mahadevan B. An assignment model for the part-families problem in group technology. Int. J. Prod. Res. 28(1), 145-152 (1990)

48. Stanfel, L.: Machine clustering for economic production. Eng. Cost. Prod. Econ. 9, 73-81 (1985)

49. Waghodekar, P.H., Sahu, S.: Machine-component cell formation in group technology MACE. Int. J. Prod. Res. 22, 937-948 (1984)

50. Won, Y., Lee, K.C.: Modified p-median approach for efficient GT cell formation. Comput. Ind. Eng. 46, 495-510 (2004)

51. Wu, X., Chao-Hsien, C., Wang, Y., Yan, W.: A genetic algorithm for cellular manufacturing design and layout. Eur. J. Oper. Res. 181, 156-167 (2007)

52. Xambre, A.R., Vilarinho, P.M.: A simulated annealing approach for manufacturing cell formation with multiple identical machines. Eur. J. Oper. Res. 151, 434-446 (2003)

53. Yang, M.-S., Yang, J.-H.: Machine-part cell formation in group technology using a modified ART1 method. Eur. J. Oper.Res. 188(1), 140-152 (2008)