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

详细信息    查看全文

• 关键词：Multiprocessor scheduling ; Flow ; shop scheduling ; Makespan ; Linear program ; Polynomial ; time approximation scheme
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9711
• 期：1
• 页码：227-237
• 全文大小：321 KB
• 参考文献：1.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)CrossRef MATH
  2.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)CrossRef MATH
  3.Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Addison-Wesley, Reading (1967)MATH
  4.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.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.Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1, 117–129 (1976)MathSciNet CrossRef MATH
  7.Gonzalez, T., Sahni, S.: Flowshop and jobshop schedules: complexity and approximation. Oper. Res. 26, 36–52 (1978)MathSciNet CrossRef MATH
  8.Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966)CrossRef MATH
  9.Gupta, J.N.D.: Two-stage, hybrid flowshop scheduling problem. J. Oper. Res. Soc. 39, 359–364 (1988)CrossRef MATH
  10.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)CrossRef MATH
  11.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.Hall, L.A.: Approximability of flow shop scheduling. Math. Program. 82, 175–190 (1998)MathSciNet MATH
  13.He, D.W., Kusiak, A., Artiba, A.: A scheduling problem in glass manufacturing. IIE Trans. 28, 129–139 (1996)CrossRef
  14.Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34, 144–162 (1987)MathSciNet CrossRef
  15.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)CrossRef MATH
  16.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.Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Res. Logistics Q. 1, 61–68 (1954)CrossRef
  18.Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)MathSciNet CrossRef MATH
  19.Lee, C.-Y., Vairaktarakis, G.L.: Minimizing makespan in hybrid flowshops. Oper. Res. Lett. 16, 149–158 (1994)MathSciNet CrossRef MATH
  20.Ruiz, R., Vázquez-Rodríguez, J.A.: The hybrid flow shop scheduling problem. Eur. J. Oper. Res. 205, 1–18 (2010)MathSciNet CrossRef MATH
  21.Sahni, S.K.: Algorithms for scheduling independent tasks. J. ACM 23, 116–127 (1976)MathSciNet CrossRef MATH
  22.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)MathSciNet CrossRef MATH
  23.Vairaktarakis, G., Elhafsi, M.: The use of flowlines to simplify routing complexity in two-stage flowshops. IIE Trans. 32, 687–699 (2000)
  24.Wang, H.: Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions. Expert Syst. 22, 78–85 (2005)CrossRef
  25.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)MathSciNet CrossRef MATH
  26.Zhang, X., van de Velde, S.: Approximation algorithms for the parallel flow shop problem. Eur. J. Oper. Res. 216, 544–552 (2012)MathSciNet CrossRef MATH
  
• 作者单位：Weitian Tong (15) (17)
  Eiji Miyano (16)
  Randy Goebel (17)
  Guohui Lin (17)
  
  15. Department of Computer Sciences, Georgia Southern University, Georgia, Statesboro, 30460, USA
  17. Department of Computing Science, University of Alberta, Edmonton, Alberta, T6G 2E8, Canada
  16. Department of Systems Design and Informatics, Kyushu Institute of Technology, Iizuka, Fukuoka, 820-8502, Japan
  
• 丛书名：Frontiers in Algorithmics
• ISBN：978-3-319-39817-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9711

文摘

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.