Skip to main content

2016 | OriginalPaper | Buchkapitel

A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan

verfasst von : Weitian Tong, Eiji Miyano, Randy Goebel, Guohui Lin

Erschienen in: Frontiers in Algorithmics

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In the parallel k-stage flow-shops problem, we are given m identical k-stage flow-shops and a set of jobs. Each job can be processed by any one of the flow-shops but switching between flow-shops is not allowed. The objective is to minimize the makespan, which is the finishing time of the last job. This problem generalizes the classical parallel identical machine scheduling (where \(k = 1\)) and the classical flow-shop scheduling (where \(m = 1\)) problems, and thus it is \(\text {NP}\)-hard. We present a polynomial-time approximation scheme for the problem, when m and k are fixed constants. The key technique is to enumerate over schedules for big jobs, solve a linear programming for small jobs, and add the fractional small jobs at the end. Such a technique has been used in the design of similar approximation schemes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat Chen, B.: Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. J. Oper. Res. Soc. 46, 234–244 (1995)CrossRefMATH Chen, B.: Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. J. Oper. Res. Soc. 46, 234–244 (1995)CrossRefMATH
2.
Zurück zum Zitat Chen, B., Glass, C.A., Potts, C.N., Strusevich, V.A.: A new heuristic for three-machine flow shop scheduling. Oper. Res. 44, 891–898 (1996)CrossRefMATH Chen, B., Glass, C.A., Potts, C.N., Strusevich, V.A.: A new heuristic for three-machine flow shop scheduling. Oper. Res. 44, 891–898 (1996)CrossRefMATH
3.
Zurück zum Zitat Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Addison-Wesley, Reading (1967)MATH Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Addison-Wesley, Reading (1967)MATH
4.
Zurück zum Zitat Dong, J., Tong, W., Luo, T., Wang, X., Hu, J., Xu, Y., Lin, G.: An FPTAS for the parallel two-machine flowshop problem. Theor. Comput. Sci. (2016, in press) Dong, J., Tong, W., Luo, T., Wang, X., Hu, J., Xu, Y., Lin, G.: An FPTAS for the parallel two-machine flowshop problem. Theor. Comput. Sci. (2016, in press)
5.
Zurück zum Zitat Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)MATH Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)MATH
6.
Zurück zum Zitat Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1, 117–129 (1976)MathSciNetCrossRefMATH Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1, 117–129 (1976)MathSciNetCrossRefMATH
7.
8.
Zurück zum Zitat Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966)CrossRefMATH Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966)CrossRefMATH
9.
Zurück zum Zitat Gupta, J.N.D.: Two-stage, hybrid flowshop scheduling problem. J. Oper. Res. Soc. 39, 359–364 (1988)CrossRefMATH Gupta, J.N.D.: Two-stage, hybrid flowshop scheduling problem. J. Oper. Res. Soc. 39, 359–364 (1988)CrossRefMATH
10.
Zurück zum Zitat Gupta, J.N.D., Hariri, A.M.A., Potts, C.N.: Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Ann. Oper. Res. 69, 171–191 (1997)CrossRefMATH Gupta, J.N.D., Hariri, A.M.A., Potts, C.N.: Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Ann. Oper. Res. 69, 171–191 (1997)CrossRefMATH
11.
Zurück zum Zitat Gupta, J.N.D., Tunc, E.A.: Schedules for a two-stage hybrid flowshop with parallel machines at the second stage. Int. J. Prod. Res. 29, 1489–1502 (1991)CrossRef Gupta, J.N.D., Tunc, E.A.: Schedules for a two-stage hybrid flowshop with parallel machines at the second stage. Int. J. Prod. Res. 29, 1489–1502 (1991)CrossRef
12.
13.
Zurück zum Zitat He, D.W., Kusiak, A., Artiba, A.: A scheduling problem in glass manufacturing. IIE Trans. 28, 129–139 (1996)CrossRef He, D.W., Kusiak, A., Artiba, A.: A scheduling problem in glass manufacturing. IIE Trans. 28, 129–139 (1996)CrossRef
14.
Zurück zum Zitat Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34, 144–162 (1987)MathSciNetCrossRef Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34, 144–162 (1987)MathSciNetCrossRef
15.
Zurück zum Zitat Hoogeveen, J.A., Lenstra, J.K., Veltman, B.: Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. Eur. J. Oper. Res. 89, 172–175 (1996)CrossRefMATH Hoogeveen, J.A., Lenstra, J.K., Veltman, B.: Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. Eur. J. Oper. Res. 89, 172–175 (1996)CrossRefMATH
16.
Zurück zum Zitat Jansen, K., Sviridenko, M.I.: Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, p. 455. Springer, Heidelberg (2000)CrossRef Jansen, K., Sviridenko, M.I.: Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, p. 455. Springer, Heidelberg (2000)CrossRef
17.
Zurück zum Zitat Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Res. Logistics Q. 1, 61–68 (1954)CrossRef Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Res. Logistics Q. 1, 61–68 (1954)CrossRef
20.
22.
Zurück zum Zitat Schuurman, P., Woeginger, G.J.: A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem. Theor. Comput. Sci. 237, 105–122 (2000)MathSciNetCrossRefMATH Schuurman, P., Woeginger, G.J.: A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem. Theor. Comput. Sci. 237, 105–122 (2000)MathSciNetCrossRefMATH
23.
Zurück zum Zitat Vairaktarakis, G., Elhafsi, M.: The use of flowlines to simplify routing complexity in two-stage flowshops. IIE Trans. 32, 687–699 (2000) Vairaktarakis, G., Elhafsi, M.: The use of flowlines to simplify routing complexity in two-stage flowshops. IIE Trans. 32, 687–699 (2000)
24.
Zurück zum Zitat Wang, H.: Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions. Expert Syst. 22, 78–85 (2005)CrossRef Wang, H.: Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions. Expert Syst. 22, 78–85 (2005)CrossRef
25.
Zurück zum Zitat Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, C.A.J., Lenstra, J.K., Sevastj́anov, S.V.: Short shop schedules. Oper. Res. 45, 288–294 (1997)MathSciNetCrossRefMATH Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, C.A.J., Lenstra, J.K., Sevastj́anov, S.V.: Short shop schedules. Oper. Res. 45, 288–294 (1997)MathSciNetCrossRefMATH
26.
Zurück zum Zitat Zhang, X., van de Velde, S.: Approximation algorithms for the parallel flow shop problem. Eur. J. Oper. Res. 216, 544–552 (2012)MathSciNetCrossRefMATH Zhang, X., van de Velde, S.: Approximation algorithms for the parallel flow shop problem. Eur. J. Oper. Res. 216, 544–552 (2012)MathSciNetCrossRefMATH
Metadaten
Titel
A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
verfasst von
Weitian Tong
Eiji Miyano
Randy Goebel
Guohui Lin
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-39817-4_22