摘要
With the remarkably increase of mass customization, there comes the seru production system (SPS), which has become a hotspot in both the research and the application fields. This paper discusses the online parallel scheduling problem of serus with resource conflicts, which aims at scheduling serus that are generated with dynamic demands on limited space to minimize the total weighted completion time. First, we consider online parallel scheduling of serus without resource conflicts. Based on the average delayed shortest weighted processing time (AD-SWPT) algorithm, an adjustment parameter is introduced and an optimization algorithm with a constant competitive ratio is proposed. Then for online parallel scheduling of serus with resource conflicts, an α-average delayed shortest weighted processing time-improved (αAD-I) algorithm is proposed, whose competitive ratio is proved to be the same as the one without resource conflicts in special cases via instance reduction. Computational experiments are implemented to test and verify the superiority of our algorithm under both special instances and general instances.
投稿的翻译标题 | An Online Algorithm for Parallel Scheduling of Serus With Resource Conflicts |
---|---|
源语言 | 繁体中文 |
页(从-至) | 444-459 |
页数 | 16 |
期刊 | Zidonghua Xuebao/Acta Automatica Sinica |
卷 | 48 |
期 | 2 |
DOI | |
出版状态 | 已出版 - 2月 2022 |
关键词
- Competitive ratio
- Instance reduction
- Online scheduling
- Seru production system
- Total weighted completion time