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

有效

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

技術領域

本發明涉及用于調度受限于互斥約束和互相延遲約束的設定時間的作業的多個并行序列的方法和系統。具體地說，本發明涉及用于執行多個并行生物學分析的系統的調度程序，所述并行生物學分析對不同的樣本應用不同的分析協議，同時共享一組機電設備。

背景技術

盡管調度具有互相延遲約束和互斥約束的具有允許的有限空余時間的多個并行且設定時間的作業序列的問題可以適用于各種各樣的背景，但是在本發明中，我們參考用于生物學分析的機電系統的運行時的調度程序的具體實例來討論該問題，而不失一般性，例如，所述機電系統諸如由bioMérieux設計的VIDAS系統。

本實例的系統能夠運行多個并行分析的組、每個并行分析都交替樣本的生物學反應的步驟和由共享的機電設備執行的傳送操作的步驟；每個反應步驟的持續時間是由該分析的生物學協議(protocol)確定的，但是在每個反應步驟完成之后，可以增加有限等待時間。

這引起了在每個步驟之后確定等待時間，以便符合最大允許延遲并且避免在共享資源的使用中的沖突，同時最大化并行分析的數量并且最小化它們的總完成時間的調度問題。

更詳細地說，每種類型的生物學分析是由預處理階段和分析協議組成的。在分析開始時，樣本被包含在通過條形碼唯一標識的試管中，而其他的管子含有稀釋液和培養液并且其余的管子是空的。在預處理階段，自動取樣器在各個管子之間反復地傾倒樣本；每個取樣器操作持續確定的時間量。在連續的操作之間允許等待時間，但是它們被約束為在由培養期/反應期以及樣本變質特性確定的最小值和最大值之間變化。在預處理階段完成之后，分析協議遵循固定的步驟序列，在這期間，樣本與試劑結合了并且通過其操作花費確定持續時間的讀取頭進行了多個測量(見圖1)。

為了機電組件的有效利用，多個可能為不同類型的分析被并行執行。為此，該系統構成了多個單元，每個單元都用于每個分析。進而，每個單元被分成多個插槽，所述插槽攜帶可以經過不同的預處理并且可以在不同對象的樣本上操作的不同的樣本。然而，由于讀取頭被設計為同時對整個單元進行測量，因此在同一個單元中的所有插槽被約束為運行相同的分析協議(見圖2)。

取樣器和讀取頭在不同的插槽和單元之間共享并且不能被兩種不同的分析同時使用。這引起了必須確定每個預處理的初始延遲以及在相同分析的事件之間的等待時間的可行值的調度問題。這種值必須避免取樣器和讀取頭同時期操作的需求，避免等待時間超過允許的界并且保持盡可能短的分析組的總時間間隔。

問題闡述

該問題可以采用如同獨立且非搶占的n個作業J₁….J_n的組的作業車間的調度的一般概念來正式建模，這n個作業J₁….J_n的組具有釋放時間r₁….r_n以及確定的執行時間e₁….e_n，每個作業被靜態分配到m個獨立的機器M₁….M_m中的一個機器上，這受限于優先約束和互斥約束：

-對于任意兩個作業J_i和J_k，優先約束可能要求在J_k完成和J_i開始之間的延遲在最小量d^-_ik和最大量d⁺_ik內變化：

d^-_ik≤r_i–(r_k+e_k)≤d⁺_ik

-對于任意兩個作業J_i和J_k，互斥約束可能要求J_k和J_i的執行期不重疊；這可以使用以下兩個判定中的任意一個來實現，所述兩個判定保證J_i在J_k完成之后開始，或者保證J_k在J_i完成之后開始：

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