US 9,804,591 B2 · Job scheduler for electromechanical system for biological analyses

Abstract

A method and system for scheduling a plurality of concurrent job sequences with constraints of precedence and mutual exclusion is described. In particular, a scheduler for a system performing biological analyzes on clinical samples including non-preemptible jobs which must use a set of resources (machines) and having constraints on release times and execution times is described. The scheduling method uses on-purpose algorithmic solution that extracts the core of DBM data structures and Floyd-Warshall algorithm from the engine of a full-fledged Model Checking tool and tailors it to the specific requirements of the case.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims14

Dependent claims

A scheduling method of a processor-controlled system including a plurality of machines and at least one processor, configured to be stored in the system and adapted to execute, via the at least one processor, a plurality of non-preemptible electromechanically driven jobs J1 . . . Jn, with deterministic execution times e1 . . . en, each job of the plurality of non-preemptible electromechanically driven jobs being statically assigned to one of m independent machines M1 . . . Mm of the plurality of machines, for setting a release time r1 . . . rn for each job J1 . . . Jn so as to minimize a completion time of overall set of jobs, while respecting precedence constraints comprising:

for a predetermined set of pairs Jx and Jy of the plurality of jobs, a delay between completion of Jy and start of Jx range within a minimum delay d−xy and a maximum delay d+xy:
d−xy≦rx−(ry+ey)≦d+xy
and respecting exclusion constraints comprising:
for a predetermined set of pairs Ji and Jk of the plurality of jobs, one of two determinations of exclusion constraint is fulfilled, the two determinations being:
ri≧rk+ek OR ri+ei≦rk
so that execution periods of Jk and Ji do not overlap,
the method comprising the steps, executed on the one or more processors, of:
A) building a frontier set including a plurality of Difference Bound Matrix (DBM) zones that collect release times satisfying the precedence constraints;
B) selecting one of the plurality of DBM zones and removing it from the frontier set;
C) responsive to the selected DBM zone not satisfying at least one exclusion constraint of one pair Ji and Jk of the predetermined set of pairs, building one restricted zone of the selected DBM zone per each of the two determinations resolving a conflict defined by (ri≧rk+ek or ri+ei≦rk);
D) checking if the restricted DBM zones are non-empty and adding the non-empty restricted DBM zones to the frontier set;
and
E) repeating the steps B to D until a selected DBM zone satisfies all the exclusion constraints.

10 more elements

Dependencies are inferred from the claim text.

Description6,240 words

Summary2,542 words

#The present application is the US national stage of International Patent Application PCT/EP2012/075468 filed on Dec. 13, 2012 which, in turn, claims priority to European Patent Application EP 11196275.9 filed on Dec. 30, 2011.

#The present invention relates to a method and system for scheduling a plurality of concurrent sequences of timed jobs that are subject to constraints of mutual exclusion and mutual delay. In particular, the present invention relates to a scheduler for a system that performs multiple concurrent biological analyses that apply different analysis protocols on different samples while sharing a set of electromechanical devices.

#While the problem of scheduling a plurality of concurrent and timed job sequences with constraints of mutual delay and mutual exclusion with allowed bounded time slacks can be applied to a large variety of contexts, in the present application, without loss of generality, we address the problem with reference to a concrete example of a run-time scheduler for an electromechanical system for biological analyses, such as for example the VIDAS system engineered by bioMérieux

Brief description of the drawings6 figures

#Reference will now be made, by way of example, to the accompanying drawings, in which:

#FIG. 1 is a schematic representation of the physical architecture of system components running a single analysis in an electromechanical apparatus for performing biological tests;

#FIG. 2 is a schematic representation, of the physical architecture of the overall system composing multiple analyses in slots and sections in an electromechanical apparatus for performing biological tests according to an embodiment of the present invention;

Detailed description3,461 words

#To the purposes of the subsequent treatment, we introduce here the main concepts on which the scheduling solution relies: Difference Bound Matrices (DBMs) and Floyd-Warshall algorithm.

#A DBM encodes a system of inequalities identifying a set of solutions for a vector of N variables r=t1 . . . tN

#D = { τ i - τ j ≤ b ij i , j ∈ [ 1 ⁢ ⁢ … ⁢ ⁢ N ] ⋃ * , b ij ∈ ℚ τ * = 0 □

Facts

Application

14/364,455Filed 13 Dec 2012

Priority

EP 1119627530 Dec 2011

Published

US 2014/0303766 A19 Oct 2014

Granted

31 Oct 2017

Term ends

5 Oct 2034

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 661 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification5 codes

G05B 19/41865
Total factory control, i.e. centrally controlling a plurality of machines, e.g. direct or distributed numerical control [DNC], flexible…:…
G06F 9/4881
By program, e.g. task dispatcher, supervisor, operating system: scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
G06F 9/4887
Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues: involving deadlines, e.g. rate based, periodic
G05B
Control or regulating systems in general

Timeline

30 Dec 2011Priority claimedEP 11196275
13 Dec 2012Application filedUS 14/364,455
5 Aug 2014Assigned to Biomerieuxassignment of assignor's interest
11 Aug 2014Assigned to Biomerieuxcorrective assignment to correct the spelling of assignee city previously recorded at reel: 033465 frame: 0182. assignor(s) hereby confirms the assignment.
9 Oct 2014PublishedUS 2014/0303766 A1
31 Oct 2017GrantedUS 9,804,591 B2
12 Oct 2026TodayWithin its term
5 Oct 2034Term endsEstimated, includes 661 days of adjustment

Job scheduler for electromechanical system for biological analyses

Life of this patent

Job scheduler for electromechanical system for biological analyses

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims14

Description6,240 words

Drawings

Classification5 codes

Life of this patent

Description6,240 words