An Online Algorithm for Parallel Scheduling of Serus With Resource Conflicts

被引：0
|
作者：
Jiang Y.-Z. [1 ]
Li D.-N. [1 ]
Jin H.-B. [1 ]
Yin Y. [2 ]
机构：
[1] Beijing Laboratory of Intelligent Information Technology, School of Computer Science, Beijing Institute of Technology, Beijing
[2] Graduate School of Business, Doshisha University, Kyoto
来源：
Zidonghua Xuebao/Acta Automatica Sinica | 2022年 / 48卷 / 02期
基金：
中国国家自然科学基金;
关键词：
Competitive ratio; Instance reduction; Online scheduling; Seru production system; Total weighted completion time;
D O I：
10.16383/j.aas.c190698
中图分类号：
学科分类号：
摘要：
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. Copyright ©2019 Acta Automatica Sinica. All rights reserved.
引用
收藏
页码：444 / 459
页数：15
相关论文
共 31 条
  • [1] Yin Y, Stecke K E, Li D N., The evolution of production systems from Industry 2.0 through Industry 4.0, International Journal of Production Research, 56, 1-2, pp. 848-861, (2018)
  • [2] Yu Y, Sun W, Tang J F, Wang J W., Line-hybrid seru system conversion: models, complexities, properties, solutions and insights, Computers & Industrial Engineering, 103, pp. 282-299, (2016)
  • [3] Roth A, Singhal J, Singhal K, Tang C S., Knowledge creation and dissemination in operations and supply chain management, Production and Operations Management, 25, 9, pp. 1473-1488, (2016)
  • [4] Yin Y, Kaku I, Stecke K E., The evolution of seru production systems throughout Canon, Operations Management Education Review, 2, pp. 27-40, (2008)
  • [5] Liu C G, Lian J, Yin Y, Li W J., Seru Seisa-an innovation of the production management mode in Japan, Asian Journal of Technology Innovation, 18, 2, pp. 89-113, (2010)
  • [6] Liu C G, Dang F, Li W J, Evans S, Yin Y., Production planning of multi-stage multi-option seru production systems with sustainable measures, Journal of Cleaner Production, 105, pp. 285-299, (2015)
  • [7] Wu Xu-Hui, Du Shao-Feng, Hao Hui-Hui, Yu Yang, Yin Yong, Li Dong-Ni, A line-seru conversion approach by means of cooperative coevolution, Acta Automatic Sinica, 44, 6, pp. 1015-1027, (2018)
  • [8] Yin Y, Stecke K E, Swink M, Kaku I., Lessons from seru production on manufacturing competitively in a high cost environment, Journal of Operations Management, 49-51, pp. 67-76, (2017)
  • [9] Stecke K E, Yin Y, Kaku I., Seru production: An extension of just-in-time approach for volatile business environments, Analytical Approaches to Strategic Decsion-Making: Inter-disciplinary Considerations, IGI Global, pp. 45-58, (2014)
  • [10] Isa K, Tsuru T., Cell production and workplace innovation in Japan: toward a new model for Japanese manufacturing, Industrial Relations: A Journal of Economy and Society, 41, 4, pp. 548-578, (2002)
1234