Academy of Mathematics and Systems Science, CAS Colloquia & Seminars
Speaker:
Prof. Guohui Lin,University of Alberta
Inviter:
Guiying Yan
Title:
A PTAS for the Multiple Parallel Identical Multi-stage Flowshops to Minimize the Makespan
Time & Venue:
2015.7.8 10:00-11:00am N613
Abstract:
In the parallel k-stage flowshops problem, we are given m identical k-stage flowshops and a set of jobs. Each job can be processed by any one of the flowshops but switching between flowshops 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 and the classical flowshop scheduling problems, and thus it is NP-hard. We present a polynomial-time approximation scheme for the problem, when m and k are fixed constants.
Appendix：
Copyright@2008, All Rights Reserved, Academy of Mathematics and Systems Science, CAS
Tel: 86-10-82541777 Fax: 86-10-82541972 E-mail: contact@amss.ac.cn
