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 Complexity of Minimizing the Total Calibration Cost Read chapter Read first chapter

2017 | OriginalPaper | Chapter

On Approximation Algorithms for Two-Stage Scheduling Problems

Authors : Guangwei Wu, Jianer Chen, Jianxin Wang

Published in: Frontiers in Algorithmics

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We study scheduling on parallel two-stage flowshops in which each job has to pass through two operations: an R-operation and a T-operation. Motivated by the current research in data centers, we consider two restricted versions of the problem: one restricts that for each job, the R-operation consumes no less time than the T-operation, while the other assumes that the T-operation takes more time than the R-operation for each job. For the first case, we present an online 2-competitive algorithm and an offline 11/6-approximation algorithm. For the second case, we give an online 5/2-competitive algorithm, and prove, for the offline setting, that the problem can be reduced to the problem in the first case.

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 Geodetic Contraction Games on Trees
next chapter A New Lower Bound for Positive Zero Forcing
Literature
1.
Abts, D., Felderman, B.: A guided tour through data-center networking. Queue 10(5), 10–23 (2012)CrossRef
2.
3.
Barroso, L.A., Clidaras, J., Hölzle, U.: The datacenter as a computer: an introduction to the design of warehouse-scale machines. Synth. Lect. Comput. Archit. 8(3), 1–154 (2013)CrossRef
4.
Bartal, Y., Fiat, A., Karloff, H., Vohra, R.: New algorithms for an ancient scheduling problem. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 51–58. ACM (1992)
5.
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York (2005)MATH
6.
Dong, J., Tong, W., Luo, T., Wang, X., Hu, J., Xu, Y., Lin, G.: An FPTAS for the parallel two-stage flowshop problem. Theoret. Comput. Sci. 657, 64–72 (2017)MathSciNetCrossRefMATH
7.
Galambos, G., Woeginger, G.J.: An on-line scheduling heuristic with better worst-case ratio than Graham’s list scheduling. SIAM J. Comput. 22(2), 349–355 (1993)MathSciNetCrossRefMATH
8.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)MATH
9.
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563–1581 (1966)CrossRefMATH
10.
11.
Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5(1), 287–326 (1979)MathSciNetCrossRefMATH
12.
He, D.W., Kusiak, A., Artiba, A.: A scheduling problem in glass manufacturing. IIE Trans. 28(2), 129–139 (1996)CrossRef
13.
Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems. Springer Science, New York (2016)CrossRefMATH
14.
Tong, W., Miyano, E., Goebel, R., Lin, G.: A PTAS for the multiple parallel identical multi-stage flow-shops to minimize the makespan. In: Zhu, D., Bereg, S. (eds.) FAW 2016. LNCS, vol. 9711, pp. 227–237. Springer, Cham (2016). doi:10.​1007/​978-3-319-39817-4_​22
15.
Vairaktarakis, G., Elhafsi, M.: The use of flowlines to simplify routing complexity in two-stage flowshops. IIE Trans. 32(8), 687–699 (2000)
16.
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, New York (2011)CrossRefMATH
17.
Wu, G., Chen, J., Wang, J.: On scheduling two-stage jobs on multiple two-stage flowshops. Technical report, School of Information Science and Engineering Central South University (2016)
18.
Zhang, X., van de Velde, S.: Approximation algorithms for the parallel flow shop problem. Eur. J. Oper. Res. 216(3), 544–552 (2012)MathSciNetCrossRefMATH
Metadata
Title
On Approximation Algorithms for Two-Stage Scheduling Problems
Authors
Guangwei Wu
Jianer Chen
Jianxin Wang
Copyright Year
2017
Book
Frontiers in Algorithmics

Print ISBN: 978-3-319-59604-4

Electronic ISBN: 978-3-319-59605-1

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-59605-1_22

Premium Partner

    Image Credits