2018/01/27 by Guangwei Wu, Wu, Guangwei, Jianer Chen +3
Computer Science · Engineering · #Cloud Computing and Resource Management #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1801.09089
arxiv created 2018/01/27 · openalex publication_date 2018/01/27 · arxiv updated 2018/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by the current research in data centers and cloud computing, we study the problem of scheduling a set of two-stage jobs on multiple two-stage flowshops. A new formulation for configurations of such scheduling is proposed, which leads directly to improvements to the complexity of scheduling algorithms for the problem. Motivated by the observation that the costs of the two stages can be significantly different, we present deeper study on the structures of the problem that leads to a new approach to designing scheduling algorithms for the problem. With more thorough analysis, we show that the new approach gives very significant improved scheduling algorithms for the problem when the costs of the two stages are different significantly. Improved approximation algorithms for the problem are also presented.