[發明專利]用于生物學分析的機電系統的作業調度程序

有效

• 申請號: 201280065420.7
• 申請日: 2012-12-13
• 公開（公告）號: CN104081352B
• 公開（公告）日: 2017-09-22
• 發明（設計）人: 恩里科·維卡里奧;洛倫佐·理迪;安德里亞·卡里尼亞諾;雅格布·特瑞妮
• 申請（專利權）人: 生物梅里埃公司
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 北京安信方達知識產權代理有限公司11262
• 代理人: 王思琪,鄭霞

1.一種調度方法，其在適合于執行具有確定的執行時間e₁….e_n的多個非搶占的作業J₁….J_n，且每個作業被靜態分配到m個獨立的機器M₁….M_m中的一個機器上的系統中，以便確定關于每個作業J₁….J_n的釋放時間r₁….r_n，目的是最小化整個作業集的完成時間，同時遵循以下優先約束：

-對于所述多個非搶占的作業的預先確定的對J_x和J_y的集合，在J_y完成和J_x開始之間的延遲在最小延遲d^-_xy和最大延遲d⁺_xy范圍內：

d^-_xy≤r_x–(r_y+e_y)≤d⁺_xy

以及遵循以下排斥約束：

-對于所述多個非搶占的作業的預先確定的對J_i和J_k的集合，滿足排斥約束的以下兩個判定中的一個：

r_i≥r_k+e_k或者r_i+e_i≤r_k

使得J_k和J_i的執行期不重疊，所述方法包含以下步驟：

-A)建立包括了收集滿足所述優先約束的釋放時間的差分界矩陣DBM帶的邊界集；

-B)選擇所述DBM帶中的一個并且將其從所述邊界集移除；

-C)響應于所選擇的DBM帶不滿足所預先確定的對集合中的一對J_i和J_k的至少一個排斥約束，根據解決沖突的兩個判定r_i≥r_k+e_k和r_i+e_i≤r_k中的每個判定，建立所選擇的DBM帶的一個限制帶；

-D)檢查被限制的DBM帶是否是非空的，并且將非空的被限制的DBM帶添加到所述邊界集；

-E)重復所述步驟B)到D)，直到被選擇的DBM帶滿足所有的所述排斥約束。

2.如權利要求1所述的調度方法，其中，執行所述重復步驟，直到所述邊界集中的所有DBM帶都滿足所有的所述排斥約束。

3.如權利要求2所述的調度方法，其中，所述重復步驟在達到了預先確定的最大搜索時間時停止。

4.如權利要求1-3中任一項所述的調度方法，其還包括：

-在所有的滿足所有的排斥約束的DBM帶內選擇最優調度。

5.如權利要求1-3中任一項所述的調度方法，其中，步驟B是依據啟發式估計來執行的。

6.如權利要求5所述的調度方法，其中，所述啟發式包括估計所選擇的滿足所有排斥約束的DBM帶的性能的最長間隔的安全的啟發式。

7.如權利要求5所述的調度方法，其中，所述啟發式包括估計所選擇的最小化總完成時間的DBM帶的性能的最短間隔的貪婪的啟發式。

8.如權利要求6所述的調度方法，其中，所述啟發式包括估計所選擇的最小化總完成時間的DBM帶的性能的最短間隔的貪婪的啟發式。

9.如權利要求1-3和6-8中任一項所述的調度方法，其中，在步驟C的執行中，使用將復雜度從O(n³)降低到O(n²)的Floyd-Warshall算法的優化版本，通過避免重新計算沒有被限制影響的DBM系數，導出了限制帶的標準形，其中n是作業的數量。

10.如權利要求1-3和6-8中任一項所述的調度方法，其中，為了限制算法的時間復雜度以及所利用的數據結構的空間占用，實施代碼優化。