200816063 七、指定代表圖： (一） 本案指定代表圖為：第（二）圖。 (二） 本代表圖之元件符號簡單說明： S21〜S29 :流程步驟。 八、 本案若有化學式時，請揭示最能顯示發明特徵的化學 式: 九、 發明說明： 【發明所屬之技術領域】 本發明係提供一種相依排程之派工方法，特別是關於 由共識因子獲得新世代母體，由求解出演化後之排程序 列，以縮短任務排程完成的時程。 【先前技術】 隨著電子資訊科技的快速發展，各種電子資訊產品如 個人電腦、筆記型電腦、伺服器或工作站等裝置或系統， 其功能不但愈來愈強大，相較於以往，其價格亦更加的平 易近人。因此，無論是擁有成千上萬員工的大企業或是其 他員工人數較少之中小業，均相繼將電子資訊裝置或系統 200816063 t其企業之營運及管理流程中，其中可包括諸如透過電 =料研發、電子文件或樓案之傳送與簽核、企举資 敫，之辅助製造、自動化之產品測試以:企 管理等。透過上述之電子資訊裝置或系統 及其理之：ί:供企業更有效率的執行設計、生產、製造 及官理之作業流程。 h.、任務之間具有相依關係（dependent aticnshxp), ,Ma M f ^ # ^ ## ^ 田以（irected acyclic graph，DAG) 〇 旦右H閱第Γ圖’係為任務排程之有向非循環圖。圖中， ::㈣:=(task)’任務間有㈣ 二二％ “要任務排程6與任務排程^都執行完畢， 方此執仃’當任務排程6需要任務排程6執行 方处 執行^當任務排程4要任務排^執行完畢，方能執^ 第二、任務的執行具有共用資源的特性，即此 戶 源是有限數量的機器，每個任務都可用任 P而上述任務排程問題可發生在各種領域，如研發專案 排私、生產系統排程、計算機系統排程。 x ^ =,排程序列的演化-般是以基因演算法，利用交 「二子、(c聰over operator)和突變因子一ati〇n operator)來產生新染色體的排程序列。 孜 限制的相依性，交配因子和突變因子可能產生兩^問題： 6 200816063 (1)易產生不合理解；（2)產生品質不佳的解。 因此’為解決上述所提出的問題。本發明人基於多年 k事研究與諸多貫務經驗，經多方研究設計與專題探討， 遂於本發明提出一種相依排程之派工方法以作為前述期望 一實現方式與依據。 ' 【發明内容】 有鐘於上述課題，本發明之目的為提供—種相依者m 求寺別是關於由共識因子獲得新世代母體，E 化後之排程序列，簡短任務排程完成的時程 法，提二土f目的’依本發明之相依排程之派工; 個處=備=具有相依性的複數個㈣ 對產生一處理時：，排私及處理設備的酉 及傳輪時間產生你敦姑 專輸蚪間，再由處理時間矩㈣ 任務排程之—排除之各別優先值，依據優先值排歹^ 生多個該排程序歹^，歹卜且由處理時間矩陣及傳輸時間J 樣自母體之排程]^成母體，I續，由共識因子將拍 藉由共識因子重德的斜仃’貝化，以產生新世代母體，同樣 直到新產生_、世新母產生㈣世代母體抽樣進行演 即停止演化，最後，體相演化服或演化代數， 識固子使得具有:::月之相依排程之派工方法中的共 組的任務排程經此產生品質優排程序 200816063 列’以縮短任務排程完成的時程。 茲為使貴審查委員對本發明之枯# # 功效有更進-步之瞭解與認識，下=特徵及所達成之 及相關圖式以為齡之用，並叫=供較佳之實施例 如後。 之呢明文字配合說明 【實施方式】 為讓本發明之上述目的、特徵 下文依本發明之相依排程之派卫方;^能更明顯易懂， 配合所附相關式’作詳細說明 =μ實施例’並 以相同的元件符號加以說明。’’、中相同的元件將 請參閱第二圖，係為本發明松 流程圖。此方法之流程步驟如後：&排程之派工方法之 步驟S21 :提供複數個任務排 任務排程具有相依性； 壬，邠份或全部前述 步驟S22 :提供複數個處理設備，處理前述任務排程； 理時= 排程及處理設備的配對產生-處 拂程由處理時間矩陣及傳輸時間’產 列^ S25 : _優先_列前述任務排程之-排程序 ’由處理時間_及傳輪時間產生乡侧轉列，以形 200816063 成一母體； 、雜Y驟S26 :經由母體產生至少一共識因子，將抽樣自 母脰之排程序列進行演化，以產生一新世代母體； ^驟S27 :經由新世代母體產生共識因子，對新產生 的新世代母體抽樣進行演化，並重複演化，直到新產生的 新世代母體達到一演化門檻或一演化代數，即停止演化； 步驟S28:由所獲得最終的新世代母體求解出一演化 後之排程序列；以及 /、 步驟S29 ··將所獲得的演化後之排程序列投入於任務 排程的執行。 上述之處理設備一般可為電腦設備或生產設備等，而 處理設備可具有不同的處理能力，傳輸時間為具相依性的 任務排程的中間產物於處理設備間的傳遞所花費的時間， 且共識因子至少包含有一經演化後該排程序列中固定不變 的優先關係、一經演化後談排程序列中產生新的優先關係 或一共識因子權重等。 請參閱第三圖，係為本發明之任務排程及處理設備配 對之處理時間矩陣。此例，提供三個具有不同的處理能力 的處理設備mi、m2及脱，當第一圖中任兩個任務排程指派 給同一個處理設備時，傳輸成本設定為0，代表並不需要 傳輸資料，且設定任兩個處理設備的頻寬使任兩個任務排 程之間的傳輸成本相等於其資料傳輸量，指派給不同處理 設備不會影響傳輸時間。因為是具有不同的處理能力的處 200816063200816063 VII. Designation of representative representatives: (1) The representative representative of the case is: (2). (2) A brief description of the component symbols of this representative figure: S21~S29: Process steps. 8. If there is a chemical formula in this case, please disclose the chemical formula that best shows the characteristics of the invention: IX. Description of the invention: [Technical field of the invention] The present invention provides a method for dispatching related schedules, in particular, obtained by a consensus factor The new generation of the parent, by solving the evolution of the program column, to shorten the time course of the task schedule completion. [Prior Art] With the rapid development of electronic information technology, various electronic information products such as personal computers, notebook computers, servers or workstations are not only more powerful but also more expensive than before. More approachable. Therefore, whether it is a large enterprise with thousands of employees or a small number of other small employees, the electronic information device or system 200816063 will be included in the operation and management process of its enterprise, which may include, for example, Material research and development, electronic documents or building cases transmission and signing, enterprise funds, auxiliary manufacturing, automated product testing to: enterprise management. Through the above-mentioned electronic information device or system and its rationale: ί: for the company to more efficiently carry out the design, production, manufacturing and official operations. h., the relationship between the tasks (dependent aticnshxp), , Ma M f ^ # ^ ## ^ ir ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( Acyclic graph. In the figure, ::(4):=(task)' There are (4) 22% between tasks. “To schedule the task 6 and the task schedule ^ are executed, and then execute the task schedule 6 when the task schedule 6 needs to be executed. Execution at the party ^ When the task schedule 4 is completed, the task can be executed. Second, the execution of the task has the characteristics of shared resources, that is, the household source is a limited number of machines, and each task can be used as P. The above task scheduling problems can occur in various fields, such as R&D project smuggling, production system scheduling, and computer system scheduling. x ^ =, the evolution of the program column is generally a gene algorithm, using the "two sons, ( c Cong over operator) and the mutation factor-ati〇n operator) to generate a new chromosome sequence. 孜Restricted dependence, mating factors and mutation factors may produce two problems: 6 200816063 (1) easy to produce misunderstanding; (2) Producing a solution with poor quality. Therefore, in order to solve the above-mentioned problems, the inventors have based on many years of research and many experience of management, and have studied and designed by special parties, and proposed a dependent row according to the present invention. Cheng Zhi’s method of dispatching As a result of the foregoing implementation and the basis of the present invention, the present invention aims to provide a dependent person to obtain a new generation of mothers by a consensus factor. Column, the time-course method of short task scheduling completion, the two-funded purpose of the invention according to the present invention; the location = preparation = a plurality of dependencies (four) for the generation of a treatment:, smuggling And the processing equipment's 酉 and transit time will generate your Dingku special transmission, and then the processing time moment (4) task scheduling - exclude the respective priority value, according to the priority value 歹 ^ generate more than one of the program 歹 ^ , and by the processing time matrix and the transmission time J sample from the mother's schedule] ^ into the mother, I continue, by the consensus factor will be taken by the consensus factor of the weight of the slant 'bee, to produce a new generation of the mother, Similarly, until the new generation _, the world new mother produces (four) generations of the mother sample to stop the evolution, and finally, the body evolution service or evolution algebra, the knowledge of the solid makes the::: month of the corresponding scheduling method Group task scheduling produces quality Schedule 200816063 column 'to shorten the time schedule of task scheduling completion. In order to make your reviewer have a more advanced understanding and understanding of the efficacy of the invention, the following = characteristics and the achieved and related schemas For the purpose of ageing, and for the preferred embodiment, for example, the following is a description of the present invention. In order to make the above objects and features of the present invention, the following is based on the invention of the invention; It is easy to understand, and the related formula 'detailed description = μ embodiment' is described with the same component symbol. '', the same component will be referred to the second figure, which is the flow chart of the invention. The process steps are as follows: & the scheduling method of the scheduling method S21: providing a plurality of task scheduling tasks having dependencies; 壬, 邠 or all of the foregoing steps S22: providing a plurality of processing devices to process the foregoing task row Process; Timing = scheduling and processing device pairing generation - process by processing time matrix and transmission time 'production column ^ S25: _ priority_column of the aforementioned task scheduling - row program' by processing time _ and transfer Time Generate a township side transition to form a parent body in the form of 200816063; and a mixture of Y and S26: generate at least one consensus factor through the mother, and evolve the sample from the rank of the mother to produce a new generation of mothers; ^S27: via The new generation of maternal generation of consensus factors, the evolution of the new generation of new generation maternal samples, and repeated evolution until the newly generated new generation of mothers reaches an evolution threshold or an evolutionary algebra, that is, stop evolution; Step S28: the final The new generation of the parent solves an evolved program sequence; and /, step S29 · · puts the obtained evolved program into the execution of the task schedule. The processing device described above may generally be a computer device or a production device, and the processing device may have different processing capabilities, and the transmission time is the time taken for the intermediate product of the dependent task scheduling to be transmitted between the processing devices, and the consensus The factor includes at least one of the fixed priority relationships in the queue after evolution, and a new priority relationship or a consensus factor weight in the queue after evolution. Please refer to the third figure, which is the processing time matrix of the task scheduling and processing equipment pairing of the present invention. In this example, three processing devices mi, m2 and off with different processing capabilities are provided. When any two task schedules in the first figure are assigned to the same processing device, the transmission cost is set to 0, indicating that transmission is not required. The data, and the bandwidth of any two processing devices is set such that the transmission cost between any two task schedules is equal to the data transmission amount, and assignment to different processing devices does not affect the transmission time. Because it is a place with different processing capabilities 200816063
理設備，同一任務排程在不同處理設備的期望執行時間 (expected execution time)會不同；再者任務排程不能再 拆解，亦即設每一個任務排程只能指派給一部處理設備執 行。其中，任務排程ti於處理設備mi、in2及脱執行的處理 時間分別為2、3及1 ;任務排程仪於處理設備mi、胞及 ms執行的處理時間分別為3、4及5;任務排程t3於處理設 備m、in2及ms執行的處理時間分別為3、2及2 ;任務排程 t4於處理設備mi、m2及1〇3執行的處理時間分別為3、1及2; 任務排程t5於處理設備mi、m2及ms執行的處理時間分別為 3、3及3，任務排程t6於處理設備mi、in2及ms執行的處理 時間分別為1、2及3。 由處理時間矩陣及傳輸時間，產生任務排程之各別優 先值，首先，產生b-ievei，為每一任務排程到最後一個 任務排程的最長路徑長度，因此每個任務排程的關鍵路徑 被相依性所限制，因此越前面的任務排程所需的路徑越 長，其b-level通常較高。每個任務排程的b-levei ^算 為在各處理設備的平均處理時間加上與最長（1〇n狀紂）的 子任務排程（child task)的b-level和傳輸時間。再者， ^每個任務排程的卜leve卜此可以觸任務排程的最 早開始時間。卜1evel的計算為父任務排程（parent task、 &Γ1和父任務的傳輸時間加上父任務排務的平均處 經上述計算，請參㈣四圖係為本發 派工方法一優弁佶夕而丨± ^ 1欠无值之列表。因此，依據此表產生一妯 列’首先’依據b-level姐中★ + + avei排出匕、匕、心、6、&及七 200816063 參照t-level調整優先序， 優先於以Μ憂先於f 由卜levei中得知順序中& 列為/另5又優先於匕。故，獲得排程序 L2 L5 t3：8L t4。 列中固定不變的優先關係成= 新的優先關係或一共識因子權口 ==程序列中產生The same task schedule will be different in the expected execution time of different processing devices; in addition, the task schedule can not be disassembled, that is, each task schedule can only be assigned to one processing device to perform . The processing time of the task scheduling ti in the processing device mi, in2, and off execution is 2, 3, and 1 respectively; the processing time of the task scheduler in the processing device mi, cell, and ms is 3, 4, and 5, respectively; The processing time of the task scheduling t3 performed by the processing devices m, in2, and ms is 3, 2, and 2, respectively; the processing time of the task scheduling t4 performed by the processing devices mi, m2, and 1〇3 is 3, 1, and 2, respectively; The processing time of the task scheduling t5 performed by the processing devices mi, m2, and ms is 3, 3, and 3, respectively, and the processing time of the task scheduling t6 performed by the processing devices mi, in2, and ms is 1, 2, and 3, respectively. The processing time matrix and transmission time are used to generate the respective priority values of the task scheduling. First, b-ievei is generated, and the longest path length for each task scheduling to the last task scheduling is performed, so the key of each task scheduling is Paths are limited by dependencies, so the longer the path required for the previous task schedule, the higher the b-level is. The b-levei^ of each task schedule is calculated as the b-level and transmission time of the longest (1〇n 纣) subtask task at the average processing time of each processing device. Furthermore, ^ each task schedule can be touched at the earliest start time of the task schedule. Bue 1evel's calculation is the parent task schedule (parent task, & Γ 1 and the parent task's transmission time plus the average of the parent task scheduling through the above calculations, please refer to (four) four maps for this method of sending a job佶夕而丨± ^ 1 owes no value to the list. Therefore, according to this table, a list of 'first' is based on b-level sister + + avei discharge 匕, 匕, heart, 6, & and seven 200816063 The t-level adjusts the priority order, which takes precedence over the fact that the order is in the levei and the column is / another 5 and takes precedence over 匕. Therefore, the program L2 L5 t3:8L t4 is obtained. The constant priority relationship becomes = new priority relationship or a consensus factor weight == generated in the program column
進行演化，以產生新世代母體，同樣I =產Ϊ:新世，達到演化==:停 序列，夢的新世代母體求解出演化後之排程 糾縮短任務排程完成的時程。 變的優先關i識因=為—、_化後該排程序列中固定不 子權重等，請參閱第五圖所顯示本發= 5日 生方去之流程圖，其流程步驟如後： “ 建立i:隹巧’自欲演化之母體隨機抽取多個排程序列， 定之/門=^所抽取個數較料母體半數紐用者所設 S52 · 4异共識集合中所有排程序列各自的優先 =係矩陣，意即產生與排程序列對應之複數個優先關係矩 口步驟S521 :提供一零矩陣及單一個排程序列，依排 王列中任兩個任務排程的先後順序以決定所對應的矩陣 11 200816063 元為0或1 ’以產生前述之優先_矩陣； 步驟S53 .加總所有優先關係矩陣，形成一對偶優先 矩陣； 步驟S54:標準化上述之對偶優先矩陣，其中演化後 為0或1之矩陣tl於演化前即為0或i者，兩任務排程即 固定不變的優先關係，演化後為G或1之矩陣元於演化 前不為0或1者’兩任務排程即為新產生的優先關係；以 及Evolution is carried out to produce a new generation of maternal, the same I = calving: the new world, reaching evolution ==: stop sequence, the dream of the new generation of the mother to solve the evolution of the schedule to correct the time schedule of the completion of the task schedule. Change the priority of the knowledge of i = cause -, after the _ after the row of the fixed column weights, etc., please refer to the flow chart shown in the fifth figure = 5 days to go to the flow chart, the process steps are as follows: Establish i: 隹巧's self-desired evolution of the parent body randomly extracts a number of rows of program, the number of / gate = ^ the number of the number of the parent is set to be more than half of the parent set S52 · 4 different consensus set of all the rows of the program Priority = system matrix, that is, generating a plurality of priority relationship moments corresponding to the row of the program step S521: providing a zero matrix and a single row of program columns, according to the order of any two task schedules in the row of kings to determine the corresponding The matrix 11 200816063 element is 0 or 1 ' to generate the aforementioned priority_matrix; step S53. Add all the priority relationship matrices to form a pair of even priority matrices; Step S54: normalize the above dual priority matrix, where the evolution is 0 or The matrix tl of 1 is 0 or i before evolution, and the two task schedules are fixed priority relationships. The matrix elements of G or 1 after evolution are not 0 or 1 before the evolution. a new priority relationship; and
步驟S55 .依據可插入的任務排程間的對偶優先矩陣 的比例’產生共識因子權重’用以調整排程序列。 不』因子則包括為經演化後該排程序列中固定 係或共顧子權重。 排㈣列中產生新的優先關 綜上所述，本發明之減轉 子嶋有相依性的任務排程經此產生品^， 以縮短任務排程完成的時程。 、炎王 以上所述僅為舉例性，而非卜 本發明之精神與範疇，而對其進行者。任何未用 應包含於後社申請專·圍中。之4效修改或變更， 【圖式簡單說明】 第-圖係為任務排程之有向非循環圖 12 200816063 第二圖係為本發明之相依排程之派工方法之流程圖； 第三圖係為本發明之任務排程及處理設備配對之處理時 間矩陣； 第四圖係為本發明之相依排程之派工方法一優先值之列 表，以及 第五圖係為本發明之共識因子的產生方法之流程圖。 •【主要元件符號說明】 匕、66及6 :任務排程； S21〜S29 :流程步驟； mi、m2及m3 :處理設備；以及 S51〜S55及S521 :流程步驟。 13Step S55. A consensus factor weight is generated according to the ratio of the dual priority matrix between the insertable task schedules to adjust the queue. The non-factor is included as the fixed or shared sub-weight in the row of programs after evolution. A new priority is generated in the row (four) column. In summary, the dependent task schedule of the present invention is generated by the task schedule to shorten the time course of the task schedule completion.炎王 The above description is for illustrative purposes only, and not for the spirit and scope of the invention. Any unused use should be included in the post-society application. 4 effect modification or change, [Simple description of the diagram] The first diagram is the directed acyclic of the task schedule. Figure 12 200816063 The second diagram is a flow chart of the method of dispatching the dependent schedule of the present invention; The figure is a processing time matrix of the task scheduling and processing device pairing of the present invention; the fourth figure is a list of priority values of the dispatching method of the dependent scheduling of the present invention, and the fifth figure is the consensus factor of the present invention. A flow chart of the method of production. • [Main component symbol description] 匕, 66 and 6: task scheduling; S21~S29: process steps; mi, m2 and m3: processing equipment; and S51~S55 and S521: process steps. 13