1313437 . 七、指定代表圖·· (一） 本案指定代表圖為：第（二）圖。 (二） 本代表圖之元件符號簡單說明： S21〜S29 :流程步驟。1313437 . 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.
八、本案若有化學式時，請揭示最能顯示發明特徵的化學 式： 九、發明說明： 【發明所屬之技術領域】 本發明係提供一種相依排程之派工方法，特別是關於 由共識因子獲得新世代母體，由求解出演化後之排程序 列，以縮短任務排程完成的時程。 【先前技術】 隨著電子資訊科技的快速發展，各種電子資訊產品如 個人電腦、筆記型電腦、伺服器或工作站等裝置或系統， 其功能不但愈來愈強大，相較於以往，其價格亦更加的平 易近人。因此，無論是擁有成千上萬員工的大企業或是其 他員工人數較少之中小業，均相繼將電子資訊裝置或系統 5 1313437 • 4人其企業之營運及管理流程中，其中可包括諸如透過電 腦輔助設計研發、電子文件或檔案之傳送與簽核、企業資 料之管理、生產線之辅助製造、自動化之產品測試以及企 業資源之整合與管理等。透過上述之電子資訊裝置或系统 之辅助，得以提供企業更有效率的執行設計、生產、製造 • 及管理之作業流程。 "°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 to which the invention pertains] The present invention provides a method for dispatching related schedules, particularly regarding obtaining by consensus factors 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 tens of thousands of employees or a small number of other small employees, the electronic information device or system will be included in the operation and management process of the enterprise, which may include Through computer-aided design and development, transmission and signing of electronic documents or files, management of enterprise data, auxiliary manufacturing of production lines, product testing of automation, and integration and management of enterprise resources. Through the assistance of the above-mentioned electronic information devices or systems, it is possible to provide enterprises with more efficient execution of design, production, manufacturing, and management operations. "°
然而’在有限資源的情況下，各種任務排程問題具有 下列二個特性：第-、任務之間具有相依關係（㈣⑽的 relationship)，此相依關係通常可用一個有向非循環圖來 描述（directed acyclic graph, DAG)。 請參閱第-圖，係為任務排程之有向非循環圖。圖中， 具有6個任務排程（task)，任務間有執行财上的限制， 當任務排程的要任務排程6與任務排程6都執行完畢， 方能執行，當任務排程h需要任務軸6執行完畢，方能 執行’當絲擁“要歸齡㈣行完畢，方能執行。 ，即該些任務 可用任一部機 第二、任務的執行具有共用資源的特性 所有的資源是有限數量的機器，每個任務都 器加工。 而上述任務排程問題可發生在各種領域，如研發專案 排程、生產系統排程、計算機系統排程。 習知之排程序韻演化-般是以基因料法，利用交 配運算子（crossover operator)和突變因子（mutati〇n operator)來產生新染色體的排程序列。因為任務有順序 限制的相依性，交配因子和突變因子可能產生兩個問題： ⑴易產生不合理解；⑵產生品質不佳的解。 從事：tit:所提出的問題。本發明人基於多年 遂於本發明提出多方研究設計與專題探討， ―實現方式與依據。目、&之派工方法以作為前述期望 【發明内容】 % 之派:二:上，本發明之目的為提供一種相依排; 求解出演化後之挪：：由共識因子獲得新世代母體，〗 θ 、王序列以縮短任務排程完成的時程 法’ s部::本發;之相依排程之派工; 個處理設備處理你^目又性的複數個任務排程及複! 對產生—處理時 Μ呈’經由任騎程及處理設備的g 及傳輪時間產生:t陣及一傳輸時間’再由處理時間矩碎 任務排程之-排海務排程之各別優先值，依據優先值排歹However, in the case of limited resources, various task scheduling problems have the following two characteristics: first, and the dependencies between tasks ((4) (10) relationship). This dependency relationship can usually be described by a directed acyclic graph (directed Acyclic graph, DAG). See the figure - for a directed acyclic graph of the task schedule. In the figure, there are 6 task schedules, and there are financial restrictions between tasks. When the task schedule 6 and task schedule 6 of the task schedule are executed, the task schedule can be executed. It is required that the execution of the task axis 6 is completed before the execution of the "When the silk" is completed (4), and the execution can be performed. That is, the tasks can be performed by any of the second machines, and the execution of the tasks has the characteristics of the shared resources. It is a limited number of machines, each of which is processed. The above task scheduling problems can occur in various fields, such as R&D project scheduling, production system scheduling, and computer system scheduling. Using the gene surrogate method, using the crossover operator and the mutatix operator to generate a new chromosome sequence. Because the task has sequential dependence, the mating factor and the mutation factor may cause two problems. (1) It is easy to produce misunderstanding; (2) Produce a poor quality solution. Engaged in: tit: The problem raised. The inventor has proposed multi-party research design and design based on the invention for many years. Discussion, ―Implementation and basis. The method of dispatching and arranging as the above-mentioned expectation [invention]%: On: The purpose of the present invention is to provide a dependent row; The new generation maternal is obtained by the consensus factor, 〗 θ, Wang sequence to shorten the task schedule to complete the time-course method 's Department:: this hair; the scheduling of the corresponding scheduling; the processing equipment to handle your complex and multiplicity Task scheduling and recovery! For production-processing, it is generated by g and the transmission time of the riding and processing equipment: t-array and one transmission time, and then the processing time is broken. Each priority value of the process, based on the priority value
生多個該排㈣序列’且由處理時間矩陣及傳輸時間J 樣自母體之排丄，以形成母體，接續，由共識因子將抽 藉由共識行演化，以絲世代母體，同樣 化’直到新產複的對新產生的新世代母體抽樣進行演 即停止演化，2新世代母料冑化代數， 拼程序列，難,、4 ’由最終的新世代母體求解出演化後之 曰乂縮短任務排程完成的時程。 承上所述 識因子使彳f 因依本發明之相依触之派^法中的共 、相依性的任務排程經此產生品質優排程序 1313437 列’以縮短任務排程完成的時程。 ^使㈣查委員對本發明之技術特徵及所達成之 功效有更進-步之瞭解與認識，下文謹提供較佳之實施例 j關圖式以為辅佐之用，独詳細之說敎字配合說明 如後。 【實施方式】 為讓本發明之上述目的、騎ϋ 下文依本發明之相⑽程之派工方祕，易十重’ 配合所附相關圖式，作詳細㈣"特^ 土實施例，並 以相同的元件符號加以說明。 ’、中相同的件將 請參閱第二圖，係為本發明之相依排程之派 流程圖。此方法之流程步驟如後： 法之 步驟S21:提供複數個任務排程， 任務排程具有相依性； 丨忉^王4刚遑 步驟S22 :提供複數個處理設備，處理前述任務排程； 步驟S23 :經由任務排程及處理設備的配對產生 理時間矩陣及一傳輸時間； 處 步驟S24:經由處理時間矩陣及傳輪 排程之各別優先值； i生任務 排程序 列’以形 步驟S25 :依據優先值排列前述任務排程之一 列’由處理時間矩陣及傳輸時間產生多個排程序 1313437 成一母體； 步驟S26 :經由母體產生至少一共識因子，將抽樣自 母體之排程序列進行演化’以產生一新世代母體； 步驟S27 :經由新世代母體產生共識因子，對新產生 的新世代母體抽樣進行演化，並重複演化，直到新產生的 新世代母體達到一演化門檻或一演化代數，即停止演化； 步驟S28:由所獲得最終的新世代母體求解出—演化 後之排程序列；以及 步驟S29 :將所獲得的演化後之排程序列投入於任務 排程的執行。 上述之處理設備一般可為電腦設備或生產設備等，而 處理設備可具有不同的處理能力，傳輸時間為具相依性的 任務排程的中間產物於處理設備間的傳遞所花費的時間， 且共識因子至少包含有一經演化後該排程序列中固定不變 的優先關係、一經演化後該排程序列中產生新的優先關係 或一共識因子權重等。 請參閱第三圖，減本發明之任務排程及處理設備配 對之處理時間矩陣。此例’提供三個具有不同的處理能力 的處理設備πυ、ra3 ’當第—圖中任兩個任務排程指派 給同二個處理設備時，傳輸成本設定為〇，代表並不需要 傳輪貝料，且設定任兩做理設備的頻寬使任兩個任務排 程之間的傳輸成本相等於其資料傳輪量，指派给不同處理 设備不會影響傳輸時間。因為是具有不同的處理能力的處 1313437A plurality of the row (four) sequences are generated and are processed from the matrix by the processing time matrix and the transmission time J to form the matrix, and the continuation is performed by the consensus factor, and the evolution is performed by the consensus line to the same generation. The new production of the new generation of new generation maternal sampling will stop the evolution, 2 new generation masterbatch deuterated algebra, spelling the program, difficult, 4 'from the final new generation of the mother to solve the evolution after the shortening The time course in which the task schedule is completed. According to the above-mentioned knowledge factor, the task scheduling of the common and dependent processes in the method according to the present invention generates a quality scheduling program 1313437 column to shorten the time course of the task scheduling completion. ^ (4) The Commissioner has a more in-depth understanding and understanding of the technical features of the present invention and the achieved effects. The following is a preferred example of the diagram j for the purpose of assistance, and the detailed description of the wording is as follows: Rear. [Embodiment] In order to make the above object of the present invention, ride on the following (10) process of the invention, Yi Shizhong's accompanying related drawings, detailed (four) " special soil embodiment, and The same component symbols are used for explanation. The same components will be referred to the second figure, which is a flowchart of the dependent scheduling of the present invention. The process steps of the method are as follows: Step S21 of the method: providing a plurality of task schedules, and the task schedules have dependencies; 丨忉^王王刚遑Step S22: providing a plurality of processing devices to process the foregoing task schedule; S23: generating a rational time matrix and a transmission time through the pairing of the task scheduling and the processing device; at step S24: respectively, by using the processing time matrix and the respective priority values of the routing schedule; i generating the task scheduling column 'to the shape step S25 : arranging one of the foregoing task schedules according to the priority value 'generating a plurality of scheduling programs 1313437 into a parent by the processing time matrix and the transmission time; Step S26: generating at least one consensus factor via the parent, and performing sampling from the parent row of the program column' To generate a new generation of maternal bodies; Step S27: to generate a consensus factor through the new generation of maternal, to evolve the new generation of new generation maternal samples, and repeat the evolution until the newly generated new generation maternal reaches an evolution threshold or an evolutionary algebra, ie Stop the evolution; Step S28: Solve the final new generation matrix obtained by the obtained - the evolved program column; S29: After the evolution obtained scheduling sequence input to perform tasks scheduled. 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 fixed priority relationship 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 to reduce the processing time matrix of the invention and the processing time matrix of the processing equipment. In this example, 'three processing units with different processing capabilities are provided πυ, ra3'. When any two task schedules in the first graph are assigned to the same processing device, the transmission cost is set to 〇, which means that there is no need for a transfer. The material is set, and the bandwidth of any two processing devices is set so that the transmission cost between any two task schedules is equal to the data transmission amount, and the assignment to different processing devices does not affect the transmission time. Because it is a place with different processing power 1313437
理設備’同一任務排程在不同處理设備的期望執行時間 (expected execution time)會不同；再者任務排程不能再 拆解，亦即設每一個任務排程只能指派給一部處理設備執 行。其中，任務排程11於處理設備mi、in2及m3執行的處理 時間分別為2、3及1 ;任務排程t2於處理設備mi、此及 ms執行的處理時間分別為3、4及5 ;任務排程t3於處理設 備nu、Hi2及脱執行的處理時間分別為3、2及2 ;任務排程 t4於處理設備mi、m2及ms執行的處理時間分別為3、1及2 ; 任務排程ts於處理設備mi、Π12及ms執行的處理時間分別為 3、3及3 ;任矛务排程Ϊ6於處理設備m!、m2及m3執行的處理 時間分別為1、2及3。 由處理時間矩陣及傳輸時間，產生任務排程之各別優 先值，首先，產生b-level，為每一任務排程到最後—個 任務排程的最長路徑長度，因此每個任務排程的關鍵路徑 被相依性所限制，因此越前面的任務排程所需的路徑越 長’其b-level通常較高。每個任務排程的b_level計算 為在各處理設備的平均處理時間加上與最長（1〇ngest)的 子任務排程（chiId task)的b-level和傳輸時間。再者， 計算每個任務排程的t-level ’此可以判斷任務排程的最 早開始時間。t-level的計算為父任務排程（parent仏故) 的t-level和父任務的傳輸時間加上父任務排務的平均處 理時間。 經上述δ十异，晴參閱第四圖係為本發明之相依排程之 派工方法一優先值之列表。因此，依據此 列，首先，依據b，vel排出Β、&丄 1313437 - 參照Hevel調整優先順序，由t_level中得知順序中广 優先於心；6優先於6又優先於匕。故，獲得排程序 歹'[麵 tl、te、t2、t5、t3 反 t4。 承上，遂由各任務排程對應處理設備的處理時間之區 , 間，產生多個排程序列形成母體。由一經演化後該排程二 . 列中固定不變的優先關係、一經演化後該排程序列中產生 新的優先關係或一共識因子權重等作為共識因子，將抽樣 自母體之排程序列進行演化，以產生新世代母體，同樣摔 ^ 由共識因子重複的對新產生的新世代母體抽樣進行演化^ 直到新產生的新世代母體達到演化門檻或演化代數，即停 止演化，最後，由最終的新世代母體求解出演化後之排程 序列，藉以縮短任務排程完成的時程。 緣是’共識因子可為一經演化後該排程序列中固定不 變的優先關係、一經演化後該排程序列中產生新的優先關 係或一共識因子權重等’請參閱第五圖所顯示本發明之共 識因子的產生方法之流程圖，其流程步驟如後： 步驟S51 :自欲演化之母體隨機抽取多個排程序列， 建立共識集合，所抽取個數較佳為母體半數或使用者所設 定之門檻個數； 步驟S52 :計算共識集合中所有排程序列各自的優先 - 關係矩陣’意即產生與排程序列對應之複數個優先關係矩 陣； 步驟S521 :提供一零矩陣及單一個排程序列’依據排 程序列中任兩個任務排程的先後順序以決定所對應的矩陣 11 1313437 -元為0或1 ’以產生前述之優先關係矩陣； 步驟S53 :加總所有優先關係矩陣，形成—對偶優先 矩陣； 步驟S54 :標準化上述之對偶優先矩陣，其中演化後 為0或1之矩陣元於演化前即為〇或1者，兩任務排程<即 具固定不變的優先關係，凟化後為0或1之矩陣元於演化 前不為0或1者，兩任務排程即為新產生的優先關係；以 及 b 步驟S55 :依據可插入的任務排程間的對偶優先矩陣 的比例，虞生共識因子權重，用以調整排程序列。 其中，衿識因子則包括為經演化後該排程序列中固定 不變的優先關係、經演化後邊排程序列中產生新的優先關 係或共識因子權重。 綜上所述’本發明之相依排程之派工方法中的共識因 子使得具有相依性的任務排程經此產生品質優排程序列， .以縮短任務排程完成的時程。 以上所述僅為舉例性，而非為限制性者。任何未脫離 本發明之精神與範疇，而對其進行之等效修改或變更，均 應包含於後附之申請專利範圍中。 【圖式簡單説明】 第一圖係為任務排程之有向非循環圖； 12 1313437 第二圖係為本發明之相依排程之派工方法之流程圖； 第三圖係為本發明之任務排程及處理設備配對之處理時 間矩陣； 第四圖係為本發明之相依排程之派工方法一優先值之列 表；以及 第五圖係為本發明之共識因子的產生方法之流程圖。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. carried out. The processing time of the task scheduling 11 in the processing devices mi, in2, and m3 is 2, 3, and 1 respectively; the processing time of the task scheduling t2 in the processing device mi, and the ms is 3, 4, and 5, respectively; The processing time of the task scheduling t3 in the processing devices nu, Hi2, and off-execution is 3, 2, and 2, respectively; the processing time of the task scheduling t4 in the processing devices mi, m2, and ms is 3, 1, and 2, respectively; The processing time for the processing devices mi, Π12, and ms is 3, 3, and 3, respectively; the processing time for the spear scheduling Ϊ6 at the processing devices m!, m2, and m3 is 1, 2, and 3, respectively. The processing time matrix and the transmission time are used to generate the respective priority values of the task scheduling. First, the b-level is generated, and the longest path length is scheduled for each task to the last task scheduling, so each task scheduling is performed. Critical paths are limited by dependencies, so the longer the path required for the previous task schedule, the higher the b-level is. The b_level of each task schedule is calculated as the b-level and transmission time of the longest (1〇ngest) sub-hid task (chiId task) at the average processing time of each processing device. Furthermore, calculating the t-level of each task schedule can determine the earliest start time of the task schedule. The t-level is calculated as the t-level of the parent task schedule (parent) and the transmission time of the parent task plus the average processing time of the parent task schedule. The above-mentioned δ is different, and the fourth drawing is a list of the priority values of the dispatching method of the dependent scheduling of the present invention. Therefore, according to this column, first, according to b, vel, &, & 1313437 - refer to Hevel to adjust the priority order, from t_level to know that the order has priority over the heart; 6 takes precedence over 6 and takes precedence over 匕. Therefore, the program is obtained 歹'[face tl, te, t2, t5, t3 inverse t4. In the above, between the processing time of each processing task corresponding to the processing device, a plurality of rows are generated to form a parent. After the evolution, the fixed priority relationship in the second column of the schedule, after the evolution, the new priority relationship or the weight of the consensus factor is generated as a consensus factor, and the sample is sampled from the parent row. Evolve to produce a new generation of maternal bodies, and also to evolve from a new generation of new generation maternal samples by consensus factors until the newly generated new generation maternal reaches the evolution threshold or evolution algebra, that is, ceases to evolve, and finally, by the final The new generation of mothers solves the evolved program sequence to shorten the time course of task scheduling completion. The reason is that the 'consensus factor can be a fixed priority relationship in the queue after evolution, and a new priority relationship or a consensus factor weight is generated in the queue after evolution. Please refer to the figure shown in the fifth figure. A flow chart of a method for generating a consensus factor of the invention, the process steps are as follows: Step S51: randomly extracting a plurality of rows of program columns from the parent to be evolved, and establishing a consensus set, the number of which is preferably the parent half or the user Step S52: calculating respective priority-relationship matrices of all the queues in the consensus set means to generate a plurality of priority relationship matrices corresponding to the row of program blocks; Step S521: providing a zero matrix and a single row The program column 'determines the corresponding matrix 11 1313437 - the element is 0 or 1 ' according to the order of the two task schedules in the queue column to generate the foregoing priority relationship matrix; Step S53: sum all the priority relationship matrices, Forming a dual priority matrix; Step S54: normalizing the above dual priority matrix, wherein the matrix element after evolution of 0 or 1 is 〇 or 1 before evolution , the two task schedules < has a fixed priority relationship, the matrix element of 0 or 1 after deuteration is not 0 or 1 before the evolution, the two task schedule is the newly generated priority relationship; and b Step S55: A consensus factor weight is generated according to the ratio of the dual priority matrix between the insertable task schedules, and is used to adjust the queue. Among them, the ignorance factor includes a fixed priority relationship in the queue after evolution, and a new priority relationship or consensus factor weight is generated in the evolved side-by-side program column. In summary, the consensus factor in the dispatching method of the dependent scheduling of the present invention enables the dependent task schedule to generate a quality scheduling program to shorten the time course of the task scheduling completion. The above is intended to be illustrative only and not limiting. Any equivalent modifications or alterations to the spirit and scope of the present invention are intended to be included in the scope of the appended claims. [Simple diagram of the diagram] The first diagram is a directed acyclic diagram of the task schedule; 12 1313437 The second diagram is a flowchart of the method for dispatching the dependent schedule of the present invention; the third diagram is the invention The processing time matrix of the task scheduling and processing device pairing; 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 a flow chart of the method for generating the consensus factor of the present invention .
【主要元件符號說明】 △、&、&、匕、匕及匕··任務排程； S21〜S29 :流程步驟； mi、m2及m3 :處理設備；以及 S51〜S55及S521 :流程步驟。[Description of main component symbols] △, &, &, 匕, 匕, and 匕··Task scheduling; S21~S29: process steps; mi, m2, and m3: processing equipment; and S51~S55 and S521: process steps .
1313