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
                    詳細信息
                      作者簡介:

                      北京理工大學計算機學院博士研究生. 主要研究方向為賽如生產智能優化. 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

                    • 基金項目:  內蒙古自治區重大基礎研究開放課題(GZ2018KF001), 國家自然科學基金(61763046)資助

                    An Online Algorithm for Parallel Scheduling of Serus with Resource Conflicts

                    More Information
                    • Fund Project:  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
                    • [1] 趙曉麗, 宮華, 車平. 批處理機上具有兩類釋放時間的工件集競爭調度問題[J]. 自動化學報, doi: 10.16383/j.aas.2018.c170536
                      [2] 王永富, 馬冰心, 柴天佑, 張曉宇. PEMFC空氣供給系統的二型自適應模糊建模與過氧比控制[J]. 自動化學報, doi: 10.16383/j.aas.c180047
                      [3] 俞勝平, 柴天佑. 開工時間延遲下的煉鋼-連鑄生產重調度方法[J]. 自動化學報, doi: 10.16383/j.aas.2016.c150197
                      [4] 王大志, 劉士新, 郭希旺. 求解總拖期時間最小化流水車間調度問題的多智能體進化算法[J]. 自動化學報, doi: 10.3724/SP.J.1004.2014.00548
                      [5] 湯步洲, 王曉龍, 王軒. 置信度加權在線序列標注算法[J]. 自動化學報, doi: 10.3724/SP.J.1004.2011.00188
                      [6] 劉亮, 段納, 解學軍. 具有奇整數比次方的隨機高階非線性系統的輸出反饋鎮定[J]. 自動化學報, doi: 10.3724/SP.J.1004.2010.00858
                      [7] 於春月, 王成恩, 曲蓉霞. 中厚板熱軋生產調度優化方法[J]. 自動化學報, doi: 10.3724/SP.J.1004.2010.00282
                      [8] 趙君, 劉全利, 王偉. 冷軋生產調度模型及算法[J]. 自動化學報, doi: 10.3724/SP.J.1004.2008.00565
                      [9] 張居陽, 孫吉貴, 楊輕云. 半在線調度中約束求解算法研究[J]. 自動化學報, doi: 10.1360/aas-007-0765
                      [10] 趙玉芳, 唐立新. 極小化最大完工時間的單機連續型批調度問題[J]. 自動化學報
                      [11] 翟橋柱, 管曉宏, 郭燕, 孫嵐, 范煒. 具有混合動態約束的生產系統優化調度新算法[J]. 自動化學報
                      [12] 趙傳立, 張慶靈, 唐恒永. 具有線性惡化加工時間的調度問題[J]. 自動化學報
                      [13] 趙傳立, 張慶靈, 唐恒永. 一類線性加工時間單機調度問題[J]. 自動化學報
                      [14] 蔡圣義, 何勇. 工件從大到小到達的帶處理器費用的半在線調度算法[J]. 自動化學報
                      [15] 費越, 汪力新, 戴汝為. 競爭監督學習法在集成型識別系統中的應用[J]. 自動化學報
                      [16] 謝益民, 鄭應平. 具有同一交工期和指數加工時間的單機隨機調度[J]. 自動化學報
                      [17] 戴學東, 呂勇哉. 兩級多品種生產調度的專家系統[J]. 自動化學報
                      [18] 顧幸生, 胡仰曾. 按段多重契比雪夫多項式系及其在線性時變系統辨識中的應用[J]. 自動化學報
                      [19] 曹長修, 周鋒. 利用切比雪夫級數辨識線性分布參數系統[J]. 自動化學報
                      [20] 孫宗智. 計算機在問題解答領域中理解自然語言的一個實例--SSH系統[J]. 自動化學報
                    • 加載中
                    計量
                    • 文章訪問數:  747
                    • HTML全文瀏覽量:  1236
                    • 被引次數: 0
                    出版歷程
                    • 收稿日期:  2019-10-09
                    • 錄用日期:  2020-02-07

                    帶有資源沖突的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

                    摘要: 隨著大規模定制的市場需求日趨顯著, 賽如生產系統(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)算法, 特殊實例下可通過實例歸約的方法證明其競爭比與無資源沖突的情況相同. 最后, 通過實驗, 驗證了在波動的市場環境下算法對于特殊實例與一般實例的優越性.

                    English Abstract

                    江煜舟, 李冬妮, 靳洪博, 殷勇. 帶有資源沖突的 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
                    • 隨著大規模定制發展的趨勢, 傳統的生產系統, 如流水線(Flow Line)、豐田生產系統(Toyota Production System, TPS)、作業車間(Job Shop)、單元制造系統(Cellular Manufacturing System, CMS)等, 難以適應對動態不確定市場的快速響應需求, 賽如生產系統($ Seru $ Production System, SPS)應運而生[1-3].

                      Yin等[4]的研究展示了傳統生產系統轉化為SPS的重要性, Liu等[5, 6]的研究也表明SPS具有傳統生產系統難以企及的先進性和發展前景[7]. 自二十世紀九十年代起, SPS已經逐漸被亞洲的眾多電子企業采用, 如三星、佳能、LG、索尼、松下、富士通、NEC、富士康等[8-10].

                      $ Seru $代指SPS下的最小生產單元, 脫胎自基于精益(Lean)思想[11]的裝配流水線, 一個$ Seru $通常是生產一種或多種產品的裝配單元, 包含若干設備和工人.

                      一個SPS至少包含一個$ Seru $. SPS中的每一個$ Seru $都能夠頻繁地在短時間內被重構, 這給SPS帶來了極大的靈活性. 可以快速頻繁地建立、改變、拆除和轉化, 以響應頻繁波動的市場需求[9, 10].

                      SPS運作管理的基本原則為面向“組織”的準時生產原則(Just-In-Time Organisation System, JIT-OS), 是TPS傳統的面向“物料”的準時生產原則(Just-In-Time Material System, JIT-MS)的延伸. JIT-MS指在合適的時間地點投入合適的物料, 強調的是物料. 而JIT-OS強調的是組織, 對應到SPS, 即在合適的時間地點構建合適的$ Seru $. 這讓SPS可以通過調整生產組織結構快速獲得相應的生產能力, 為重構的實施提供了有效的載體和途徑[1].

                      SPS的運作可以被劃分為$ Seru $構建與$ Seru $調度兩個部分, $ Seru $構建指如何依據訂單任務對人員進行分配與組合, $ Seru $調度指如何在有限的空間下安排各個$ Seru $的構建順序及時間, 目前相關研究大都側重于$ Seru $構建. 如Liu等提出的解決工人分配問題的三段式啟發模型[12]、Yu等提出的以產品流通時間和總勞動時間為目標的一種非支配排序遺傳算法[13]、Yu等結合局部搜索算法提出的第二代非支配排序遺傳算法[14]、以及Wu等聯合$ Seru $構建與訂單分配提出的一種協同進化算法[7], 賈凌云等[15]與田云娜等[16]對跨單元調度問題的研究等.

                      目前對$ Seru $調度這一方面的研究相對較少, 難以充分體現SPS調整結構的動態性, 但要想充分發揮出SPS的靈活性, 快速響應“小批量, 多品種”市場的動態變化, 在提高$ Seru $構建效率之外, 還需要考慮結構上的變化, 即Seru調度. 如何在有限的位置上安排$ Seru $的構建順序及時間也是SPS運作管理基本原則JIT-OS的一項重要內容.

                      據此, 本文對$ Seru $在線并行調度問題展開了研究, 該問題具體是指, 將隨時間動態構建的$ n $$ Seru $安排到有限的$ m $個位置上, 以總加權完工時間最小為目標, 在線決策各$ Seru $的構建順序及時間. 同時, 考慮到具體的生產環境, 為了增強算法的實用性, 本文還將對帶有資源沖突的$ Seru $在線并行調度問題進行討論.

                      本文接下來的內容安排如下: 第1節, 給出具體的問題模型; 第2節, 給出AD-SWPT算法優化后得到的具有良好常數競爭比的在線算法; 第3節, 給出帶有資源沖突的$ Seru $在線并行調度算法, 并計算特殊實例下算法的競爭比; 第4節, 設計相關實驗, 展示實驗結果, 分析實驗數據; 第5節為結論部分.

                      • 本文所研究的帶有資源沖突的$ Seru $在線并行調度問題是指, 如何在有限個$ Seru $的可用位置上在線安排多個帶有資源沖突的$ Seru $, 以提高生產效率, 具體描述如下:

                        有一系列的訂單任務隨著時間發布, 每一個訂單任務對應一個$ Seru $, $ Seru $間可能存在資源沖突, 在無優先級的情況下, 將它們安排到$ m $$ Seru $的可用位置上進行處理, 存在資源沖突的兩個$ Seru $不能同時被處理, 每一個$ Seru $都對應一個訂單任務發布時間$ r_j $, 一個處理時間$ p_j $和一個權重$ w_j $, 所有關于$ Seru $的信息在訂單任務發布前都是未知的. 同樣, $ Seru $的總數量也無法提前得知.

                        目標量是總加權完工時間$ \displaystyle\sum{w_j C_j} $, 其中$ C_j $對應$ Seru $的完工時間, 本文的目的是探尋一個使得總加權完工時間$ \displaystyle\sum{w_j C_j} $最小的在線調度算法.

                        在線算法的優劣通常用它的競爭比$ \rho $來評價(對任意實例, 算法的目標函數值都不大于$ \rho $倍的最優離線目標值).

                        問題的基本假設如下:

                        1)車間中有$ m $$ Seru $的可用位置, 共有$ n $個訂單任務會發布($ m $$ n $均為正整數);

                        2)所有發布的訂單任務都可以被完成, 不考慮由工人技術或車間規模限制而導致的拒單;

                        3)一個訂單任務只能在一個$ Seru $中完成, 不考慮拆分;

                        4)一個$ Seru $的可用位置同一時間段最多安排一個$ Seru $;

                        5)一旦$ Seru $構建完成, 被安排到某一空的可用位置上, 在結束任務前$ Seru $的位置不會發生改變, 任務進程不會被打斷;

                        6)不考慮由工具損壞或自然災害等不可控因素導致的生產中斷;

                        7)車間24小時運轉不停工.

                        問題描述所需的符號變量如下:

                        $ t $表示當前時間;

                        $ m $表示$ Seru $的可用位置數目;

                        $ j $$ Seru $的序號索引$ (j = 1,2,3,\cdots) $;

                        $ k $為車間內$ Seru $可用位置的序號索引$ (k = 1, $$2,3,\cdots) $;

                        $ r_j $表示$ Seru $對應的訂單任務發布時間($ r_j \!\geq\! 0 $);

                        $ p_j $表示$ Seru $的處理時間($ p_j>0 $);

                        $ w_j $表示$ Seru $的權重($ w_j\geq 0 $);

                        $ S_j $表示$ Seru $的構建時間($ S_j\geq r_j $);

                        $ C_j $表示$ Seru $的完工時間($ C_j = S_j+p_j $).

                        決策變量:

                        $$ X_j^k(t) = \begin{cases} 1,&t{{\text{時刻}}Seru\ j{\text{在位置}}k{\text{上運作}}}\\ 0,&{\text{其他}} \end{cases} $$

                        目標量總加權完工時間的表示為:

                        $$ \min \displaystyle\sum\limits_j{w_j C_j} $$

                        根據實際生產中的問題特性和約束, 本文的約束條件描述如下:

                        $$ S_j\geq r_j $$ (1)
                        $$ \displaystyle\sum\limits_{k,j} X_j^k(t)\leq m, \ \forall\ t $$ (2)
                        $$ \displaystyle\sum\limits_j X_j^k(t)\leq 1, \ \forall\ t, k $$ (3)
                        $$ C_j = S_j+p_j $$ (4)

                        其中, 式(1)表示訂單任務發布之前, 一切信息未知, 無法構建相應$ Seru $; 式(2)表示任意時刻工廠內最多容納$ m $$ Seru $運作; 式(3)表示任意時刻同一位置上最多容納一個$ Seru $運作; 式(4)表示$ Seru $一旦構建, 將會持續運作至完成訂單任務, 中途不會被打斷.

                        目前尚無專門針對有資源沖突的$ Seru $在線并行調度問題的相關研究, 考慮類似的并行機調度問題構建. $ Seru $的空間位置對應到并行機, 將$ Seru $安排在相應的位置上. 并行機調度問題的跨領域應用在控制系統的故障診斷中也有體現[17, 18].

                        對并行機調度問題, Anderson和Potts率先提出了單機器下競爭比為2的最優確定性在線算法, 最小加權處理時間(Shortest Weighted Processing Time, SWPT)算法[19]. 多機器下, Hall等設計了一個競爭比為(4+$ \varepsilon $)的算法[20], 其中$ \varepsilon $為任意小的正數. Megow和Schulz將競爭比改進為3.28[21]. Correa和Wagner又提出了競爭比為2.618的無優先級$ \alpha $調度(Non-preemptive $ \alpha $ Scheduling, NAS)算法[22]. Sitters設計了O NLINE($ \varepsilon $)算法[23], 并證明其競爭比不大于$ {(1+1/\sqrt{m})}^{2} $(3e-2)/(2e-2), 在并行機數量較少時該算法遠優于NAS算法, 但在并行機數量增大時NAS算法的競爭比趨近1.79, 優于O NLINE($ \varepsilon $)算法. 隨機化被允許時, 可以得到更好的算法, 這里不再贅述[22, 24, 25].

                        通過推廣Megow和Schulz設計的單機器下的算法[21], Tao提出一個以總加權完工時間最小為目標的并行機在線調度算法, 即平均延遲最短加權處理時間(Average delayed shortest weighted processing time, AD-SWPT)算法, 算法競爭比為(2.5-1/2$ m $)[26]. 對AD-SWPT進行改進, Tao等提出一個競爭比為$(1+(m-1+\sqrt{17{m}^{2}-2m+1})/ $$ 4m)\approx2.28 $的算法[27], 是目前文獻中以總加權完工時間最小為目標的并行機在線調度算法中競爭比最小的一個. 但無論是AD-SWPT算法還是其改進算法, 所得到的競爭比都不是一個常數, 后者還極為復雜.

                        先基于AD-SWPT算法及其改進算法得到一個競爭比為常數的算法, 有利于將原本針對于并行機調度問題的算法應用于SPS, 以及在無資源沖突的$ Seru $在線并行調度算法上添加沖突機制后對算法性能展開數學上的理論分析.

                        非常數的競爭比會讓對帶有資源沖突的$ Seru $在線并行調度算法競爭比的計算變得更加復雜, 甚至難以推進. 同時, 一個具有常數競爭比的算法也能為本領域及并行機調度等相關領域的后續研究提供更加便捷與直觀的參照.

                        因此, 本文針對$ Seru $在線并行調度問題, 首先考慮無資源沖突的情況, 對AD-SWPT算法競爭比不為常數的局限性, 設計$ \alpha $AD-SWPT算法, 采用實例歸約的方法來計算競爭比, 得到一個具有良好常數競爭比的算法, 再在$ \alpha $AD-SWPT算法的基礎上, 針對帶有資源沖突的$ Seru $在線并行調度問題, 將問題轉化為計算具有特殊結構實例的競爭比, 可以得到某些特殊情況下的優化算法.

                      • AD-SWPT算法. 對并行機的在線調度問題, 一旦出現空機器和一些可以被安排的任務時, 在所有已生成但未安排的任務中, 選擇處理時間與權重比值$ p_j/w_j $(后文中用加權處理時間來代指這個比值)最小的一個. 當出現相等的情況時, 選擇處理時間較小的. 記被選擇的任務為$ J_i $, 計算時刻$ t $所有機器上正在運作的任務的剩余處理時間總和. 這個值根據表1中的符號可以被寫作$ \sum_{S_j\leq t}^{}{\hat{p_j}(t)} $. 那么如果

                        表 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$
                        $$ \dfrac{p_i+\displaystyle\sum\limits_{S_j\leq t}^{}{\hat{p_j}(t)}}{m}\leq t $$ (5)

                        就在$ t $時刻將$ J_i $安排在空機器上; 否則, 等下一個時刻重復以上整個過程.

                        對一般情況下AD-SWPT算法的競爭比, 有:

                        定理1.[26]對以總加權完工時間為目標量的無優先級并行機在線調度問題, AD-SWPT算法的競爭比區間為 [2,2.5?1/2m].

                        定理1的證明采用了實例歸約, 該思想在對兩個半在線單調度問題的分析中被首次提出[28, 29]. 在證明中發現, AD-SWPT算法可以被進一步優化.

                      • AD-SWPT算法的競爭比(2.5-1/2m)不為常數, 而其優化算法的競爭比$ (1+(m-1+ $$\sqrt{17{m}^{2}-2m+1})/4m) $, 雖然在數值上略有減小, 卻更為復雜. 于是, 本文在AD-SWPT算法的基礎上, 設計了一種競爭比為常數的調度算法. 記為$ \alpha $AD-SWPT ($ \alpha $-Average Delayed Shortest Weighted Shortest Processing Time)算法.

                        在式(5)右側添加調度參數$ \alpha $(當$ \alpha = 1 $時, 優化算法退化為AD-SWPT算法, $ m\to \infty $時, 新發布的任務無需等待可立即被安排, 可以認為$ \alpha >1 $[27]), 將$ t $變為$ \alpha t $, 同時將并行機的調度問題, 對應到$ Seru $的調度問題上, AD-SWPT算法變化如下:

                        αAD-SWPT算法 一旦出現空位置和一些可以被構建的$ Seru $時, 在所有對應訂單任務已發布但未構建的$ Seru $中選擇加權處理時間$ p_j/w_j $最小的一個. 當出現相等的情況時, 選擇處理時間較小的. 記被選擇的$ Seru $$ J_i $, 計算時刻$ t $所有位置上正在處理的$ Seru $的剩余處理時間總和. 這個值根據表1中的符號可以被寫作$ \sum_{S_j\leq t}^{}{\hat{p_j}(t)} $. 那么如果

                        $$ \dfrac{p_i+\displaystyle\sum\limits_{S_j\leq t}^{}{\hat{p_j}(t)}}{m}\leq \alpha t $$ (6)

                        就在$ t $時刻將$ J_i $安排在空位置上; 否則, 等下一個時刻重復以上整個過程.

                      • 盡管競爭比是指在所有可能的實例中所能達到的最壞性能比, 但窮舉搜索是不可能的, 因為集合所包含的實例數目是無窮的.

                        性能比與競爭比的概念類似, 在接下來的證明過程中, 為了不至于造成誤解, 將非一般實例集合下的競爭比稱為性能比.

                        $ \alpha $AD-SWPT算法競爭比的計算方法與AD-SWPT算法同源[26], 同樣采用實例歸約.

                        實例歸約的思路是在實例空間中找出最壞的情況, 證明部分實例的競爭比不小于其他實例, 從而縮小搜索空間, 在更小的集合內對算法的性能比進行分析. 這些更小集合里的實例擁有的特殊性質, 可以使對性能比計算的分析更加深入.

                        本文中, 最壞的情況可能從兩類實例集中得到. 可以推測, 這兩類實例性能比的表達式中含有調節參數$ \alpha $.

                        圖  1  AD-SWPT與$\alpha$AD-SWPT算法流程圖

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

                      • $ \alpha $AD-SWPT算法中由于存在延遲機制, 所以在一些位置上會出現空余的時間段.

                        為了方便敘述, 參考AD-SWPT算法競爭比計算中的定義[26]:

                        稱一個位置在時刻$ t $為“閑置”, 如果這個位置在時間段($ t-\varepsilon $,$ t+\varepsilon $)閑置; 稱一個位置在時刻t為“運作”, 如果這個位置在時間段($ t-\varepsilon $,$ t+\varepsilon $)不閑置, 其中$ \varepsilon $為無窮小的正數.

                        稱時刻$ t $是一個位置的“運作起點”(記為SPoint), 如果這個位置在時間段($ t-\varepsilon $,$ t $)閑置, 在時間段($ t $,$ t+\varepsilon $)不閑置; 稱時刻$ t $是一個位置的“運作終點”(記為EPoint), 如果這個位置在時間段($ t-\varepsilon $,$ t $)不閑置, 在時間段($ t $,$ t+\varepsilon $)閑置.

                        根據Tao在論文中的描述, 可以證明, 最壞情況下的實例在$ \alpha $AD-SWPT算法下產生的調度方案中, 所有位置最早的SPoint和最晚的EPoint之間, 不存在時刻$ t $, 滿足所有位置都在時刻t閑置[26].

                        記滿足上述性質的實例為$ I_1 $.

                        $ \sigma(I_1) $中的$ Seru $按照構建時間排列, 記作$J_1, $$ J_2,\cdots,J_n $. 以隊列內$ Seru $的加權處理時間非減為原則, 可將$ Seru $分割為若干個子隊列, 每個子隊列最后一個$ Seru $的加權處理時間大于下一個子隊列第一個$ Seru $的加權處理時間, 如圖2所示.

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

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

                      • 首先引入一個重要引理[28], 這個引理會在接下來的分析中被反復使用.

                        引理2. $ f(x) $$ g(x) $是定義在區間$ [u,v] $上的兩個正值函數, 且$ f(x) $為凸函數, $ g(x) $為凹函數. $ f(x)/g(x) $的最大值在區間端點處取到, 即:

                        $$ \frac{f(x)}{g(x)}\leq \max\{\frac{f(u)}{g(u)},\frac{f(v)}{g(v)}\}\ \forall x\in [u,v] $$

                        證明. $ \forall x\in[u,v] $, $ \exists a\in[0,1] $, $s.t.\ x = au+ $$ (1-a)v $. 又$ f(x) $為凸函數, $ g(x) $為凹函數, 那么有:

                        $ f(x)\leq af(u)+(1-a)f(v) $.

                        $ g(x)\geq ag(u)+(1-a)g(v) $.

                        $ f(x) $$ g(x) $是定義在區間$ [u,v] $上的兩個正值函數, 那么有:

                        $$ \dfrac{f(x)}{g(x)}\leq \dfrac{af(u)+(1-a)f(v)}{ag(u)+(1-a)g(v)}\leq \max\{\frac{f(u)}{g(u)},\dfrac{f(v)}{g(v)}\} $$

                        可以證明, 在區間的某個端點開放時引理也成立, 此時$ f(x)/g(x) $的上確界存在于相對應的端點處.

                        按照Tao的處理方式, 將$ I_1 $在性能比不減的情況下, 化歸為兩類特殊實例, 它們在$ \alpha $AD-SWPT算法下生成的調度方案具有更多簡單特殊的子隊列結構.

                        第一類, 實例中的$ Seru $擁有相同的加權處理時間, 記作$ I_2 $; 第二類, 實例中部分$ Seru $的權重趨近于無窮大, 記作$ I_3 $.

                        $ I'_1 $為一個過渡實例, 它在$ \alpha $AD-SWPT算法下生成的調度方案滿足最后一個子隊列中所有$ Seru $具有相同的加權處理時間.

                        直接引用Tao在論文中給出的定理, 有:

                        引理3.[26]對任意實例$ I_1 $, 都能通過修改$ I_1 $$ Seru $的權重來找到一個過渡實例$ I'_1 $, 使得:

                        $$ \dfrac{\sigma(I_1)}{{\text{π}}(I_1)}\leq \dfrac{\sigma(I'_1)}{{\text{π}}(I'_1)} $$

                        引理4.[26]對任意實例$ I'_1 $, 都能通過修改$ I'_1 $$ Seru $的權重來構建一個實例$ I_2 $$ I_3 $, 使得:

                        $$ \dfrac{\sigma(I'_1)}{{\text{π}}(I'_1)}\leq \max\{\dfrac{\sigma(I_2)}{{\text{π}}(I_2)},\dfrac{\sigma(I_3)}{{\text{π}}(I_3)}\} $$

                        表 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$的權重無窮大的一類實例
                      • 引理5. 在$ \alpha $AD-SWPT算法下, 對于特殊實例$ I_2 $, 有:

                        $$ \dfrac{\sigma(I_2)}{{\text{π}}(I_2)}\leq\dfrac{5+\sqrt{17}}{4} $$

                        證明. 參考Tao在計算AD-SWPT算法下競爭比時的推理過程[26], 在不影響性能比大小的情況下, 對$ I_2 $中所有的$ Seru $進行標準化.

                        $ \sigma(I_2) $中最后一個SPoint為$ r_L $, 在$ r_L $之后, 每一個位置上$ Seru $都被連續安排, 不存在有位置空閑的時間段. 下面分為兩種情況討論:

                        1)在$ \sigma(I_2) $中不存在對應訂單任務先于$ r_L $發布, 但于$ r_L $或之后構建的$ Seru $. 將$ \sigma(I_2) $中于$ r_L $或之后構建的$ Seru $, 按照構建時間的順序排列, 記為$ J_1,J_2,\cdots,J_n $, 剩余$ Seru $構成的過渡實例記為$ I'_2 $.

                        $ \displaystyle\sum\nolimits_{S_i<r_L}^{}\hat{p_j}(r_L): = A $, $ \displaystyle\sum\nolimits_{j = 1}^{n}p_j: = B $.

                        可以給出$ \sigma(I_2) $的一個放縮及$ {\text{π}} (I_2) $的一個下界:

                        $ \sigma(I_2)\leq\sigma(I'_2)+(r_L\!+\!\dfrac{A}{m})B\!+\!\dfrac{B^2}{2m}\!+\!(1\!-\!\dfrac{1}{2m})\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2 $

                        ${\text{π}}(I_2)\geq{\text{π}}(I'_2)+r_LB+\dfrac{B^2}{2m}+\dfrac{1}{2}\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2 $

                        根據$ \alpha $AD-SWPT算法, 有$ A/\alpha m\leq r_L $. 結合以上兩個式子, 有:

                        $$ \begin{array}{l} \dfrac{\sigma(I_2)}{{\text{π}}(I_2)}\leq \\ \quad\max\{\dfrac{\sigma(I'_2)}{{\text{π}}(I'_2)},\dfrac{(r_L\!\!+\!\!\dfrac{A}{m})B\!\!+\!\!\dfrac{B^2}{2m}\!\!+\!\!(1\!\!-\!\!\dfrac{1}{2m})\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2}{r_LB+\dfrac{B^2}{2m}+\dfrac{1}{2}\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2}\} \leq \\ \quad\max\{\dfrac{\sigma(I'_2)}{{\text{π}}(I'_2)},1+\alpha\} \end{array} $$

                        2)在$ \sigma(I_2) $中存在至少一個$ Seru $, 對應訂單任務于$ r_L $之前發布, 但于$ r_L $或之后構建, 記為$ J_k $.

                        $ \sigma(I_2) $中于$ r_L $或之后完成的$ Seru $, 按照構建時間的順序排列, 記為$ J_1,J_2,\cdots,J_n $, 剩余$ Seru $構成的過渡實例記為$ I'_2 $.

                        $ \{J_1,J_2,\cdots,J_n\} $分為如下兩個集合:

                        $$ Q_1 = \{J_i|S_j<r_L,C_j>r_L\}\cup\{J_k\} $$
                        $$ Q_2 = \{J_i|S_j\geq r_L\}\setminus{J_k} $$

                        $ \displaystyle\sum\nolimits_{J_j\in Q_1}p_j: = A $, $ \displaystyle\sum\nolimits_{J_j\in Q_2}p_j: = B $.

                        可以給出$ \sigma(I_2) $的一個放縮及${\text{π}}(I_2) $的一個下界:

                        $$ \begin{split} &\sigma(I_2)\leq\sigma(I'_2)+r_L(A+B)+\dfrac{(A+B)^2}{2m}+\\ &\quad (1-\dfrac{1}{2m})\displaystyle\sum\nolimits_{J_i\in Q_1\cup Q_2}^{}p_j^2 \\ &\quad {\text{π}}(I_2)\geq{\text{π}}(I'_2)+\dfrac{(A+B)^2}{2m}+\dfrac{1}{2}\displaystyle\sum\nolimits_{J_i\in Q_1\cup Q_2}^{}p_j^2 \end{split} $$

                        $ A/\alpha m\geq r_L $, $ \displaystyle\sum\nolimits_{J_j\in Q_1}^{}p_j^2\geq A^2/m $. 結合以上兩個式子, 有:

                        $$ \begin{split} &\dfrac{\sigma(I_2)}{{\text{π}}(I_2)}\leq \max\{\dfrac{\sigma(I'_2)}{{\text{π}}(I'_2)}, \\ &\quad\dfrac{r_L(A\!\!+\!\!B)\!\!+\!\!\dfrac{(A+B)^2}{2m}\!\!+\!\!(1\!\!-\!\!\dfrac{1}{2m})\displaystyle\sum\nolimits_{j\in Q_1\cup Q_2}^{}p_j^2}{\dfrac{(A+B)^2}{2m}+\dfrac{1}{2}\displaystyle\sum\nolimits_{j\in Q_1\cup Q_2}^{}p_j^2}\} \leq \\ &\quad \max\{\dfrac{\sigma(I'_2)}{{\text{π}}(I'_2)},2+\dfrac{\dfrac{A(A+B)}{\alpha m}-\dfrac{(A+B)^2}{2m}-\dfrac{A^2}{2m^2}}{\dfrac{(A+B)^2}{2m}+\dfrac{A^2}{2m}}\} =\\ &\quad \max\{\dfrac{\sigma(I'_2)}{{\text{π}}(I'_2)},1.5+\dfrac{1}{\alpha}-\dfrac{1}{2m}\} \end{split} $$

                        通過將$ I'_2 $重寫作$ I_2 $, 不斷迭代, 可以得到:

                        $$ \begin{split} &\dfrac{\sigma(I_2)}{{\text{π}}(I_2)}\leq \max\{1+\alpha,1.5+\dfrac{1}{\alpha}-\dfrac{1}{2m}\} \leq \\ &\quad \max\{1+\alpha,1.5+\dfrac{1}{\alpha}\}(m\to+\infty) \end{split} $$

                        $ f(\alpha) = 1+\alpha $, $ g(\alpha) = 1.5+1/\alpha $, 圖像如圖3:

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

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

                        $ f(\alpha) = g(\alpha) $, 可以得到:

                        $ \alpha = \dfrac{1+\sqrt{17}}{4} $時, 有$ \dfrac{\sigma(I_2)}{{\text{π}}(I_2)} \leq\dfrac{5+\sqrt{17}}{4}\approx2.28 $.

                        引理6. 在$ \alpha $AD-SWPT算法下, 對于特殊實例$ I_3 $, 有:

                        $$ \dfrac{\sigma(I_3)}{{\text{π}}(I_3)}\leq\dfrac{5+\sqrt{17}}{4} $$

                        證明. 參考Tao在計算AD-SWPT算法下競爭比時的推理過程[26], 將$ \sigma(I_3) $中最后一個子隊列中所有$ Seru $的集合記為$ Q_\infty $, 將$ Q_\infty $中最早發布的訂單任務的發布時間記為$ r_f $, 將$ \sigma(I_3) $中最后一個SPoint記為$ r_L $. 下面分為三種情況討論:

                        1) $ r_L\leq r_f $.

                        $ Q_\infty $中的$ Seru $按照構建時間的順序排列, 記為$ J_1,J_2,\cdots,J_n $. 記$ \displaystyle\sum\nolimits_{J_j\in Q_\infty}^{}p_j: = B $. 可以得到$ \sigma(I_3) $的一個上界以及$ {\text{π}}(I_3) $的一個下界:

                        $$ \begin{split} &\sigma(I_3)\leq O(1)+\delta((1+\alpha)r_fB+\dfrac{B^2}{2m}+\\ &\quad(1-\dfrac{1}{2m})\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2)\\ &\quad{\text{π}}(I_3)\geq O(1)+\delta(r_fB+\dfrac{B^2}{2m}+\dfrac{1}{2}\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2) \end{split} $$

                        其中$ O(1) $表示一個有限的數值.

                        $ \delta\to+\infty $時, 顯然有:

                        $$ \dfrac{\sigma(I_3)}{{\text{π}}(I_3)}\leq 1+\alpha $$

                        2) $ r_L\!>\!r_f $, 且$ \sigma(I_3) $中所有于$ r_L $時刻運作的$ Seru $全部屬于$ Q_\infty $. 剔除$ I_3 $中的某些$ Seru $, 可以得到$ r_L $不是最后一個SPoint的過渡實例$ I'_3 $, 進而有:

                        $$ \dfrac{\sigma(I_3)}{{\text{π}}(I_3)}\leq \max\{\dfrac{\sigma(I'_3)}{{\text{π}}(I'_3)},\dfrac{5+\sqrt{17}}{4}\} $$

                        3) $ r_L\!\!>\!\!r_f $, 且$ \sigma(I_3) $中于$ r_L $時刻運作的$ Seru $中至少存在一個不屬于$ Q_\infty $. 下面再分為兩種情況討論:

                        a)在$ \sigma(I_3) $中, $ Q_\infty $中不存在對應訂單任務于$ r_L $之前發布, 但構建于$ r_L $或之后的$ Seru $. 這種情況下, 所有對應訂單任務于$ r_L $或之后發布的$ Seru $也于$ r_L $或之后構建. 從$ I_3 $中剔除這些$ Seru $之后可以得到一個過渡實例$ I'_3 $.

                        $ \displaystyle\sum\nolimits_{S_j\geq r_L}^{}p_j: = B $, 則有:

                        b)在$ \sigma(I_3) $中, $ Q_\infty $中至少存在一個對應訂單任務于$ r_L $之前發布, 且構建于$ r_L $或之后的$ Seru $.

                        $ \sigma(I_3) $中, 于$ r_L $時刻運作, 但不屬于$ Q_\infty $$ Seru $組成的集合記為$ Q' $. 根據$ \alpha $AD-SWPT算法, 這些$ Seru $一定于$ r_f $之前構建.

                        $ Q_\infty $中于$ r_L $之后完成的$ Seru $分為如下兩個集合:

                        $$ Q_1 = \{J_i\in Q_\infty|S_j<r_L,C_j>r_L\}\cup\{J_k\} $$
                        $$ Q_2 = \{J_i\in Q_\infty|S_j\geq r_L\}\setminus\{J_k\} $$

                        $ \displaystyle\sum\nolimits_{j\in Q'}\hat{p}_j(r_L): = A' $.

                        $ \displaystyle\sum\nolimits_{J_j\in Q_1}p_j: = A $,$ \displaystyle\sum\nolimits_{J_j\in Q_2}p_j: = B $.

                        $ I_3 $中剔除掉$ Q_1 $$ Q_2 $中的$ Seru $, 構建過渡實例$ I'_3 $. 則有:

                        $$\begin{split} &\sigma(I_3)\leq\sigma(I'_3)+\delta((r_L+\dfrac{A'}{m})(A+B)+\dfrac{(A+B)^2}{2m}+\\ &\quad (1-\dfrac{1}{2m})\displaystyle\sum\nolimits_{J_j\in Q_1\cup Q_2}^{}p_j^2)\\ &\quad{\text{π}}(I_3)\!\geq\!{\text{π}}(I'_3)+\delta(r_f(A+B)+\dfrac{(A+B)^2}{2m}+ \\ &\quad \dfrac{1}{2}\displaystyle\sum\nolimits_{J_j\in Q_1\cup Q_2}p_j^2) \end{split} $$

                        進而:

                        $$ \dfrac{\sigma(I_3)}{{\text{π}}(I_3)}\leq \max\{\dfrac{\sigma(I'_3)}{{\text{π}}(I'_3)},1+\alpha,1.5+\dfrac{1}{\alpha}-\dfrac{1}{2m}\} $$

                        綜合上述三種情況, 有:

                        $$ \dfrac{\sigma(I_3)}{{\text{π}}(I_3)}\leq \max\{\dfrac{\sigma(I'_3)}{{\text{π}}(I'_3)},1+\alpha,1.5+\dfrac{1}{\alpha}-\dfrac{1}{2m}\} $$

                        通過將$ I'_3 $重寫作$ I_1 $, 不斷迭代, 可以得到:

                        $$ \begin{split} &\frac{\sigma(I_3)}{\pi(I_3)}\leq \max\{1+\alpha,1.5+\frac{1}{\alpha}-\frac{1}{2m}\}\leq \\ &\quad\max\{1+\alpha,1.5+\frac{1}{\alpha}\}(m\to+\infty) \end{split} $$

                        同引理5的證明, 可以得到:

                        $ \alpha = \dfrac{1+\sqrt{17}}{4} $時, 有$ \dfrac{\sigma(I_3)}{\pi(I_3)} \leq\dfrac{5+\sqrt{17}}{4}\approx2.28 $.

                        從而有如下定理:

                        $$ \begin{array}{l} \dfrac{\sigma(I_3)}{{\text{π}}(I_3)}\leq \dfrac{\sigma(I'_3)\!\!+\!\!\delta((r_L\!\!+\!\!\dfrac{\displaystyle\sum\nolimits_{S_j<r_L}p_j}{m})B\!\!+\!\!\dfrac{B^2}{2m}\!\!+\!\!(1\!\!-\!\!\dfrac{1}{2m})\!\displaystyle\sum\nolimits_{S_j\geq r_L}p_j^2)}{{\text{π}}(I'_3)+\delta(r_LB+\dfrac{B^2}{2m}+\dfrac{1}{2}\displaystyle\sum\nolimits_{S_j\geq r_L}^{}p_j^2)}\!\leq \!\max\{\dfrac{\sigma(I'_3)}{{\text{π}}(I'_3)},1+\alpha\} \end{array} $$

                        定理7. 對無資源沖突的$ Seru $在線并行調度問題, $ \alpha $AD-SWPT算法的最優競爭比在$ \alpha = (1+$$\sqrt{17})/4 $時取得, 為$ (5+\sqrt{17})/4\approx2.28 $.

                        圖4給出了AD-SWPT算法、AD-SWPT的改進算法以及$ \alpha $AD-SWPT算法的競爭比對比圖, 可以看出與AD-SWPT算法比較, 雖然$ Seru $的可用位置數目$ m = 1,2 $時, $ \alpha $AD-SWPT算法競爭比偏大, 但是到$ m>2 $時, AD-SWPT算法的競爭比不斷增大, 競爭比恒為常數的$ \alpha $AD-SWPT算法的性能明顯更優.

                        圖  4  三個算法的競爭比

                        Figure 4.  Graphs of each algorithm' competitive ratio

                        $ \alpha $AD-SWPT算法的競爭比雖略大于AD-SWPT的改進算法, 不具有競爭比上的絕對優勢, 但隨著$ m $的增大, 二者之間的細微差距在不斷縮小, 直至可以忽略不計. 對此, 后文會通過計算機模擬實驗在有資源沖突的情況下進行驗證.

                      • 若有兩個$ Seru $由于人力資源或物力資源上的沖突, 不能同時被安排, 就稱這兩個$ Seru $是具有資源沖突的. 記本文所設計的帶有資源沖突情況下的調度算法為$ \alpha $AD-I($ \alpha $-Average Delayed Shortest Weighted Processing Time - Improved)算法.

                        αAD-I算法. 一旦出現空位置和一些可以被安排的$ Seru $時, 在所有對應訂單任務已發布但未構建的$ Seru $中選擇加權處理時間$ p_j/w_j $最小的一個. 當出現相等的情況時, 選擇處理時間較小的. 記被選擇的$ Seru $$ J_i $, 計算時刻$ t $所有位置上正在處理的$ Seru $的剩余處理時間總和. 這個值根據表1中的符號可以被寫作$ \displaystyle\sum\nolimits_{S_j\leq t}^{}{\hat{p_j}(t)} $. 那么如果

                        $$ \dfrac{p_i+\displaystyle\sum\limits_{S_j\leq t}^{}{\hat{p_j}(t)}}{m}\leq \alpha t $$ (6)

                        并且$ J_i $與正在運作的$ Seru $間無資源沖突, 就在$ t $時刻將$ J_i $安排在空位置上; 否則, 等下一個時刻重復以上整個過程.

                        沿用實例歸約的方法, 對有資源沖突的$ Seru $在線并行調度問題展開討論, 對具有特殊結構的實例進行競爭比的計算.

                        $ \alpha $AD-I算法構建的$ Seru $中具有資源沖突的$ Seru $記為沖突集合$ F $. 若存在這樣的實例, $ F $中先構建的$ Seru\ J_v $與后構建的$ Seru\ J_k $完工時間的比值滿足$ p_v/p_k\leq(1+1/m)/2 $, 則記這樣的實例為$ I^* $.

                        圖  5  αAD-I算法流程圖

                        Figure 5.  The flow chart of αAD-I

                      • 顯然, 對于$ I^* $, 章節2.2.1和章節2.2.2中的分析都是適用的. 那么有如下引理:

                        引理8. 對任意實例$ I^* $, 都可以通過將$ I^* $中部分$ Seru $提出, 以及修改權重來構建出一個實例$ I_2^* $$ I_3^* $, 使得:

                        $$ \dfrac{\sigma(I^*)}{{\text{π}}(I^*)}\leq \max\{\dfrac{\sigma(I_2^*)}{{\text{π}}(I_2^*)},\dfrac{\sigma(I_3^*)}{{\text{π}}(I_3^*)}\} $$

                        引理9. 在$ \alpha $AD-I算法下, 對于特殊實例$ I_2^* $, 有:

                        $$ \dfrac{\sigma(I_2^*)}{{\text{π}}(I_2^*)}\leq\dfrac{5+\sqrt{17}}{4} $$

                        證明. $ \sigma(I_2^*) $中, 同引理5的證明, 在不影響性能比大小的情況下, 對$ I_2^* $中所有的$ Seru $進行標準化,

                        考慮$ \sigma(I_2) $中最后的一個SPoint, 記為$ r_L $. 也就是說, 在$ r_L $之后, 每一個位置上$ Seru $都被連續安排, 不存在有位置空閑的時間段.

                        引理5的證明分為了兩種情況討論, 顯然, 情況1)下的證明不會發生改變.

                        而對情況2), 對于對應訂單任務在$ r_L $之前發布, 但構建于$ r_L $或之后的所有$ Seru $, 若存在一個$ Seru $使得式(6)不成立, 證明過程不會發生改變; 若對其中的任意$ Seru $, 式(6)均成立, 根據$ \alpha $AD-I算法, 有:

                        在該類子情況下, 存在一個$ Seru $, 記為$ J_k $, 對應訂單任務于$ r_L $之前發布, 但構建于$ r_L $或之后, $ J_k\in F $. 將$ F $中于$ r_L $時刻運作的$ Seru $記為$ J_v $, 則$ p_v/p_k\leq(1+1/m)/2 $.

                        將于$ r_L $或之后構建的$ Seru $, 按構建時間順序排列, 記為$ J_1,J_2,\cdots,J_n $.

                        $ I_2^* $中剔除掉$ J_1,J_2,\cdots,J_n $, 記剩余的$ Seru $構成的過渡實例為$ I_2^* {'}$. $ \{J_1,J_2,\cdots,J_n\} $對剩余$ Seru $的安排不會有影響.

                        $ \displaystyle\sum\nolimits_{S_i<r_L}^{}\hat{p}_i(r_L): = A $, $ \displaystyle\sum\nolimits_{j = 1}^{n}p_j: = B $.

                        同引理5情況1)的證明, 有:

                        $$ \begin{split} &\sigma(I_2^*)\leq\sigma(I_2^{*'})+(r_L+\dfrac{A}{m})B+\dfrac{B^2}{2m}+ \\ &\quad(1-\dfrac{1}{2m})\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2 \end{split} $$ (7)

                        $ \{J_1,J_2,\cdots ,J_n\}\setminus\{J_k\} $視作一個單獨的實例, 且將其中所有$ Seru $的對應的訂單任務發布時間放縮到$ r_L $. 同引理5情況1)的證明, 可以給出$ \pi(I_2^*) $的一個下界:

                        $$ \begin{split} &{{\text{π}} (I_2^*) \!\ge\! {\text{π}} (I_2^{*'}) \!+\! {\text{π}} (\{ {J_1},{J_2},\cdots,{J_n}\} \setminus \{ {J_k}\} ) \!+\! ({r_k} \!+\! {p_k}){p_k}}\!\ge\! \\ &{{\kern 1pt}{\kern 1pt}{\text{π}} (I_2^{*'}) \!+\! {r_L}(B \!-\! {p_k}) \!+\! \dfrac{{{{(B - {p_k})}^2}}}{{2m}} \!+\! \dfrac{1}{2}\displaystyle\sum\nolimits_{j = 1}^n {p_j^2} } - \\ &{{\kern 1pt}{\kern 1pt} \dfrac{1}{2}p_k^2 + ({r_k} + {p_k}){p_k}} \end{split} $$ (8)

                        $ r_k>r_L-p_v $, 因為加權處理時間相同時會選擇處理時間較小的$ Seru $來安排, 那么根據式(7)、式(8), 有:

                        ${\text{再結合}}({p_k} \!\!+\!\! A)/\alpha m \!\!\le\!\! {r_L},{\text{以及}}$${p_v}/{p_k}\!\! \le\!\! {\rm{ }}({\rm{1 \!+\! }}1/m){\rm{/2}}$.最終有:

                        $$ \dfrac{\sigma(I_2^*)}{{\text{π}}(I_2^*)}\leq \max\{\dfrac{\sigma(I_2^*{'})}{{\text{π}}(I_2^*{'})},1+\alpha\} $$

                        通過將$ I_2^*{'} $重寫作$ I_2^* $, 不斷迭代, 可以得到:

                        $$ \dfrac{\sigma(I_2^*)}{{\text{π}}(I_2^*)}\leq \max\{1+\alpha,\frac{5+\sqrt{17}}{4}\} $$

                        $ \alpha \!=\! \dfrac{1+\sqrt{17}}{4} $時, 有最優情況$\dfrac{\sigma(I_2^*)}{{\text{π}}(I_2^*)}\!\leq\! \dfrac{5+\sqrt{17}}{4}$$ \approx2.28 $.

                        引理10.在$ \alpha $AD-I算法下, 對于特殊實例$ I_3^* $, 有:

                        $$ \dfrac{\sigma(I_3^*)}{{\text{π}}(I_3^*)}\leq \dfrac{5+\sqrt{17}}{4} $$

                        證明. $ \sigma(I_3^*) $中, 最后一個子隊列所有$ Seru $的權重趨近于無窮, 同引理6的證明, 將$ \sigma(I_3^*) $中最后一個子隊列中所有Seru的集合記為$ Q_\infty $, 將$ Q_\infty $中所有$ Seru $間最早的訂單任務發布時間記為$ r_f $, 將$ \sigma(I_3^*) $中最后一個SPoint記為$ r_L $.

                        引理10的證明分為了三種情況討論:

                        表 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$的權重無窮大的一類實例

                        1) $ r_L\leq r_f $, 證明同引理6情況1). 可得:

                        $$ \dfrac{\sigma(I_3^*)}{{\text{π}}(I_3^*)}\leq 1+\alpha $$

                        2) $ r_L>r_f $, 且$ \sigma(I_3^*) $中于$ r_L $時刻運作的$ Seru $全部屬于$ Q_\infty $, 證明同引理9, 從$ I_3^* $剔除掉一部分$ Seru $后可得到$ r_L $不為最后一個SPoint的過度實例$ I_3^{*'} $. 可得:

                        $$ \dfrac{\sigma(I_3^*)}{{\text{π}}(I_3^*)}\leq \max\{\dfrac{\sigma(I_3^{*'})}{{\text{π}}(I_3^{*'})},1+\alpha,1.5-\dfrac{1}{2m}+\frac{1}{\alpha}\} $$

                        3) $ r_L>r_f $, 且$ \sigma(I_3) $中于$ r_L $時刻運作的$ Seru $中至少存在一個不屬于$ Q_\infty $, 再分為兩種情況:

                        a)在$ \sigma(I_3) $中, $ Q_\infty $中不存在對應訂單任務于$ r_L $之前發布, 但構建于$ r_L $或之后的$ Seru $. 且所有于$ r_L $或之后構建的$ Seru $所對應的訂單任務也于$ r_L $或之后發布, 從$ I_3 $中剔除這些$ Seru $得到過渡實例$ I_3^{*'} $, 證明同引理6情況3)a. 可得:

                        $$ \begin{split} &\dfrac{\sigma(I_2^*)}{{\text{π}}(I_2^*)}\leq \max\{\dfrac{\sigma(I_2^*{'})}{{\text{π}}(I_2^*{'})}, \dfrac{(r_L+\dfrac{A}{m})B+\dfrac{B^2}{2m}+(1-\dfrac{1}{2m})\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2}{r_L(B-p_k)+\dfrac{(B-p_k)^2}{2m}+\dfrac{1}{2}\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2-\dfrac{1}{2}p_k^2+(r_L-p_v+p_k)p_k}\}= \\ &\quad \max\{\dfrac{\sigma(I_2^*{'})}{{\text{π}}(I_2^*{'})},1+\dfrac{\dfrac{AB}{m}+(\dfrac{1}{2}-\dfrac{1}{2m})\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2+\dfrac{Bp_k}{m}-\dfrac{p_k^2}{2m}-(\dfrac{p_k^2}{2}-p_vp_k)}{r_LB+\dfrac{B^2}{2m}+\dfrac{1}{2}\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2-\dfrac{Bp_k}{m}+\dfrac{p_k^2}{m}+(\dfrac{p_k^2}{2}-p_vp_k)}\} \end{split} $$
                        $$ \dfrac{\sigma(I_3^*)}{{\text{π}}(I_3^*)}\leq \max\{\dfrac{\sigma(I_3^{*'})}{{\text{π}}(I_3^{*'})},1+\alpha\} $$

                        b)在$ \sigma(I_3) $中, $ Q_\infty $中不存在對應訂單任務于$ r_L $之前發布, 但構建于$ r_L $或之后的$ Seru $. 但存在$ Seru\ J_k $$ r_L $之后構建但對應訂單任務于$ r_L $之前發布, 由$ \alpha AD-I $算法有$ J_k\in F $, 從$ I_3^* $中剔除從$ r_L $或之后構建的$ Seru $得到過渡實例$ I_3^{*'} $, 記$ \displaystyle\sum\nolimits_{S_j\geq r_L}^{} $$p_j: = B $. 同引理9的證明, 有:

                        通過迭代, 最終有: $ \dfrac{\sigma(I_3^*)}{{\text{π}}(I_3^*)}\leq \dfrac{5+\sqrt{17}}{4} $.

                        結合引理9和引理10, 對于特殊實例$ I^* $, 有:

                        定理11. 有資源沖突的$ Seru $在線并行調度問題中, 對于實例$ I^* $, $ \alpha $AD-I算法的最優競爭比在$ \alpha = (1+\sqrt{17})/4 $時取得, 為$ (5+\sqrt{17})/4\approx2.28 $.

                      • 本節對特殊實例$ I^* $$ \alpha $AD-I算法的性能進行檢測, 在NAS算法[22]以及O NLINE($ \varepsilon $)算法[23]中加入與$ \alpha $AD-I算法相同的沖突處理機制, 通過計算機實驗比較$ I^* $下三個算法的性能.

                        參考Savelsbergh等[30]以及Gu[31]在論文中采用的方法構建測試用例. 對于不屬于沖突集合$ F $$ Seru $, 訂單任務發布時間按照參數為$ \lambda $的泊松分布隨機生成, $ \lambda $為單位時間內平均發布的訂單任務個數. 對應低、平均、高三種不同的負載, 將$ \lambda $分別取為0.5、1.0和3.0; $ Seru $的處理時間和權重從[1, 100]中隨機生成.

                        對于屬于沖突集合$ F $$ Seru $, 訂單任務發布時間和權重從[1, 100]中隨機生成, 處理時間按照$ I^* $的定義生成, 先構建$ Seru $與后構建$ Seru $完工時間的比值不大于$ (1+1/m)/2 $.

                        再考慮位置數目$ m $, 不屬于$ F $$ Seru $數目$ n_1 $, 以及屬于$ F $$ Seru $數目$ n_2 $之間的不同組合.

                        $ m\in\{2,5,10,20,50\} $,

                        $ n_1\in\{m,2m,4m,50,100,200\} $,

                        $ n_2\in\{2,3,4,5\} $,

                        $ \lambda\in\{0.5,1.0,3.0\} $,

                        $ n_1\geq n_2 $, 則共有312種不同的組合, 每一種負載下有104種組合.

                        按照上述規則, 每組隨機生成1000個測試用例, 定義$ Seru $的處理時間除以$ m $后單機器下最優算法SWPT[19]的目標值為模擬最優解, 計算$ \alpha $AD-I算法、添加沖突處理機制后的NAS以及O NLINE($ \varepsilon $)算法下的目標值與相應模擬最優解的比值, 稱其平均值為模擬競爭比.

                        結果如圖6所示, 縱坐標為模擬競爭比, 橫坐標是不同的組合, 按$ m $、$ n_1 $、$ n_2 $的主次排序依據升序排列.

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

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

                        圖6中可以看出, 對不同的負載, 均有特殊實例$ I^* $$ \alpha $AD-I算法的性能明顯優于添加沖突機制后的NAS算法以及O NLINE($ \varepsilon $)算法. 且在$ m $相同時, 模擬競爭比隨著$ n_1 $、$ n_2 $的增大而減小, 算法性能與$ n_1 $、$ n_2 $呈正相關.

                        除此之外, 橫向對比, 相同負載及相同$ n_1 $、$ n_2 $下, $ m $增大到一定程度時, 再繼續增大, 模擬競爭比不增反減, 算法性能反而提高; 縱向對比, 相同$ m $、$ n_1 $、$ n_2 $下, 負載增大, 模擬競爭比減小, 算法性能提高. 實驗結果說明在特殊實例$ I^* $下, 算法對大規模定制的市場環境具有良好的適應性, 能夠體現SPS的靈活性.

                        $$ \begin{array}{l} \dfrac{\sigma(I_3^*)}{{\text{π}}(I_3^*)}\leq \dfrac{\sigma(I_3^{*'})+\delta((r_L+\dfrac{\displaystyle\sum\nolimits_{S_j<r_L}^{}p_j}{m})B+\dfrac{B^2}{2m}+(1-\dfrac{1}{2m})\displaystyle\sum\nolimits_{S_j>r_L}^{}p_j^2)}{{\text{π}}(I_3^{*'})+\delta(r_L(B-p_k)+\dfrac{(B-p_k)^2}{2m}+\dfrac{1}{2}\displaystyle\sum\nolimits_{j = 1}^{n}p_j^2-\dfrac{1}{2}p_k^2+(r_k+p_k)p_k)}\leq \max\{\dfrac{\sigma(I_3^{*'})}{{\text{π}}(I_3^{*'})},1+\alpha\} \end{array} $$
                      • 本節對一般實例下$ \alpha $AD-I算法的性能進行檢測, 同樣與添加沖突機制后的NAS算法以及O NLINE($ \varepsilon $)算法進行比較.

                        測試用例的生成與上小節類似, 唯一的區別在于, 對屬于沖突集合$ F $$ Seru $, 處理時間從[1, 100]中隨機生成. 同樣對312種不同的組合分別隨機生成1000個測試用例, 計算不同算法在每種組合下的模擬競爭比.

                        圖7中可以看出, 在一般實例下$ \alpha $AD-I算法的性能也優于添加沖突機制后的NAS算法以及O NLINE($ \varepsilon $)算法. 且具有和特殊實例$ I^{*} $下相似的實驗結果. $ m $相同時, 算法性能與$ n_1 $、$ n_2 $呈正相關. 橫向對比, $ m $增大到一定程度再繼續增大, 算法性能反而提高; 縱向對比, 負載增大, 算法性能提高. 實驗結果同樣說明在市場需求大幅度波動的情況下, 算法具有良好的適應性, 能夠體現SPS的靈活性.

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

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

                      • 在分別對特殊實例$ I^* $以及一般實例下$ \alpha $AD-I算法的性能進行檢測后, 再將兩種情況進行對比.

                        圖8中展示了特殊實例$ I^* $與一般實例下$ \alpha $AD-I算法模擬競爭比的對比, 可以看出, 相同負載下, 在$ Seru $的可用位置數目$ m $相同時, 隨著$ n_1 $、$ n_2 $的增大, 一般實例下的模擬競爭比與特殊實例$ I^* $之間的差距不斷縮小直至可以忽略. 且隨著負載的增大, 這種趨勢的進程在不斷加快. 實驗結果從一定程度上驗證了, 在大規模定制的市場環境中, 一般實例下的$ \alpha $AD-I算法同特殊實例$ I^* $下一樣具有良好的性能.

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

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

                      • 根據2.3.3節的討論, 可知具有常數競爭比的$ \alpha $AD-SWPT算法對比AD-SWPT的改進算法不具有競爭比數值上的絕對優勢, 但是隨著$ m $的增大, 二者競爭比間本就細微的差距在不斷減小, 因此在大規模定制的市場環境下這種微乎其微的差距可以忽略不計.

                        本節在一般實例下, 對基于$ \alpha $AD-SWPT算法的$ \alpha $AD-I算法與添加沖突機制后的AD-SWPT的改進算法進行計算機模擬實驗, 測試用例的生成同4.2節.

                        圖9中可以看出, 相同負載下, 在$ m $相同時, 隨著$ n_1 $$ n_2 $的增大, $ \alpha $AD-I算法的模擬競爭比較之添加沖突機制后的AD-SWPT的改進算法, 呈現從略大于到最后幾乎相等的趨勢, 中間甚至有$ \alpha $AD-I算法更加優越的情況出現. 且隨著負載和$ m $的增大, 這種趨勢的進程在不斷加快. $ \lambda = 1 $, $ m = 50 $時, 以及$ \lambda = 3 $, $ m = 20,50 $時, 兩個算法的模擬競爭比曲線幾乎完全重合.

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

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

                        實驗結果表明, 在大規模定制的市場環境下可以忽略$ \alpha $AD-SWPT算法在競爭比數值上的細微差距. 為了推進算法競爭比的計算, 在添加沖突機制時, 選用具有常數競爭比的$ \alpha $AD-SWPT算法是合理的.

                      • 本文針對帶有資源沖突的$ Seru $在線并行調度問題, 以總加權完工時間最小為目標, 決策$ Seru $的構建順序及時間. 先基于并行機在線調度問題的AD-SWPT算法, 針對無資源沖突的情況, 采用實例歸約的方法, 引入調節參數$ \alpha $, 得到競爭比為常數$ (5+\sqrt{17})/4\approx2.28 $$ \alpha $AD-SWPT算法.

                        再針對有資源沖突的情況, 基于$ \alpha $AD-SWPT算法添加沖突處理機制, 得到帶有資源沖突的$ Seru $在線并行調度算法, 即$ \alpha $AD-I算法. 沿用實例歸約的方法, 在特殊實例$ I^* $下可證明其競爭比同$ \alpha $AD-SWPT算法, 也為常數$ (5+\sqrt{17})/4\approx2.28 $.

                        最后通過計算機模擬實驗對$ \alpha $AD-I算法的性能進行檢測, 對比添加沖突機制后的NAS算法與O NLINE($ \varepsilon $)算法, $ \alpha $AD-I算法在特殊實例$ I^* $與一般實例下均具有更好的性能. 且在市場需求大幅度波動的情況下, 算法具有良好的適應性, 能夠發揮SPS靈活的特點. 且有, 在大規模定制的市場環境中, 一般實例與特殊實例$ I^* $下的$ \alpha $AD-I算法均具有良好的性能.

                    WeChat 關注分享

                    返回頂部

                    目錄

                      /

                      返回文章
                      返回