A “Greedy“ Czech Manufacturing Case

Authors: George Cristian Gruia, Michal Kavan

Abstract:

The article describes a case study on one of Czech Republic-s manufacturing middle size enterprises (ME), where due to the European financial crisis, production lines had to be redesigned and optimized in order to minimize the total costs of the production of goods. It is considered an optimization problem of minimizing the total cost of the work load, according to the costs of the possible locations of the workplaces, with an application of the Greedy algorithm and a partial analogy to a Set Packing Problem. The displacement of working tables in a company should be as a one-toone monotone increasing function in order for the total costs of production of the goods to be at minimum. We use a heuristic approach with greedy algorithm for solving this linear optimization problem, regardless the possible greediness which may appear and we apply it in a Czech ME.

Keywords: Czech, greedy algorithm, minimize, total costs.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059827

References:

[1] Guldemond T.A., Hurink J.L., Paulus J.J. ,SchuttenJ.M.J.,"Timeconstrained project scheduling" InJournal of Scheduling 2008; 11(2):137-48.
[2] Hurink J.L., Kok A.L., Paulus J.J., SchuttenJ.M.J.,"Time-constrained project scheduling with adjacent resources" InJournal of Computers & Operations Research 2011; 38:310-319.
[3] IBM ILOG CPLEX Optimization Studio v.12.5
[4] Wikipedia, the free encyclopedia http://en.wikipedia.org/wiki/Hasse_diagram
[5] Birkhoff, Garrett,Lattice Theory (Revised ed.), American Mathematical Society, 1948.
[6] Vogt, Henri Gustav,Le├ºonssur la résolutionalgébrique des équations, Nony, p. 91, 1895.
[7] Di Battista, G., Tamassia, R.,"Algorithms for plane representation of acyclic digraphs" InJournal of Theoretical Computer Science 1988; 61(2-3):175-178, doi:10.1016/0304-3975(88)90123-5.
[8] Birkhoff, Garrett,Lattice Theory, American Mathematical Colloquium Publications 1967:25, 3rd ed., Providence, R. I.
[9] Fujishige, S., Tomizawa, N.,"A note on sub-modular functions on distributive lattices" InJournal of the Operations Research Society of Japan 1983; 26:309-318.
[10] Karp, R. M.,"Reducibility Among Combinatorial Problems" In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations, New York: Plenum,1972: 85-103.
[11] Bianchi S., Nasini G., TolomeiP.,"The set covering problem on circulant matrices: polynomial instances and the relation with the dominating set problem on webs"Electronic Notes in Discrete Mathematics 2010; 36:1185-1192.
[12] Zahra Naji-Azimi, Paolo Toth, Laura Galli,"An electromagnetism metaheuristic for the unicost set covering problem" InEuropean Journal of Operational Research 2010; 205:290-300.
[13] Peter J. Zwaneveld, Leo G. Kroon, Stan P.M. van Hoesel,"Routing trains through a railway station based on a node packing model"InEuropean Journal of Operational Research 2001; 128:14-33.
[14] Yuma Tanaka, Shinji Imahori, Mihiro Sasaki, MutsunoriYagiura,"An LP-based heuristic algorithm for the node capacitated in-tree packing problem" InJournal of Computers& Operations Research 2012; 39:637- 646.
[15] M.W. Padberg,"On the facial structure of set packing polyhedral" InMathematical Programming 1973; 5:199-215.