主讲嘉宾：佐治亚南方大学童伟钿副教授
时 间：2024年6月21日14:00
地 点：信息楼510会议室
主 题：
A PTAS for parallel two-stage flowshops under makespan constraint
摘 要：
As a hybrid of the Parallel Two-stage Flowshop problem and the Multiple Knapsack problem, we investigate the scheduling of parallel two-stage flowshops under makespan constraint, which was motivated by applications in cloud computing. A set of two-stage jobs are selected and scheduled on parallel two-stage flowshops to achieve the maximum total profit while maintaining the given makespan constraint. Based on guessing strategies and rounding techniques for linear programs, we present a polynomial time approximation scheme (PTAS) for the case when the number of flowshops is a constant. As the case with two flowshops is already strongly NP-hard, our PTAS achieves the best possible approximation ratio.
主讲人简介：
Dr. Weitian Tong is a tenured associate professor in the Department of Computer Science at Georgia Southern University. Dr. Tong received the B.S. degree in Math and Applied Mathematics from Zhejiang University, Hangzhou, China, in 2010, and the Ph.D. degree in Computer Sciences from the University of Alberta, Edmonton, Canada, in 2015. Currently, Dr. Tong’s research focuses on the design of effective algorithms for optimization problems arising from data science and smart city. Dr. Tong has published over 60 peer-reviewed scholarly works on well-recognized international journals and/or conferences. In addition, Dr. Tong has edited and co-authored an Elsevier book on big spatiotemporal data processing with the state-of-the-art machine learning methods. Dr. Tong is also actively participating in various professional communities, including guest editor and editorial board member for well-known journals; chair, organizer, and/or TPC member for dozens of international conferences and workshops.