A “Greedy“ Czech Manufacturing Case

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.

Authors:

• George Cristian Gruia
• Michal Kavan

Keywords:

• Czech
• greedy algorithm
• minimize
• total costs.

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.