假设我有 n 个工作和 m 台机器。这些作业具有优先约束（在有向无环图中给出）和不同的执行时间。时间表不能是抢先的。安排它们的最佳算法是什么？有什么建议么？我知道这通常是 NP 难的，所以启发式也可以。我会考虑这里给出的 Hu Level Scheduling http://web.cecs.pdx.edu/~mperkows/temp/0002.scheduling2.pdf 但如果我理解正确，它假定执行时间相同。
问问题
125 次
2 回答
1
我会建议一个贪婪的启发式。
假设您的工作有一个execution_time和一个孩子。让叶子工作和其他工作dependency_time成为可能。execution_timeexecution_time + max(dependency_time for children)
在每一步，安排最大的可用作业dependency_time。
于 2019-09-03T16:27:19.300 回答
0
解决方案示例
欧洲航天局乔托卫星使用它飞入深空：哈雷彗星。
由教授开创。CAR HoareALT为解决并发问题提供了一种新的、确定性的（除非存在外部事件/刺激）调度。
基于π-演算驱动的调度，π-代数解决了给定 DAG 依赖关系的N-jobs 对M-resources 的依赖关系，并允许可变的作业持续时间和进程间通信（使用分离作业的开创性技术，保持它们成对-如果需要，与廉价、快速和专用的 CSP 通道互连，以仍然确定性和调度的非破坏性方式交换信息）。
::: 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... __
这 main()使用了 DAG 定义的依赖关系示例，用于~ 21具有可变持续时间的-jobs并在线运行：
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() ------------------------------------------------------------
该代码可在线运行，可用于任何真实[PARALLEL]系统设计的实验——唯一遗憾的是，InMOS Transputers 被其平台的 x86-CPU 内核所取代，其“更狂野”部分的功能受到限制PAR。
享受对 π 演算驱动调度的进一步破解：
#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() ------------------------------------------------------------
信用：感谢@bazza提醒这个令人难忘的 Occam-pi 太空任务。
于 2019-09-04T15:25:01.520 回答