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 the Finite Optimal Convergence of Logic-Based Benders’ Decomposition in Solving 0–1 Min-Max Regret Optimization Problems with Interval Costs Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores

Authors : Kateřina Böhmová, Enrico Kravina, Matúš Mihalák

Published in: Combinatorial Optimization

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We consider a scheduling problem with machine dependent intervals, where each job consists of m fixed intervals, one on each of the m machines. To schedule a job, exactly one of the m intervals needs to be selected, making the corresponding machine busy for the time period equal to the selected interval. The objective is to schedule a maximum number of jobs such that no two selected intervals from the same machine overlap. This problem is NP-hard and admits a deterministic 1 / 2-approximation. The problem remains NP-hard even if all intervals have unit length, and all m intervals of any job have a common intersection. We study this special case and show that it is APX-hard, and design a 501 / 1000-approximation algorithm.

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 Toward Computer-Assisted Discovery and Automated Proofs of Cutting Plane Theorems
next chapter Balanced Partition of a Graph for Football Team Realignment in Ecuador
Literature
1.
2.
Böhmová, K., Disser, Y., Mihalák, M., Widmayer, P.: Interval selection with machine-dependent intervals. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 170–181. Springer, Heidelberg (2013)CrossRef
3.
Böhmová, K., Kravina, E., Mihalák, M.: Maximization problems competing over a common ground set and their black-box approximation (unpublished manuscript)
4.
5.
Chuzhoy, J., Ostrovsky, R., Rabani, Y.: Approximation algorithms for the job interval selection problem and related scheduling problems. In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 348–356 (2001)
6.
7.
Kolen, A.W.J., Lenstra, J.K., Papadimitriou, C.H., Spieksma, F.C.R.: Interval scheduling: a survey. Naval Res. Logistics (NRL) 54(5), 530–543 (2007)MathSciNetCrossRefMATH
8.
Kovalyov, M.Y., Ng, C., Cheng, T.E.: Fixed interval scheduling: models, applications, computational complexity and algorithms. Eur. J. Oper. Res. 178(2), 331–342 (2007)MathSciNetCrossRefMATH
9.
Nakajima, K., Hakimi, S.L.: Complexity results for scheduling tasks with discrete starting times. J. Algorithms 3(4), 344–361 (1982)MathSciNetCrossRefMATH
10.
11.
Sung, S.C., Vlach, M.: Maximizing weighted number of just-in-time jobs on unrelated parallel machines. J. Sched. 8, 453–460 (2005)MathSciNetCrossRefMATH
Metadata
Title
Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores
Authors
Kateřina Böhmová
Enrico Kravina
Matúš Mihalák
Copyright Year
2016
Book
Combinatorial Optimization

Print ISBN: 978-3-319-45586-0

Electronic ISBN: 978-3-319-45587-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-45587-7_30

Premium Partner

    Image Credits