Top

Published in:

2018 | OriginalPaper | Chapter

Complexity of Bi-objective Buffer Allocation Problem in Systems with Simple Structure

Authors : Alexandre B. Dolgui, Anton V. Eremeev, Mikhail Y. Kovalyov, Vyacheslav S. Sigaev

Published in: Optimization Problems and Their Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider a bi-objective optimization problem of choosing the buffers capacity in a production system of parallel tandem lines, each consisting of two machines with a single intermediate buffer. During operation of the system, the equipment stops occur due to failures and these stops are random in the moments when they arise and in their durations. The product is accumulated in an intermediate buffer if the downstream machine is less productive than the upstream machine.

We study the complexity of exact and approximate computations of a Pareto front for the following two bi-objective problem formulations: (i) the expected revenue maximization with minimization of buffers allocation cost and (ii) the expected revenue maximization with minimization of expected inventory costs. The expected revenue is assumed to be an increasing function of the expected throughput of the system.

On the one hand, fully polynomial-time approximation schemes for approximation of Pareto fronts of these problems are proposed and an exact pseudo-polynomial time algorithm is suggested for the first problem in the case of integer buffer capacity costs. On the other hand, we show that both of these problems are intractable even in the case of just one tandem two-machine line.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter An Optimization Model for Empty Tank Cars Movement at Railway Petroleum Logistics Market

next chapter Inventory Policies in Dual Sourcing Systems with Uncertain Yield

Abdul-Kader, W.: Capacity improvement of an unreliable production line - an analytical approach. Comput. Oper. Res. 33, 1695–1712 (2006)CrossRef

Altiparmak, A., Bugak, A., Dengiz, B.: Optimization of buffer sizes in assembly systems using intelligent techniques. In: Proceedings of the 2002 Winter Simulation Conference, pp. 1157–1162 (2002)

Ancelin, B., Semery, A.: Calcul de la productivité d’une ligne integrée de fabrication. RAIRO Autom. Productiq. Inform. Industrielle 21, 209–238 (1987)

Bökler, F.: The multiobjective shortest path problem is NP-hard, or is it? In: Trautmann, H., Rudolph, G., Klamroth, K., Schütze, O., Wiecek, M., Jin, Y., Grimme, C. (eds.) EMO 2017. LNCS, vol. 10173, pp. 77–87. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-54157-0_6CrossRef

Chehade, H., Yalaoui, F., Amodeo, L., De Guglielmo, P.: Optimisation multiobjectif pour le probléme de dimensionnement de buffers. J. Decis. Syst. 18, 257–287 (2009)CrossRef

Cheng, T.C.E., Janiak, A., Kovalyov, M.Y.: Bicriterion single machine scheduling with resource dependent processing times. SIAM J. Optim. 8(2), 617–630 (1998)MathSciNetCrossRef

Cheng, T.C.E., Kovalyov, M.Y.: An unconstrained optimization problem is NP-hard given an oracle representation of its objective function: a technical note. Comput. Oper. Res. 29, 2087–2091 (2002)MathSciNetCrossRef

Coillard, P., Proth, J.M.: Effet des stocks tampons dans une fabrication en ligne. Revue belge de Statistique, d’Informatique et de Recherche Operationnelle 24(2), 3–27 (1984)MATH

Cruz, F.R.B., Van Woensel, T., Smith, J.M.: Buffer and throughput trade-offs in M/G/1/K queuing networks: a bicriteria approach. Int. J. Prod. Econ. 125, 224–234 (2010)CrossRef

10.

Dallery, Y., Gershwin, S.B.: Manufacturing flow line systems: a review of models and analytical results. Queueing Syst. 12(1–2), 3–94 (1992)CrossRef

11.

Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. Proc. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)CrossRef

12.

Dolgui, A., Eremeev, A., Kolokolov, A., Sigaev, V.: A genetic algorithm for the allocation of buffer storage capacities in a production line with unreliable machines. J. Math. Model. Algorithms 1, 89–104 (2002)MathSciNetCrossRef

13.

