2.793

                    2018影響因子

                    (CJCR)

                    • 中文核心
                    • EI
                    • 中國科技核心
                    • Scopus
                    • CSCD
                    • 英國科學文摘

                    留言板

                    尊敬的讀者、作者、審稿人, 關于本刊的投稿、審稿、編輯和出版的任何問題, 您可以本頁添加留言。我們將盡快給您答復。謝謝您的支持!

                    姓名
                    郵箱
                    手機號碼
                    標題
                    留言內容
                    驗證碼

                    帶有資源沖突的Seru在線并行調度算法

                    江煜舟 李冬妮 靳洪博 殷勇

                    江煜舟, 李冬妮, 靳洪博, 殷勇. 帶有資源沖突的 Seru在線并行調度算法. 自動化學報, 2020, 46(x): 1?16 doi: 10.16383/j.aas.c190698
                    引用本文: 江煜舟, 李冬妮, 靳洪博, 殷勇. 帶有資源沖突的 Seru 在線并行調度算法. 自動化學報, 2020, 46(x): 1?16 doi: 10.16383/j.aas.c190698
                    Jiang Yu-Zhou, Li Dong-Ni, Jin Hong-Bo, Yin Yong. An online algorithm for parallel scheduling of serus with resource conflicts. Acta Automatica Sinica, 2020, 46(x): 1?16 doi: 10.16383/j.aas.c190698
                    Citation: Jiang Yu-Zhou, Li Dong-Ni, Jin Hong-Bo, Yin Yong. An online algorithm for parallel scheduling of serus with resource conflicts. Acta Automatica Sinica, 2020, 46(x): 1?16 doi: 10.16383/j.aas.c190698

                    帶有資源沖突的Seru在線并行調度算法

                    doi: 10.16383/j.aas.c190698
                    基金項目: 內蒙古自治區重大基礎研究開放課題(GZ2018KF001), 國家自然科學基金(61763046)資助
                    詳細信息
                      作者簡介:

                      江煜舟:北京理工大學計算機學院博士研究生. 主要研究方向為賽如生產智能優化. E-mail: jiang_yuzhou@163.com

                      李冬妮:北京理工大學計算機學院副教授. 主要研究方向為智能優化與仿真計算等. 本文通信作者. E-mail: ldn@bit.edu.cn

                      靳洪博:北京理工大學計算機學院博士研究生. 主要研究方向為賽如生產智能優化. E-mail: hb@bit.edu.cn

                      殷勇:同志社大學商學院教授. 主要研究方向為賽如生產與工業4.0. E-mail: yyin@mail.doshisha.ac.jp

                    An Online Algorithm for Parallel Scheduling of Serus with Resource Conflicts

                    Funds: Supported by State Key Laboratory of Smart Manufacturing for Special Vehicles and Transmission Systems(GZ2018KF001), National Natural Science Foundation of China (61763046)
                    • 摘要: 隨著大規模定制的市場需求日趨顯著, 賽如生產系統(Seru Production System, SPS)應運而生, 逐漸成為研究和應用領域的熱點. 本文針對帶有資源沖突的Seru在線并行調度問題進行研究, 即需要在有限的空間位置上安排隨動態需求而構建的若干Seru, 以總加權完工時間最小為目標, 決策Seru的構建順序及時間. 先基于平均延遲最短加權處理時間(Average Delayed Shortest Weighted Processing Time, AD-SWPT)算法, 針對其競爭比不為常數的局限性, 引入調節參數, 得到競爭比為常數的無資源沖突的Seru在線并行調度算法. 接下來, 引入沖突處理機制, 得到有資源沖突的Seru在線并行調度算法, αAD-I (α-Average Delayed Shortest Weighted Processing Time - Improved)算法, 特殊實例下可通過實例歸約的方法證明其競爭比與無資源沖突的情況相同. 最后, 通過實驗, 驗證了在波動的市場環境下算法對于特殊實例與一般實例的優越性.
                    • 圖  1  AD-SWPT與$\alpha$AD-SWPT算法流程圖

                      Fig.  1  The flow charts of AD-SWPT and $\alpha$AD-SWPT

                      圖  2  按照αAD-SWPT安排方案的構建時間示意圖

                      Fig.  2  Processing sub-queues in terms of starting time in the αAD-SWPT schedule

                      圖  3  $f(\alpha)$$g(\alpha)$的圖像

                      Fig.  3  Graphs of $f(\alpha)$ and $g(\alpha)$

                      圖  4  三個算法的競爭比

                      Fig.  4  Graphs of each algorithm' competitive ratio

                      圖  5  αAD-I算法流程圖

                      Fig.  5  The flow chart of αAD-I

                      圖  6  αAD-I算法在特殊實例$I^*$下的實驗結果

                      Fig.  6  The experimental results of αAD-I in $I^*$

                      圖  7  αAD-I算法在一般實例下的實驗結果

                      Fig.  7  The experimental results of αAD-I in general instances

                      圖  8  αAD-I算法在I*與一般實例下實驗結果對比

                      Fig.  8  The comparision between αAD-I in I* and αAD-I in general instances

                      圖  9  αAD-I算法與AD-SWPT改進算法在一般實例下的實驗結果對比

                      Fig.  9  The comparision between αAD-I and improved AD-SWPT in general instances

                      表  1  基本符號說明

                      Table  1  Basic symbolic explanation

                      符號說明
                      $t$ 當前時刻
                      $\hat{p}_j(t)$ 對于一個可行的安排方案, 在時刻$t$, 任務/$Seru$ $J_j$還剩余的處理時間, 若在時刻$t$, 該任務/$Seru$還未開始運作, 那么$\hat{p}_j(t)=p_j$
                      $\sigma(\cdot)$ 一般實例下, 應用相應算法所得到的安排方案, 也用于表示對應的目標值, 在本文中即為總加權完工時間$\displaystyle\sum w_j C_j$
                      $S_j$ 任務/$Seru$ $J_j$在安排方案$\sigma(\cdot)$中的構建時間
                      $C_j$ 任務/$Seru$ $J_j$在安排方案$\sigma(\cdot)$中的完工時間
                      ${\text{π}}(\cdot)$ 一般實例下, 應用最優離線算法所得到的安排方案, 也用于表示對應的目標值, 在本文中即為總加權完工時間$\displaystyle\sum w_j C_j$
                      下載: 導出CSV

                      表  2  無沖突時的特殊實例符號說明

                      Table  2  Symbolic explanation of four special instances without conflicts

                      符號說明
                      $I_1$ $\alpha$AD-SWPT算法生成的調度方案滿足在所有的位置中, 最早的SPoint和最晚的EPoint之間, 不存在任何時刻$t$所有位置都閑置的一類實例
                      $I'_1$ 滿足$I_1$的結構, 且滿足在$\alpha$AD-SWPT算法生成的調度方案下, 最后一個子隊列中所有$Seru$的加權處理時間相同的一類實例
                      $I_2$ 滿足$I_1$的結構, 且滿足所有$Seru$的加權處理時間相同的一類實例
                      $I_3$ 滿足$I_1$的結構, 且滿足在$\alpha$AD-SWPT算法生成的調度方案下, 最后一個子隊列中所有$Seru$的權重無窮大的一類實例
                      下載: 導出CSV

                      表  3  有沖突時的特殊實例符號說明

                      Table  3  Symbolic explanation of four special instances with conflicts

                      符號 說明
                      $F$ 沖突集合, 實例中所有帶有資源沖突的$Seru$的集合
                      $I^*$ 沖突集合$F$中, 先構建的$Seru$與后構建的$Seru$完工時間的比值總是不大于$(1+1/m)/2$的一類實例
                      $I^*_2$ 滿足$I^*$的結構, $\alpha$AD-I算法生成的調度方案下, 最早的SPoint和最晚的EPoint之間, 不存在任何時刻$t$, 所有位置都閑置; 且所有$Seru$的加權處理時間相同的一類實例
                      $I^*_3$ 滿足$I^*$的結構, $\alpha$AD-I算法生成的調度方案下, 最早的SPoint和最晚的EPoint之間, 不存在任何時刻$t$, 所有位置都閑置; 且最后一個子隊列中所有$Seru$的權重無窮大的一類實例
                      下載: 導出CSV
                      360彩票
                    • [1] 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, 2018, 56(1-2): 848?861 doi: 10.1080/00207543.2017.1403664
                      [2] 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, 2016, 103: 282?299
                      [3] 3 Roth A, Singhal J, Singhal K, Tang C S. Knowledge creation and dissemination in operations and supply chain management. Production and Operations Management, 2016, 25(9): 1473?1488 doi: 10.1111/poms.12590
                      [4] Yin Y, Kaku I, Stecke K E. The evolution of seru production systems throughout Canon. Operations Management Education Review, Scotland, UK: Neilson Journals Publishing, 2008. 27-40
                      [5] 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, 2010, 18(2): 89?113 doi: 10.1080/19761597.2010.9668694
                      [6] 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, 2015, 105: 285?299 doi: 10.1016/j.jclepro.2014.03.033
                      [7] 吳旭輝, 杜劭峰, 郝慧慧, 于洋, 殷勇, 李冬妮. 一種基于協同進化的流水線向Seru系統轉化方法. 自動化學報, 2018, 44(6): 1015?1027

                      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, 2018, 44(6): 1015?1027
                      [8] 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, 2017, 49-51: 67?76 doi: 10.1016/j.jom.2017.01.003
                      [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, 2014, 45-58
                      [10] 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, 2002, 41(4): 548?578 doi: 10.1111/1468-232X.00264
                      [11] 11 Stecke K E, Yin Y, Kaku I, Murase Y. Seru: the organizational extension of JIT for a super-talent factory. International Journal of Strategic Decision Sciences, 2012, 3(1): 106?119 doi: 10.4018/jsds.2012010104
                      [12] 12 Liu C G, Yang N, Li W J, Lian J, Evans S, Yin Y. Training and assignment of multi-skilled workers for implementing seru production systems. The International Journal of Advanced Manufacturing Technology, 2013, 69(5-8): 937?959 doi: 10.1007/s00170-013-5027-5
                      [13] 13 Yu Y, Tang J F, Gong J, Yin Y, Kaku I. Mathematical analysis and solutions for multi-objective line-cell conversion problem. European Journal of Operational Research, 2014, 236(2): 774?786 doi: 10.1016/j.ejor.2014.01.029
                      [14] 14 Yu Y, Tang J F, Sun W, Yin Y, Kaku I. Combining local search into non-dominated sorting for multi-objective line-cell conversion problem. International Journal of Computer Integrated Manufacturing, 2013, 26(4): 316?326 doi: 10.1080/0951192X.2012.717717
                      [15] 賈凌云, 李冬妮, 田云娜. 基于混合蛙跳和遺傳規劃的跨單元調度方法. 自動化學報, 2014, 40(5): 936?948

                      15 Jia Ling-Yun, Li Dong-Ni, Tian Yun-Na. An intercell scheduling approach using shuffled frog leaping algorithm and genetic programming. Acta Automatic Sinica, 2014, 40(5): 936?948
                      [16] 田云娜, 李冬妮, 劉兆赫, 鄭丹. 一種基于動態決策塊的超啟發式跨單元調度方法. 自動化學報, 2016, 42(4): 524?534

                      16 Tian Yun-Na, Li Dong-Ni, Li Zhao-He, Zheng Dan. A hyper-heuristic approach with dynamic decision blocks for inter-cell scheduling. Acta Automatic Sinica, 2016, 42(4): 524?534
                      [17] 17 Wu Y K, Jiang B, Lu N Y. A descriptor system approach for estimation of incipient faults with application to high-speed railway traction devices. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 49(10): 2108?2118
                      [18] Wu Y K, Jiang B, Wang Y L. Incipient winding fault detection and diagnosis for squirrel-cage induction motors equipped on CRH trains. ISA Transactions, to be published
                      [19] 19 Anderson E J, Potts C N. Online scheduling of a single machine to minimize total weighted completion time. Mathematics of Operations Research, 2004, 29(3): 686?697 doi: 10.1287/moor.1040.0092
                      [20] 20 Hall L A, Schulz A S, Shmoys D B, Wein J. Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Mathematics of Operations Research, 1997, 22(3): 513?544 doi: 10.1287/moor.22.3.513
                      [21] 21 Megow N, Schulz A S. On-line scheduling to minimize average completion time revisited. Operations Research Letters, 2004, 32(5): 485?490 doi: 10.1016/j.orl.2003.11.008
                      [22] 22 Correa J, Wagner M. LP-based online scheduling: from single to parallel machines. Mathematical Programming, 2009, 119(1): 109?136 doi: 10.1007/s10107-007-0204-7
                      [23] Sitters R. Efficient algorithms for average completion time scheduling. Integer Programming and Combinatorial Optimization. Berlin: Springer Berlin Heidelberg, 2010. 411-423
                      [24] Chakrabarti S, Phillips C A, Schulz A S, Shmoys D B, Stein C, Wein J. Improved scheduling algorithms for minsum criteria. Automata, Languages and Programming. Berlin: Springer Berlin Heidelberg, 1996. 646-657
                      [25] 25 Schulz A S, Skutella M. Scheduling unrelated machines by randomized rounding. SIAM Journal on Discrete Mathematics, 2002, 15(4): 450?469 doi: 10.1137/S0895480199357078
                      [26] 26 Tao J P. A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time. Computers and Operations Research, 2014, 43: 215?224 doi: 10.1016/j.cor.2013.09.016
                      [27] 27 Tao J P, Huang R, Liu T. A 2.28-competitive algorithm for online scheduling on identical machines. Journal of Industrial and Management Optimization, 2015, 11(1): 185?198 doi: 10.3934/jimo.2015.11.185
                      [28] 28 Tao J P, Chao Z J, Xi Y G. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6(2): 269?282 doi: 10.3934/jimo.2010.6.269
                      [29] 29 Tao J P, Chao Z J, Xi Y G, Tao Y. An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time. Information Processing Letters, 2010, 110(8-9): 325?330 doi: 10.1016/j.ipl.2010.02.013
                      [30] 30 Savelsbergh M W P, Uma R N, Wein J. An experimental study of lp-based approximation algorithms for scheduling problems. INFORMS Journal on Computing, 2005, 17(1): 123?136 doi: 10.1287/ijoc.1030.0055
                      [31] 31 Gu H Y. Computation of approximate α-points for large scale single machine scheduling problem. Computers and Operations Research, 2008, 35(10): 3262?3275 doi: 10.1016/j.cor.2007.02.018
                    • 加載中
                    計量
                    • 文章訪問數:  923
                    • HTML全文瀏覽量:  1290
                    • 被引次數: 0
                    出版歷程
                    • 收稿日期:  2019-10-09
                    • 錄用日期:  2020-02-07

                    目錄

                      /

                      返回文章
                      返回