Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On Minimizing Supermodular Functions on Hereditary Systems Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Inapproximability Lower Bounds for Open Shop Problems with Exact Delays

Author : Alexander Ageev

Published in: Optimization Problems and Their Applications

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We study the two-machine Open Shop problem with exact delays. When all delays are equal to zero this problem converts to the no-wait two-machine Open Shop problem, which is known to be NP-hard. We prove that even the proportionate case of Open Shop problem with exact delays does not admit approximations with ratio \(1.5-\varepsilon \) unless P \(=\) NP. We also consider the very special case when the delays take at most two different values and prove that the existence of a \((1.25-\varepsilon )\)-approximation algorithm for it implies P \(=\) NP.

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 Branch and Bound Method for the Weber Problem with Rectangular Facilities on Lines in the Presence of Forbidden Gaps
next chapter Exact Solution of One Production Scheduling Problem
Literature
1.
Ageev, A.A., Baburin, A.E.: Approximation algorithms for UET scheduling problems with exact delays. Oper. Res. Lett. 35(4), 533–540 (2007)MathSciNetCrossRef
2.
3.
4.
5.
Blazewicz, J., Pawlak, G., Tanas, M., Wojciechowicz, W.: New algorithms for coupled tasks scheduling – a survey. RAIRO Oper. Res. Recherche Operationnelle 46(4), 335–353 (2012)MathSciNetCrossRef
6.
Condotta, A.: Scheduling with due dates and time lags: new theoretical results and applications. Ph.D. thesis, The University of Leeds, School of Computing, 156 pp. (2011)
7.
Condotta, A., Shakhlevich, N.V.: Scheduling coupled-operation jobs with exact time-lags. Discrete Appl. Math. 160(16–17), 2370–2388 (2012)MathSciNetCrossRef
8.
Farina, A., Neri, P.: Multitarget interleaved tracking for phased array radar. IEEE Proc. Part F Comm. Radar Signal Process. 127, 312–318 (1980)CrossRef
9.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)MATH
10.
Giaro, K.: NP-hardness of compact scheduling in simplified open and flow shops. Eur. J. Oper. Res. 130(1), 90–98 (2001)MathSciNetCrossRef
11.
Elshafei, M., Sherali, H.D., Smith, J.C.: Radar pulse interleaving for multi-target tracking. Naval Res. Logist. 51(1), 79–94 (2004)MathSciNetCrossRef
12.
Izquierdo-Fuente, A., Casar-Corredera, J.R.: Optimal radar pulse scheduling using neural networks. In: IEEE International Conference on Neural Networks, vol. 7, pp. 4588–4591 (1994)
13.
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)MathSciNetCrossRef
14.
Hwang, F.J., Lin, B.M.T.: Coupled-task scheduling on a single machine subject to a fixed-job-sequence. Comput. Ind. Eng. 60(4), 690–698 (2011)CrossRef
15.
Leung, J.Y.-T., Li, H., Zhao, H.: Scheduling two-machine flow shops with exact delays. Int. J. Found. Comput. Sci. 18(2), 341–359 (2007)MathSciNetCrossRef
16.
Orman, A.J., Potts, C.N.: On the complexity of coupled-task scheduling. Discrete Appl. Math. 72(1–2), 141–154 (1997)MathSciNetCrossRef
17.
Sherali, H.D., Smith, J.C.: Interleaving two-phased jobs on a single machine. Discrete Optim. 2(4), 348–361 (2005)MathSciNetCrossRef
18.
Yu, W.: The two-machine shop problem with delays and the one-machine total tardiness problem. Ph.D. thesis, Technische Universiteit Eindhoven, 136 pp. (1996)
19.
Yu, W., Hoogeveen, H., Lenstra, J.K.: Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. J. Sched. 7(5), 333–348 (2004)MathSciNetCrossRef
Metadata
Title
Inapproximability Lower Bounds for Open Shop Problems with Exact Delays
Author
Alexander Ageev
Copyright Year
2018
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_4

Premium Partner

    Image Credits