用于生物学分析的机电系统的作业调度程序

摘要

本发明涉及用于调度多个具有优先约束和互斥约束的并行作业序列的方法和系统。具体地说，本发明涉及用于对临床样本执行包括非抢占的作业的生物学分析的系统的调度程序，所述非抢占的作业必须使用一组资源(机器)并且具有关于释放时间和执行时间的约束。在现实工业系统中引起了调度问题。原则上，该问题可以被阐述为关于例如时间Petri网或者设定时间的自动机的并行模型的实时模型检验的例子。然而，在预期的运行时嵌入式平台中，该方法不是切实可行的。根据本发明的优选实施方式的调度方法，其利用了从成熟的模型检验工具的引擎提取DBM数据结构和Floyd-Warshall算法的核心的针对目的的算法解决方案，并且对其进行调整以适应该例子的特定要求。允许关于次优解的启发式大大降低了搜索的复杂度，并且通过递增算法改进的方式来容许获得预期的性能要求。

主权项

一种调度方法，其在适合于执行具有确定的执行时间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带满足所有的所述排斥约束。