神戸大学 システム情報学研究科 2018年1月実施 第二期 専門科目 システム理論 [1]

标签：

• Kobe-University
• Combinatorial-Optimization
• Shortest-Job-First-Scheduling

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

ある工場で稼働している1台の機械に対して，時刻 $0$ で次の6つのジョブが到着した。処理時間 $p_j$ と納期 $d_j$ は次のとおりである。

ジョブ $j$	1	2	3	4	5	6
処理時間 $p_j$	5	7	6	3	1	8
納期 $d_j$	18	23	17	20	19	22

1. SPT (Shortest Processing Time)，EDD (Earliest Due Date)，MS (Minimum Slack) の各ディスパッチングルールで計画を作り，ガントチャートで示せ。
2. 各スケジュールの総滞留時間 $C_{\mathrm{sum}}$ と最大納期遅れ $L_{\max}$ を求めよ。

题目描述

某工厂的一台机器需要处理在时刻 $0$ 同时到达的 6 个作业，其加工时间 $p_j$ 和交货期 $d_j$ 如上表所示。

1. 分别按 SPT（最短加工时间）、EDD（最早交货期）和 MS（最小松弛量）规则排序，并用甘特图表示。
2. 求每种排程的总滞留时间 $C_{\mathrm{sum}}$ 和最大交货延误 $L_{\max}$。

Kai

完了時刻を $C_j$，納期遅れを

$$L_j=C_j-d_j$$

とする。また，時刻 $t$ における MS のスラックは

$$s_j(t)=d_j-t-p_j$$

である。残っているジョブに対して $-t$ は共通なので，今回の MS 順序は $d_j-p_j$ の昇順で決まる。

(1)

• SPT：$5\to4\to1\to3\to2\to6$
• EDD：$3\to1\to5\to4\to6\to2$
• MS：$d_j-p_j=(13,16,11,17,18,14)$ より $3\to1\to6\to2\to4\to5$

ガントチャート（括弧内は開始時刻と完了時刻）は次のとおりである。

SPT  設備 M : | J5 (0-1) | J4 (1-4) | J1 (4-9) | J3 (9-15) | J2 (15-22) | J6 (22-30) |
EDD  設備 M : | J3 (0-6) | J1 (6-11) | J5 (11-12) | J4 (12-15) | J6 (15-23) | J2 (23-30) |
MS   設備 M : | J3 (0-6) | J1 (6-11) | J6 (11-19) | J2 (19-26) | J4 (26-29) | J5 (29-30) |

(2)

$C_{\mathrm{sum}}=\sum_j C_j$ として，各ジョブの $(C_j,L_j)$ を順番に書くと次のようになる。

規則	ジョブ順	$(C_j)$	$(L_j)$	$C_{\mathrm{sum}}$	$L_{\max}$
SPT	5, 4, 1, 3, 2, 6	1, 4, 9, 15, 22, 30	$-18,-16,-9,-2,-1,8$	$81$	$8$
EDD	3, 1, 5, 4, 6, 2	6, 11, 12, 15, 23, 30	$-11,-7,-7,-5,1,7$	$97$	$7$
MS	3, 1, 6, 2, 4, 5	6, 11, 19, 26, 29, 30	$-11,-7,-3,3,9,11$	$121$	$11$

したがって，

$$\boxed{ \begin{array}{c|cc} &C_{\mathrm{sum}}&L_{\max}\\ \hline \mathrm{SPT}&81&8\\ \mathrm{EDD}&97&7\\ \mathrm{MS}&121&11 \end{array}}$$