Let's assume I have n jobs and m machines. The jobs have precedence constraints (given in a directed, acyclic graph) and different execution times. The schedule must NOT be preemptive. What's the best algorithm to schedule them? Any suggestions? I know it's NP-hard in general, so heuristics are also okay. I would consider Hu Level Scheduling as given here http://web.cecs.pdx.edu/~mperkows/temp/0002.scheduling2.pdf but if I understand it right, it assumes equal execution times.
This was used by ESA Giotto Satellite to fly into deep Space: the Halley Comet.
Pioneered by prof. C. A. R. Hoare a new, deterministic (unless external events/stimuli/ALTs present) scheduling was made possible for solving concurrency problems.
Based on a π-calculus driven scheduling, the π-algebra solves dependencies for N-jobs on M-resources given DAG dependencies and permits both variable job-duration and inter-process-communications ( using a pioneered technique of separating jobs, keeping them pair-interconnected with cheap, fast and exclusive-use CSP-channels, if needs exist, to exchange pieces of information in a still deterministic and scheduling non-devastating manner ).
::: occam-pi executed all the N-jobs as per dependencies were specified
::: using pi-calculus algebra for deterministic
::: scheduling N-jobs over a pool of M-resources available
::: w.r.t. all dependencies
:::
job: 1 job duration: 15 timer: 545252301 START.... __
job: 11 job duration: 9 timer: 545252302 START.... __
job: 11 job duration: 9 timer: 545252317 FINISH... __
job: 21 job duration: 8 timer: 545252447 START.... __
job: 21 job duration: 8 timer: 545252489 FINISH... __
job: 20 job duration: 16 timer: 545252447 START.... __
job: 20 job duration: 16 timer: 545252538 FINISH... __
job: 19 job duration: 7 timer: 545252447 START.... __
job: 19 job duration: 7 timer: 545252614 FINISH... __
job: 12 job duration: 9 timer: 545252447 START.... __
job: 12 job duration: 9 timer: 545252659 FINISH... __
job: 13 job duration: 8 timer: 545252682 START.... __
job: 13 job duration: 8 timer: 545252704 FINISH... __
job: 14 job duration: 7 timer: 545252727 START.... __
job: 14 job duration: 7 timer: 545252752 FINISH... __
job: 15 job duration: 6 timer: 545252775 START.... __
job: 15 job duration: 6 timer: 545252798 FINISH... __
job: 16 job duration: 5 timer: 545252819 START.... __
job: 16 job duration: 5 timer: 545252840 FINISH... __
job: 17 job duration: 4 timer: 545252862 START.... __
job: 17 job duration: 4 timer: 545252886 FINISH... __
job: 18 job duration: 9 timer: 545252908 START.... __
job: 18 job duration: 9 timer: 545252930 FINISH... __
job: 8 job duration: 2 timer: 545252301 START.... __
job: 8 job duration: 2 timer: 545252976 FINISH... __
job: 9 job duration: 5 timer: 545252999 START.... __
job: 9 job duration: 5 timer: 545253022 FINISH... __
job: 10 job duration: 31 timer: 545253044 START.... __
job: 10 job duration: 31 timer: 545253093 FINISH... __
job: 1 job duration: 15 timer: 545252416 FINISH... __
job: 5 job duration: 31 timer: 545253142 START.... __
job: 5 job duration: 31 timer: 545253230 FINISH... __
job: 6 job duration: 27 timer: 545253242 START.... __
job: 6 job duration: 27 timer: 545253309 FINISH... __
job: 7 job duration: 11 timer: 545253324 START.... __
job: 7 job duration: 11 timer: 545253347 FINISH... __
job: 4 job duration: 12 timer: 545253141 START.... __
job: 4 job duration: 12 timer: 545253392 FINISH... __
job: 2 job duration: 24 timer: 545253141 START.... __
job: 2 job duration: 24 timer: 545253436 FINISH... __
job: 3 job duration: 6 timer: 545253460 START.... __
job: 3 job duration: 6 timer: 545253482 FINISH... __
This main() used an exemplified case of DAG-defined dependencies for ~ 21-jobs having variable durations and was run on-line:
PROC main(CHAN BYTE keyboard, screen, error)
[25]CHAN messagePROTOCOL mon :
CHAN messagePROTOCOL prn :
PAR -- DAG-root-node-(sorry for naive ASCII-art)-*-*-*-*-* DAG root-node's subtree(s)
-- | | | | |
SysPrintr(screen!, prn?)-------------------------+ | | | |
-- | | | |
SysMonMUX( prn!, mon?)---------------------------+ | | |
-- | | |
SEQ -- ----------------------------------------------: | |
-- | | |
job( 1, 15, mon[ 1]!) --job_1---------------+ | |
-- | | |
PAR ----------------------------------------+-+-+--* | |
-- | | | | |
job( 4, 12, mon[ 4]!) -- job_4---+ | | | |
-- | | | |
SEQ ----------------------------------------: | | |
-- | | | |
job( 2, 24, mon[ 2]!) -- job_2-----+ | | |
job( 3, 6, mon[ 3]!) -- _3---+ | | |
SEQ ------------------------------------------: | |
job( 5, 31, mon[ 5]!) -- job_5-------+ | |
job( 6, 27, mon[ 6]!) -- _6-----+ | |
job( 7, 11, mon[ 7]!) -- _7---+ | |
SEQ ---------------------------------------------------: |
-- | |
job( 8, 2, mon[ 8]!) --job_8-----------------+ |
job( 9, 5, mon[ 9]!) -- job_9------------+ |
job( 10, 31, mon[10]!) -- job_10------+ |
SEQ -----------------------------------------------------:
-- |
job( 11, 9, mon[11]!) --job_11------------------+
PAR ---------------------------------------------------*---*-*-*-*
-- | | | |
job( 21, 8, mon[21]!) -- job_21----------------+ | | |
job( 20, 16, mon[20]!) -- job_20----------------|-+ | |
job( 19, 7, mon[19]!) -- job_19----------------|-|-+ |
SEQ -----------------------------------------------------------:
-- |
job( 12, 9, mon[12]!) -- job_12----------------------+
job( 13, 8, mon[13]!) -- _13-------------------+
job( 14, 7, mon[14]!) -- _14----------------+
job( 15, 6, mon[15]!) -- _15-------------+
job( 16, 5, mon[16]!) -- _16----------+
job( 17, 4, mon[17]!) -- _17-------+
job( 18, 9, mon[18]!) -- _18----+
: -- main() ------------------------------------------------------------
The code is made runnable online for any experimentation with true-[PARALLEL] system designs - the only pity is, that InMOS Transputers got substituted by their platform's x86-CPU-core(s) with restricted powers for "wilder" PAR-sections.
Enjoy any further hacking into π-calculus driven scheduling:
#INCLUDE "course.module" -- #USE "course.lib"
-- +------+--------+----+----------+
-- | jobID|duration|time|aSTRING[] |
-- +---------------+------+--------+----+----------+
-- |messagePROTOCOL| INT; INT; INT; [10]BYTE |
PROTOCOL messagePROTOCOL IS INT; INT; INT; [10]BYTE : -- Error-occ21-.code.tio.occ(7)- array type must have dimension specified
-- +---------------+------+--------+----+----------+
PROC job ( VAL INT id, VAL INT duration, CHAN messagePROTOCOL outP )
INT t : -- declare INT
TIMER aCentralCLOCK : -- declare TIMER
[10]BYTE flag.START : -- declare [10]BYTE
[10]BYTE flag.FINISH: -- declare [10]BYTE
SEQ ------------------------------------------------------------------SEQ:
flag.START := " START...." -- .SET
flag.FINISH := " FINISH..." -- .SET
aCentralCLOCK ? t -- .read ? .SET t from timer at start
outP ! id; duration; t; flag.START -- .outP ! messagePROTOCOL{ id; duration; t; aString }
aCentralCLOCK ? AFTER ( t PLUS duration ) -- .read ? .wait till ( start PLUS duration )
-- ^^^^^
-- |||||
-- |||||
-- +++++------------------------------------------------- <this> emulates a variable <job>-duration
aCentralCLOCK ? t -- .read / .SET t from timer at finish
outP ! id; duration; t; flag.FINISH -- .outP ! messagePROTOCOL{ id; duration; t; aString }
: -- job() -------------------------------------------------------------
PROC SysPrintr(CHAN BYTE outCH, CHAN messagePROTOCOL inCH )
INT iJobID :
INT iDuration:
INT iTimer :
[10]BYTE aString :
WHILE TRUE
SEQ
--GET ? ----------------------------------------------------------
inCH ? iJobID; iDuration; iTimer; aString
--PRINT ---------------------------outCH--------------------------
out.string( " job: ", 5, outCH )
out.int( iJobID, 3, outCH )
out.string( " job duration: ", 20, outCH )
out.int( iDuration, 5, outCH )
out.string( " timer: ", 8, outCH )
out.int( iTimer, 10, outCH )
SEQ i = 0 FOR SIZE aString
outCH ! aString[i]
out.string( "__*n", 4, outCH )
flush( outCH ) -- .flush
: -- SysPrintr() -------------------------------------------------------
PROC SysMonMUX(CHAN messagePROTOCOL out!, []CHAN messagePROTOCOL in?)
INT iJobID :
INT iDuration:
INT iTimer :
[10]BYTE aString :
WHILE TRUE
ALT
in[ 0] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 1] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 2] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 3] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 4] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 5] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 6] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 7] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 8] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[ 9] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[10] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[11] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[12] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[13] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[14] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[15] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[16] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[17] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[18] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[19] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[20] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[21] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
in[22] ? iJobID; iDuration; iTimer; aString
out ! iJobID; iDuration; iTimer; aString
: -- SysMonMUX()--------------------------------------------------------
PROC main(CHAN BYTE keyboard, screen, error)
[25]CHAN messagePROTOCOL mon :
CHAN messagePROTOCOL prn :
PAR -- DAG-root-node ----------------------------*-*-*-*-* DAG root-node's subtree(s)
-- | | | | |
SysPrintr(screen!, prn?)-------------------------+ | | | |
-- | | | |
SysMonMUX( prn!, mon?)---------------------------+ | | |
-- | | |
SEQ -- ----------------------------------------------: | |
-- | | |
job( 1, 15, mon[ 1]!) --job_1---------------+ | |
-- | | |
PAR ----------------------------------------+-+-+--* | |
-- | | | | |
job( 4, 12, mon[ 4]!) -- job_4---+ | | | |
-- | | | |
SEQ ----------------------------------------: | | |
-- | | | |
job( 2, 24, mon[ 2]!) -- job_2-----+ | | |
job( 3, 6, mon[ 3]!) -- _3---+ | | |
SEQ ------------------------------------------: | |
job( 5, 31, mon[ 5]!) -- job_5-------+ | |
job( 6, 27, mon[ 6]!) -- _6-----+ | |
job( 7, 11, mon[ 7]!) -- _7---+ | |
SEQ ---------------------------------------------------* |
-- | |
job( 8, 2, mon[ 8]!) --job_8-----------------+ |
job( 9, 5, mon[ 9]!) -- job_9------------+ |
job( 10, 31, mon[10]!) -- job_10------+ |
SEQ -----------------------------------------------------*
-- |
job( 11, 9, mon[11]!) --job_11------------------+
PAR ---------------------------------------------------*---*-*-*-*
-- | | | |
job( 21, 8, mon[21]!) -- job_21----------------+ | | |
job( 20, 16, mon[20]!) -- job_20----------------|-+ | |
job( 19, 7, mon[19]!) -- job_19----------------|-|-+ |
SEQ -----------------------------------------------------------+
-- |
job( 12, 9, mon[12]!) -- job_12----------------------+
job( 13, 8, mon[13]!) -- _13-------------------+
job( 14, 7, mon[14]!) -- _14----------------+
job( 15, 6, mon[15]!) -- _15-------------+
job( 16, 5, mon[16]!) -- _16----------+
job( 17, 4, mon[17]!) -- _17-------+
job( 18, 9, mon[18]!) -- _18----+
: -- main() ------------------------------------------------------------
Credit : credit goes to @bazza for reminding of this memorable Occam-pi space mission.