Dolgui, A., Eremeev, A.V., Kovalyov, M.Y., Sigaev, V.S.: Complexity of buffer capacity allocation problems for production lines with unreliable machines. J. Math. Model. Algorithms Oper. Res. 12(2), 155–165 (2013)MathSciNetCrossRef

14.

Dolgui, A., Eremeev, A.V., Sigaev, V.S.: Analysis of a multicriterial buffer capacity optimization problem for a production line. Autom. Remote Control 78(7), 1276–1289 (2017)MathSciNetCrossRef

15.

Dolgui, A., Eremeev, A.V., Sigaev, V.S.: HBBA: hybrid algorithm for buffer allocation in tandem production lines. J. Intell. Manuf. 18(3), 411–420 (2007)CrossRef

16.

Dolgui, A.B., Svirin, Y.P.: Models of evaluation of probabilistic productivity of automated technological complexes. Vesti Akademii Navuk Belarusi: phisikatechnichnie navuki 1, 59–67 (1995)

17.

Dubois, D., Forestier, J.-P.: Productivité et en cours moyen d’un ensemble de deux machines séparées par une zone de stockage. RAIRO Automat 16(2), 105–132 (1982)MATH

18.

D’Souza, K., Khator, S.: System reconfiguration to avoid deadlocks in automated manufacturing systems. Comput. Industr. Eng. 32, 445–465 (1997)CrossRef

19.

Emelichev, V.A., Perepelitsa, V.A.: Multiobjective problems on the spanning trees of a graph. Soviet Math. Dokl 37(1), 114–117 (1999)MATH

20.

Hamada, M., Martz, H., Berg, E., Koehler, A.: Optimizing the product-based avaibility of a buffered industrial process. Reliab. Eng. Syst. Saf. 91, 1039–1048 (2006)CrossRef

21.

Hansen, P.: Bicriterion path problems. In: Fandel, G., Gal, T. (eds.) Multiple Criteria Decision Making Theory and Application. Lecture Notes in Economics and Mathematical Systems, vol. 177, pp. 109–127. Springer, New York (1979). https://doi.org/10.1007/978-3-642-48782-8_9CrossRef

22.

Kovalyov, M.Y.: A rounding technique to construct approximation algorithms for knapsack and partition type problems. Appl. Math. Comput. Sci. 6(4), 101–113 (1996)MathSciNetMATH

23.

Levin, A.A., Pasjko, N.I.: Calculating the output of transfer lines. Stanki i Instrument 8, 8–10 (1969). (in Russian)

24.

Li, J., Meerkov, S.M.: Production Systems Engineering. Springer, New York (2009). https://doi.org/10.1007/978-0-387-75579-3CrossRefMATH

25.

Serafini, P.: Some considerations about computational complexity for multiobjective combinatorial problems. In: Jahn, J., Krabs, W. (eds.) Recent Advances and Historical Development of Vector Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 294, pp. 222–231. Springer, Heidelberg (1986). https://doi.org/10.1007/978-3-642-46618-2_15CrossRef

26.

Patchong, A., Lemoine, T., Kern, G.: Improving car body production at PSA Peugeot Citroen. Interfaces 33(1), 36–49 (2003)CrossRef

27.

Perepelitsa, V.A.: Mnogokriterial’nye modeli i metody dlya zadach optimizatsii na grafakh. Lambert Academic Publishing, 330 (2013)

28.

Tempelmeier, H.: Practical considerations in the optimization of flow production systems. Int. J. Prod. Res. 41(1), 149–170 (2003)CrossRef

29.

Warburton, A.: Approximation of pareto optima in multiple-objective shortestpath problems. Oper. Res. 35(1), 70–79 (1987)MathSciNetCrossRef

30.

Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, Comput. Engin. Commun. Networks Lab, Swiss Federal Institute Technology, Zurich (2001)

Title: Complexity of Bi-objective Buffer Allocation Problem in Systems with Simple Structure
Authors: Alexandre B. Dolgui
Anton V. Eremeev
Mikhail Y. Kovalyov
Vyacheslav S. Sigaev
Publisher: Springer International Publishing
Book: Optimization Problems and Their Applications
Print ISBN: 978-3-319-93799-1

Electronic ISBN: 978-3-319-93800-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-93800-4_22

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner