• Complex
  • Title
  • Author
  • Keyword
  • Abstract
  • Scholars
Search

Author:

Dong, Jianming (Dong, Jianming.) | Tong, Weitian (Tong, Weitian.) | Luo, Taibo (Luo, Taibo.) | Wang, Xueshi (Wang, Xueshi.) | Hu, Jueliang (Hu, Jueliang.) | Xu, Yinfeng (Xu, Yinfeng.) | Lin, Guohui (Lin, Guohui.)

Indexed by:

SCIE

Abstract:

We consider the NP-hard m-parallel two-stage flowshop problem, abbreviated as the (m, 2)-PFS problem, where we need to schedule n jobs to m parallel identical two-stage fiowshops in order to minimize the makespan, i.e. the maximum completion time of all the jobs on the m fiowshops. The (m, 2)-PFS problem can be decomposed into two subproblems: to assign the n jobs to the m parallel flowshops, and for each flowshop to schedule the jobs assigned to the flowshop. We first present a pseudo-polynomial time dynamic programming algorithm to solve the (m, 2)-PFS problem optimally, for any fixed m, based on an earlier idea for solving the (2, 2)-PFS problem. Using the dynamic programming algorithm as a subroutine, we design a fully polynomial-time approximation scheme (FPTAS) for the (m, 2)-PFS problem. (C) 2016 Elsevier B.V. All rights reserved.

Keyword:

Dynamic programming Fully polynomial-time approximation scheme Makespan Multiprocessor scheduling Two-stage flowshop scheduling

Author Community:

  • [ 1 ] [Dong, Jianming; Wang, Xueshi; Hu, Jueliang; Lin, Guohui] Zhejiang Sci Tech Univ, Dept Math, Hangzhou 310018, Zhejiang, Peoples R China
  • [ 2 ] [Tong, Weitian; Luo, Taibo; Lin, Guohui] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada
  • [ 3 ] [Tong, Weitian] Georgia Southern Univ, Dept Comp Sci, Statesboro, GA 30458 USA
  • [ 4 ] [Luo, Taibo; Xu, Yinfeng] Sichuan Univ, Sch Business, Chengdu 610065, Sichuan, Peoples R China
  • [ 5 ] [Xu, Yinfeng] State Key Lab Mfg Syst Engn, Xian 710049, Shaanxi, Peoples R China

Reprint Author's Address:

  • Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada.

Show more details

Related Keywords:

Related Article:

Source :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

Year: 2017

Volume: 657

Page: 64-72

0 . 7 7 2

JCR@2017

0 . 8 2 7

JCR@2020

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:135

JCR Journal Grade:3

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count: 17

SCOPUS Cited Count: 22

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 4

FAQ| About| Online/Total:443/168406308
Address:XI'AN JIAOTONG UNIVERSITY LIBRARY(No.28, Xianning West Road, Xi'an, Shaanxi Post Code:710049) Contact Us:029-82667865
Copyright:XI'AN JIAOTONG UNIVERSITY LIBRARY Technical Support:Beijing Aegean Software Co., Ltd.