带时限的作业排序问题

《算法分析与设计》实验报告
姓名：
学号：
问题解析（对问题的分析、解题思路与解题方法）：
对当前正在考虑的作业，按限期大小采用一种“插入排序”的方式，尝试将其“插入”到一个按限期从小到大顺序构造的作业调度序列中，以此判断是否能够合并到当前部分解J中。如果可以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。
r--;
if(d[J[r]] <= d[i] && d[i]>r)
{
for(int j=k; j>r; j--)
J[j+1] = J[j];
J[r+1] = i;
k++;
}
}
return k;
}
fjs算法：
int FJS(int *D,int n,int b,int *J,int *Q)
{
int i,*F,*P,j,I,m,k;
具体如下:假设n个作业已经按照效益值从大到小的次序,即p1>=p2...>=pn的顺序排列好，每个作业可以在单位时间内完成，并具有相应的时间期限;且至少有一个单位时间可以执行作业：
首先，将作业1存入部分解J中，此时J是可行的;
然后，依次考虑作业2到n。假设已经处理了i-1个作业，其中有K个作业计入了部分解J中：J(1),J(2),...,J(K),且有
if(F[j]!=0)
{
k=k+1;
J[k]=i;
Q[F[j]]=i;
m=F[j];
I=FIND(P,F[j]-1);
UNION(P,I,j);
F[j]=F[I];
}
}
return k;//返回最优解的个数
}

⑥ 选择作业 1，则 X 6, 2,3,5,1 。将其按照期限 di 非减次序排列可
得：
ID
di
5
1
6
2
3
3
1
3
2
4
作业5
作业3 作业2
-1
0
1
2
3
4
作业6 作业1（冲突）
该集合无可行排序，因此 X 6, 2,3,5,1 不可行， X 6, 2,3,5 ；
3
⑦ 选择作业 0，则 X 6, 2,3,5, 0 。将其按照期限 di 非减次序排列
可得：
ID
di
5
1
0
1
6
2
3
3
2
4
作业5
作业3 作业2
-1
0
1
2
3
4
作业0（冲突）作业6
该集合无可行排序，因此 X 6, 2,3,5, 0 不可行，X 6, 2,3,5 ；
⑧ 选择作业 4，则 X 6, 2,3,5, 4 。将其按照期限 di 非减次序排列
可得：
ID
Hale Waihona Puke di516
12,5,8,32, 7,5,18, 26, 4,3,11,10, 6 。请给出最优存储方案。
解析：首先将这 13 个程序按照程序长度非降序排列，得：
程序 ID
9 8 1 5 12 4 2 11 10 0 6 7 3
程序长度 ai 3 4 5 5 6 7 8 10 11 12 18 26 32
根据定理可知，按照程序编号存放方案如下：
解析：已知 Prim 算法时间复杂度为 O n2 ，受顶点 n 影响；
Kruskal 算法时间复杂度为 O m logm ，受边数 m 影响；

Ｏｐ ＝ ， ｕｒ ｃ，０ １ ｔｅ 巧 １ 。ｔｅ ｊ ２ ＝ ， ｒ Ｉ ｔｅ ∑ Ｉ Ｉ ｐ ｅ ∑ ， ｌ
ｊ ｌ ＝ ｊ ＝ｌ
Ｏ ｊ １ ｍＰ ＝ ， １ ｉ
０ｐ ＝ １ Ｉ Ｉ ∑
ｊ ＝１
可以看 出，这些结论大都是在单位加工时 间的假设条件下得 到的。本文将 在一般 情形下研究 问
基金项目：国家 自然科学基金重大国际 （ 地区） 合作研究 （０３ １０１） ７７ １６ ０５；江苏省教育厅 （ ６３ ） 江苏省 “ ｙ ０７ ｗ０ 青
篮 ”工 程 ．
第４ 期
陈荣军，唐国春 ：使带权总完工时间为最小的 自由作业排序 问题
６１ ３
均极小 ＮＰ困难 ；而下面几个 问题为极大 多项式 时间可解 ，即这些 问题本身是多项式时间可解 的，但略微一般 的情况都不是多项式时间可解 的【６。 ４】 —
ｊ ＝１
其 中 ， Ｍｉ 别 表 示 工 件 歹 Ｃ 分 和 的 完 工 时 间 ，ｗ ， ｊ ＷＭｉ 工 件 和 机 器 的 权 ，Ｊ 示 工 为 表
件，ｉ 表示机器。 与 自由作业相关 的大部分 问题 是 Ｎ Ｐ困难 的，只有少数情形是 多项式时 间可解 的 。当机器 数为两 台时 ，Ａｃｕ ｂ ｅ Ｃ ｉ［ 证 明 ｈ ｇ ｕ ｈｎ ］ 。
总完 工 时 间 为最 小 的 两类 问题 ，本 文 用 组 合方 法 或 者 数 学规 划 方 法 分 别给 出 了稠 密 时 间表 的算 法 或 者 置 换排 序 的算 法 ， 并分 析 算 法 的 性 能 比 。此 方法 在 理 论 和应 用 两 方 面 都 是 有 意义 的 。
关键词：排序 ； 自由作业 ；带权总完工时间；性能 比
题ｏ ｌ ｎ ｊ 的多项式时间近似算法。另外，在 日 ａ 一 ｒ Ｉ Ｗ 常生活中，人们也常常希望机器尽早 ∑

时限调度算法给出的调度顺序时限调度算法是一种常用的任务调度算法，它主要用于在有限的时间内，合理地安排多个任务的执行顺序，以提高系统的效率和性能。

本文将介绍时限调度算法的基本原理和常见的调度顺序。

一、先来了先服务（FCFS）调度顺序先来了先服务（First-Come-First-Served）调度顺序是最简单的一种调度算法，它按照任务到达的先后顺序进行调度。

当一个任务到达后，系统就立即执行它，直到任务结束或发生阻塞。

这种调度顺序的优点是简单易实现，但缺点是无法根据任务的重要程度和紧急程度进行优先级调度，容易导致低优先级任务长时间等待。

二、最短作业优先（SJF）调度顺序最短作业优先（Shortest-Job-First）调度顺序是根据任务的执行时间长度进行调度的算法。

当多个任务同时到达时，系统会选择执行时间最短的任务先执行。

这种调度顺序的优点是能够最大程度地减少平均等待时间，提高系统的响应速度。

然而，它也存在着一定的缺点，即可能导致长任务的饥饿问题，即长任务可能一直等待短任务执行完毕而得不到执行。

三、优先级调度顺序优先级调度顺序是根据任务的重要程度和紧急程度进行调度的一种算法。

每个任务都有一个优先级，优先级越高的任务越先执行。

这种调度顺序能够根据任务的紧急程度进行调度，保证重要任务得到及时处理。

然而，它也存在着可能导致低优先级任务长时间等待的问题，因此需要合理设置任务的优先级。

四、时间片轮转（RR）调度顺序时间片轮转（Round-Robin）调度顺序是一种基于时间片的调度算法，它将每个任务分配一个固定长度的时间片，当一个任务的时间片用完后，系统会将其放入等待队列，并执行下一个任务。

这种调度顺序能够公平地分配系统资源，避免某个任务长时间占用资源，但也可能导致任务的响应时间较长。

五、最早截止时间优先（EDF）调度顺序最早截止时间优先（Earliest-Deadline-First）调度顺序是根据任务的截止时间进行调度的一种算法。

两类带时限的作业排序问题第1题带时限的作业排序问题问题描述：设有⼀个单机系统、⽆其它资源限制且每个作业运⾏相等时间，不妨假定每个作业运⾏ 1 个单位时间。

现有 n 个作业，每个作业都有⼀个截⽌期限di>0，di 为整数。

如果作业能够在截⽌期限之内完成，可获得 pi>0 的收益。

问题要求得到⼀种作业调度⽅案，该⽅案给出作业的⼀个⼦集和该作业⼦集的⼀种排列，使得若按照这种排列次序调度作业运⾏，该⼦集中的每个作业都能如期完成，并且能够获得最⼤收益。

输⼊：第⼀⾏输⼊ n 的值，以下 n ⾏输⼊作业号 i，收益 pi，截⽌期限 di。

输出：n 个作业的⼀个最优⼦集。

⽰例：输⼊:41 100 22 10 13 15 24 27 11 4输出: 0 0 1 1第2题带时限的作业排序问题II问题描述：带时限的作业排序问题可描述为：设有 n 个作业和⼀台处理机，每个作业所需的处理时间、要求的时限和收益可⽤三元组（pi, di, ti），0<=i<n 表⽰，其中，作业 i 的所需时间为 ti，如果作业 i 能够在时限 di 内完成，将可收益 pi，求使得总收益最⼤的作业⼦集 J。

输⼊：第⼀⾏输⼊ n 的值；第⼆⾏输⼊ pi；第三⾏输⼊ di；第四⾏输⼊ ti （i=0，…，n-1 且作业已经按时限⾮减次序排列）。

输出：xi（⽤固定长度 n-元组 xi 表⽰，xi=0 或 1，i=0，…，n-1）。

⽰例：输⼊:45 36 101 12 31 1 1 2输出: 0 0 1 1第1题思路分析这题的思路⽐较明显，就是每次都选取作业收益最⼤的，并把它放在允许的最⼤的截⽌时间内完成，符合贪⼼算法的基本思想。

将输⼊的每个作业按收益从⼤到⼩进⾏排序，⽤⼀个数组vis表⽰某时刻是否已经有作业正在运⾏，vis[i]=1，表⽰时间i被占⽤。

然后从第1个作业开始往后搜索，将该作业安排到vis[d]时间运⾏，如果d已经有安排，将从d-1开始往前搜索，直到找到⼀个未被占⽤的时间点。

带时间延迟的极小化总完工时间的单机排序问题胡觉亮;王焕男;蒋义伟【摘要】研究工件带有两道工序的单台机排序问题.在该问题中,工件的第一道工序先于第二道工序加工,并且第二道工序的开工时间与第一道工序的完工时间至少间隔一定的延迟时间,目标是极小化所有工件的总完工时间.文章考虑所有工件相同且两道工序的加工时间均为单位时间的情形.通过引入k-连续加工的概念和分析最优解的性质,根据延迟时间的大小,分别设计了两个算法并证明了算法所得的排序为最优排序.【期刊名称】《浙江理工大学学报》【年(卷),期】2014(031)001【总页数】5页(P83-87)【关键词】单台机;时间延迟;总完工时间;算法设计与分析;最优排序【作者】胡觉亮;王焕男;蒋义伟【作者单位】浙江理工大学理学院,杭州310018;浙江理工大学理学院,杭州310018;浙江理工大学理学院,杭州310018【正文语种】中文【中图分类】O233本文主要研究带延迟时间的单机排序问题。

每个工件Jj有两道工序aj和bj，第一道工序先于第二道工序加工，第一道工序的完工时间与第二道工序的开工时间之间至少存在lj个单位时间延迟，也就是说第二道工序至少等待lj个单位时间才能开工。

此类问题在一些产品制造工艺流程、布匹印染和服装订单的生产中有重要的应用背景。

对于带有延迟的排序问题，主要分为两类，一类是工件Jj前后两道工序的延迟时间恰好为lj，本文称之为精确延迟排序；另一类是两道工序间的延迟时间至少为lj，称之为至少延迟排序。

关于精确延迟的排序问题，Orman等［1］证明了单台机的一些特殊情况是多项式可解的，并证明即便所有工序的加工时间相同，该问题还是强NP-难的。

Leung等［2］利用贪婪算法研究延迟非增的情形，给出了问题F2｜，aj=a，bj=b，a≥b｜∑Cj的最优排序，并对问题F2｜，aj=a，bj=b，a＜b｜∑Cj给出了一个2-近似算法。

Ageev等［3］分别研究了单台机和两台流水作业机器问题的一些近似算法。

带有限期的作业排序问题的描述：带有期限的作业排序要解决的是操作系统中单机、无资源约束且每个作业可在等量的时间内完成的作业调度问题。

把这个问题形式化描述为：①要在一台机器上处理n个作业，每个作业可以在单位时间内完成②每个作业i都有一个期限值d i，d i>0③当作业在它规定的期限值前完成，就可以获得的效益p i，p i>0问题求解的目标是：问题的可行解是这n个作业的一个子集合J。

J中的每个作业都能在各自的截止期限前完成后，产生一个作业效益之和。

我们的目标就是找到一个子集J，J中的每个作业都能在各自的截止期限前完成，并且使得作业效益值的和最大。

这个作业的一个子集合J就是所求的最优解。

带有期限的作业排序的一个例子：例3.2 n=4，(p1,p2,p3,p4)=(100,10,15,20)，(d1,d2,d3,d4)=(2,1,2,1)。

这个问题的最优解为第7个，所允许的处理顺序是：先处理作业4，在处理作业1。

在时间0开始处理作业4而在时间2完成对作业1的处理。

可行解处理顺序效益值1 {1} 1 1002 {2} 2 103 {3} 3 154 {4} 4 205 {1，2} 2，1 1106 {1，3} 1，3或3，1 1157 {1，4} 4，1 1208 {2，3} 2，3 259 {3，4} 4，3 35带有期限的作业排序贪心算法度量标准的选取：我们的目标是作业效益值的和最大，因此首先把目标函数作为度量标准。

首先把作业按照它们的效益值作一个非增次序的排序。

以例3.2来说，作业根据效益值排序后为作业1、4、3、2。

求解时首先把作业1计入J，由于作业1的期限值是2，所以J={1}是一个可行解。

接下来计入作业4。

由于作业4的期限值是1而作业1的期限值是2，可以先完成作业4后再完成作业1，所以J={1, 4}是一个可行的解。

然后考虑作业3，但是作业3的期限值是2，计入J后就没有办法保证J中的每一个作业都在期限值内完成，因此计入作业3后不能构成一个可行解。

贪⼼法-带有限期的作业排序问题描述–假定在⼀台机器上处理n个作业，每个作业均可在单位时间内完成；同时每个作业i都有⼀个截⾄期限di>0,当且仅当作业i在其截⾄期限以前被完成时，则获得pi>0的效益。

–问题：求这n个作业的⼀个⼦集J，其中的所有作业都可在其截⾄期限内完成。

——J是问题的⼀个可⾏解。

–可⾏解J中的所有作业的效益之和是 i<j∑Pi，具有最⼤效益值的可⾏解是该问题的最优解。

⽬标函数：–约束条件：所有的作业都应在其期限之前完成–分析如果所有的作业期限“⾜够宽松” ，⽽使得多有作业都能在其期限之内完成，则显然可以获得当前最⼤效益值；否则，将有作业⽆法完成——决策应该执⾏哪些作业，以获得最⼤可能的效益值。

n=4，(p1，p2，p3，p4)＝(100,10,15,20)和(d1，d2，d3，d4)＝(2,1,2,1)。

可⾏解如下表所⽰：问题的最优解是⑦。

所允许的处理次序是：先处理作业4再处理作业1。

量度标准：下⼀个要计⼊的作业将是使得在满⾜所产⽣的J是⼀个可⾏解的限制条件下让得到最⼤增加的作业。

处理规则：按pi的⾮增次序来考虑这些作业。

procedure JS(D,J,n,k)//D(1),…,D(n)是期限值。

n≥1。

作业已按p1≥p2≥…≥pn的顺序排序。

J(i)是最优解中的第i个作业，1≤i≤k。

终⽌时， D(J(i))≤D(J(i＋1))， 1≤i＜k//integer D(0:n),J(0:n), i, k, n, rD(0)←J(0)←0 //初始化//k←1;J(1)←1 //计⼊作业1//for i←2 to n do //按p的⾮增次序考虑作业。

找i的位置并检查插⼊的可⾏性//r←kwhile D(J(r))＞D(i) and D(J(r)) ≠r do r←r-1 repeatif D(J(r))≤D(i) and D(i)＞r then //把i插⼊到J中//for i←k to r+1 by -1 doJ(i+1) ←J(i) //将插⼊点的作业后移⼀位//repeatJ(r+1) ←i;k←k+1endifrepeatend JS#include <iostream>using namespace std;/*D(1),…,D(n)是期限值。

平均流程时间：
F
1 n
n i 1
Fi
235
/5
47
3、EDD-SPT 综合原则
例: 在一台设备上安排6个工件的加工任务， 每项任务的作业时间和交货期如下表所示。
J1
J2
J3
J4
J5
J6
作业时间
3
2
4
8
6
5
交货期 6
要求
3
10
20
28
30
在满足Tmax最小的情况下，使平均流程时间最 小。
1、首先使用EDD规则排序
来自上游工 作地的订单
工件排队 等待加工
工作地
加工完毕的订单流向 下一工作地
第二节 制造业作业排序
作业排序（Sequencing）——对一 定期间内分配给生产单位的作业任 务，根据产品(零件)的工艺路线和 设备负荷可能性，确定各个生产单 位作业任务的先后顺序。
作业排序问题通常表述为“n项作 业任务在m个生产单位的排序的问 题”。
确定出最佳的作业顺序看似容易，只要列出所有的顺序 ，然后再从中挑出最好的就可以了，但要实现这种想法 几乎是不可能的。
排序的基本概念 (Sequencing)
例如：考虑32项任务（工件），有32！=2.6*1035种方 案，假定计算机每秒钟可以检查1 billion个顺序，全 部检验完毕需要8.4*1015个世纪。
4、去掉已调整的任务，重复2-4步。 最后得最优解： J2 –J1 –J3 –J4 –J6 –J5
F=13.67
4、FCFS、SPT、EDD、SST优先规则的应用
例：下表是在某工作中心等待加工的6项作业的加 工时间（包含换产时间）与预定日期，假设工作的 到达顺序与表中顺序相符 。根据以下规则来决定其 作业顺序：① FCFS ② SPT ③ EDD ④ SST并对它 们分别进行评价。

练习
J1 机器1 机器2 pi1 pi2 8 8 10 15 3 J2 11 19 21 5 J3 16 21 22 4 J4 20 22 24 J5 J6 2 22 4 26
2
5 5
8
2
2
1
1
2
5
8
27 35
6
10
33 45
机器3
机器4
pi3
pi4
20 5 26 4 30 1 31 7 42 10 55
(2) Palmer（斜度指标法）
工件的斜度指标计算公式
λ i=
k (m 1) / 2Pik
k 1
m
k＝1，2，……m 式中，m机器数；Pik为工件i在Mk上 的加工时间。
举例
有一个4/3/P/Fmax问题，其加工时间如下 表所示，用Palmer法求解。
i Pi1 Pi2 Pi3
一、排序问题的基本概念
排序是确定工件（零部件）在一台 或一组设备上加工的先后顺序。
在一定约束条件下，寻找总加工时 间最短的安排产品加工顺序的方法，就 是生产作业排序。
排序困难性
例如，考虑32项任务（工件），有32！2.61035种 方案,假定计算机每秒钟可以检查1 billion个顺序, 全部检验完毕需要8.41015个世纪。 如果只有16个工件, 同样按每秒钟可以检查1 billion 个顺序计算, 也需要2/3年。 以上问题还没有考虑其他的约束条件, 如机器、人 力资源、厂房场地等，如果加上这些约束条件，所 需要的时间就无法想象了。 所以，很有必要去寻找一些有效算法，解决管理中 的实际问题。
li0延误fmax最长流程时间fmaxmaxfi根据机器数的多少单台机器的排序问题多台机器的排序问题根据加工路线的特征单件作业排序jobshop流水作业排序flowshop根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序根据要实现的目标单目标排序多目标排序其中n工件数

带期限的作业排序问题(1)答：c`(x)的设计思路:当x=1时，c`(x)为所有作业的罚款金额总和,某节点m的估计值为c`(x)，并对其进行扩展时，其有效的子节点a的c`(x)为m的c`(x)-a的罚款金额。

对于u(x)初始时为作业罚款金额总和。

之后，若队列中的某一节点b的c`(x)最小且小于u(x),则使u(x) =b. c`(x)(2)(3)当某节点的已经被罚款项即c(x)>U，则封杀此节点。

(4)当从根开始到当前要加入的节点这条路径中，共花费时间costtime ,最大截止期限为maxdeadtime，若maxdeadtime<costtime则此节点不可行，否则可行.(5)主要结构及类型说明node queue[1000];//存放状态空间树中的节点Node结构在构造状态空间树时使用struct node{int number;//所代表的作业在source[]的下标int mayfine;//可能的罚款的金额即罚款金额的上限int currentfine;//到此节点止已罚款的金额bool iskilled;//是否被杀死int timecost;//从根节点到此节点为止已花费的时间int parent;//父节点在queue[]的下标};Tast结构在输入作业信息时使用struct task{int number;//作业的序号int fine;//罚款金额int deadline;//截止期限int time;//完成此作业所需的时间};int ans=0;//最小上界值在queue的下标int minmayfine;//队列中活结点的罚款上限的最小值即Uint activenumber=1;//活结点的数目const int N = ?;//N表示作业数int size = 1;//当前队列中的元素个数(6)程序代码思想：//使作业按截至期限的非降序排列，则对一个父节点s，要加入一个节点m，只要m 的截至期限大于等于s.timecost+m所代表的作业的time#include<iostream>#include<algorithm>using namespace std;struct node{int number;//选择的节点在source[]的下标int mayfine;//可能的罚款的金额即罚款金额的上限int currentfine;//到此节点止已罚款的金额bool iskilled;//是否被杀死int timecost;//从根节点到此节点为止已花费的时间int parent;//父节点在queue[]的下标};struct task{int number;//作业的序号int fine;//罚款金额int deadline;//截止期限int time;//完成此作业所需的时间};//节点被杀死的条件是已罚款的金额超过了最小罚款金额即currentfine>mayfinenode queue[1000];//存放状态空间树const int N = 4;//N表示作业数task source[N+1] = {{0,0,0,0}, {1,5,1,1}, {2,10,3,2}, {3,6,2,1}, {4,3,1,1}};//作业集合int ans=0;//最小上界值在queue的下标int minmayfine;//队列中活结点的罚款上限的最小值int activenumber=1;//活结点的数目void init()//初始化队列{for (int i =1; i <= N; i++){minmayfine +=source[i].fine;}queue[0].mayfine = minmayfine;queue[0].currentfine =0;queue[0].iskilled =0;queue[0].number = 0;//作业的序号queue[0].parent = -1;queue[0].timecost =0;}bool greater(task x,task y){if (x.deadline <= y.deadline)return 1;elsereturn 0;}//aloca为节点m在queue[]的下标,b为m的子节点x的作业在source[]的下标，获取x 到目前为止已罚款数int getfine(int aloca,int b){int a = queue[aloca].number;//a为节点m在source[]中的下标int fine = queue[aloca].currentfine;for(int i = a+1;i<b;i++)fine += source[i].fine;return fine;}void construction(){sort(source+1,source+N+1,greater);//截止期限按非降序排列int size = 1;//当前队列中的元素个数int active =0;//正在扩展的活结点的下标int a;int costtime;while (activenumber != 0){//当一个节点已罚的款数大于最终罚款的上界的最小值，则杀死并查找下一个活结点if(queue[active].currentfine > minmayfine ){queue[active].iskilled = 1;active++;activenumber--;//活结点减少1continue;}//向后选择作业，直到所有的组合都选择完a=queue[active].number+1;while (a<=N){costtime = queue[active].timecost+source[a].time;if (costtime <= source[a].deadline){queue[size].currentfine = getfine(active,a);//a为在source[]中的下标queue[size].iskilled =0;queue[size].mayfine = queue[active].mayfine - source[a].fine;queue[size].parent = active;queue[size].number = a;queue[size].timecost = costtime;//寻找队列中最终罚款的上限的最小值if(queue[size].mayfine < minmayfine){minmayfine = queue[size].mayfine;//答案节点的上界即Uans = size;}size++;//队列长度增加activenumber++;}//外层if结束a++;}//内层while结束//一个节点完全扩展完了，就会被杀死，并且活结点数目减少1queue[active].iskilled =1;activenumber--;active++;//扩展下一个节点}//外层while结束while (ans != 0){cout<<source[queue[ans].number].number<<" ";ans = queue[ans].parent;}cout<<endl;}void main(){init();construction();}. .。

带期限的作业调度问题2010-2011 第二学期08通信专业算法作业题目：给定一个带期限的作业排序问题, n=5, (p1,p2,p3,p4,p5)=(6,3,4,8,5), (t1,t2,t3,t4,t5)=(2,1,2,1,1), (d1,d2,d3,d4,d5)= (3,1,4,2,4), 应用FIFOBB求使总罚款数最小的可行作业集J, 要求:1）阐述c’(X)和u(X)的设计思路，U的初始值;2）针对解向量变长格式, 画出FIFOBB的生成的部分状态空间树, 按活节点生成顺序给节点编号，在各节点位置给出c’(X)和U的值，给每条边标记选择的作业编号;3）阐述c’(X)=U的处理方案, 可行解的判断方案；4）阐述你程序中的主要数据类型、数据变量和功能模块。

5）、编成并上机实现FIFOBB程序, 实现对不同作业排序问题实例的求解，问题实例的输入数据存储在case.txt文件中，其格式为：第一行问题规模（最多10个作业）第二行各作业的罚款数，数据项之间用一个空格分隔第三行各作业的截止期限，数据项之间用一个空格分隔第四行各作业所需的运行时间，数据项之间用一个空格分隔解：1、C（x）为成本估计函数，Pi是各个作业的成本。

U（x）是对应结点X的解的成本值。

在比较的时候可能出现C（x）=U（x），我们设一个较小的常数e，一句当前结点的截止期限与前面结点的运行时间总和比较，若大于，则结点可行，不大于，则不可行。

2.状态空间树：方框：椭圆表示结点；作业：1 2 3 4 5 六边形表示死结点。

作业：2 3 4 5 3 4 5 4 5 5作业：3 4 5 4 5 5 4 5 5 5作业：51 11 10 9 8 7 12 6 5 43 2 16 15 14 13 1922 23 24 26 25估计成本：最小上界： 17,1718,18 21， 21 13， 18 9， 22 6， 23 0，267,12 3， 16 0， 17 13， 13 15， 15 9,1410,15 6, 19 0， 20 12， 127， 7 6, 1114，1410，106, 1117 2721 20183.主要数据类型与变量int max// 罚款总数int cost;//罚款int time;//所用时间{int parent;//父亲结点int x;//表示节点所做的任务几Int U;//存放最小成本int c；//估计罚款}4.算法或程序模块int maycost(Elemt X) 功能：计算估计成本maycost函数int Mincost(int x[5],int y[5]) 功能：计算最小上界mincost成本void entergroup(int w,int E) 功能：活结点进队列int outgroup(int E) 功能：活结点出队列void BB(int T) 功能：在所有的结点中寻找最小成本四、测试1.方案建立一个文本文档case.txt与程序放在同一个文件目录下。

一种更快的作业排序算法从带有限期的作业排序贪心算法可以看到:当找到下一个要插入队列中的作业的位置后,需要将队列中位于它后面的所有作业均向后移动一个位置,算法中有许多时间浪费在移动作业的位置上。

如果能一次找准下一个要插入到队列中的作业的位置,则可避免队列中作业位置的移动,为算法节省不少时间,这是算法值得改进的地方。

为了给后继作业留下尽可能大的选择空间，在考虑作业i 时,将[0 、1 ] , [1 、2 ] , ⋯,[]i i d d ,1-中最大的空闲时间区间分配给作业i 。

通过使用不相交集合的UNION 与FIND 算法以及使用一个不同的方法来确定部分解的可行性，可以把JS 的计算时间由2()O n 降低到数量级相当接近于()O n 。

如果J 是作业的可行子集，那么可以使用下述规则来确定这些作业中的每一个作业的处理时间：若还没给作业i 分配处理时间，则分配给它时间片[]1,αα-，其中α应尽量取大且时间片[]1,αα-是空的。

此规则就是尽可能推迟对作业i 的处理。

于是，在将作业一个一个地装配到J 中时，就不必为接纳新作业而去移动J 中那些已分配了时间片的作业。

如果正被考虑的新作业不存在像上面那样定义的α，这个作业就不能计入J 。

例5.3 设n=5,(p1,…,p5)=(20,15,10,5,1),(d1,…,d5)=(2,2,1,3,3)。

最优解是J ＝{1,2,4}由于只有n 个作业且每个作业花费一个单位时间，因此只需考虑这样一些时间片[]1,,1i i i b -≤≤，其中{}{}min ,max j b n d =。

为简便起见，用i 来表示时间片[]1,i i -。

实现上述调度规则的一种方法是把这b 个期限值分成一些集合。

对于任一期限值i ，设i n 是使得i n i ≤的最大整数且是空的时间片。

为避免极端情况，引进一个虚构的期限值0和时间片[]1,0-。

当且仅当i j n n =，期限值i 和j 在同一个集合中，即所要处理的作业的期限值如果是i 或j ，则当前可分配的最接近的时间片是i n 。

一种改进的有限期作业排序算法研究提出了作业最晚运行次序的概念,改进算法的时间复杂度完全取决于排序算法的时间复杂度,并且改进算法可以直接得到最大效益作业子集的一种可行运行次序。

标签：有限期作业;贪心方法;作业最晚运行次序;排序1 改进算法1.1 算法思想改进的有限期作业排序的贪心方法:取得最大效益的作业子集一定是运行作业数目最多的子集,在不考虑获得最大效益的前提下,首先将n个作业按有限期从小到大排序,然后求出在一批作业中CPU最多能运行的作业数目m(m* pData,int count){ int i,j;int k;Job* t;for(i=0;ideadline>(*pData)[j]->deadline)k=j;if(k!=i){t=(*pData)[i];(*pData)[i]=(*pData)[k];(*pData)[k]=t;}}}long runMostJobNumber(vector* pVecPJob){ int t=0;int i;for(i=0;ideadline )t++;return t;}1.3 设置作业的最晚运行次序作业最晚运行次序依赖于具体一个作业集合,同一个作业在不同作业集合中时其最晚运行次序值可能是不同的。

如果一个作业在一个作业集中运行的次序大于它的最晚运行次序,那么无法获得该作业的效益值,因为CPU运行到改该作业时作业已过期。

根据m给每个作业设置CPU运行该作业的最晚次序(lateRunOrder)。

作业集仍按deadline从小到大有序,将排列中最后一个作业的最晚运行次序设为m。

然后从排列倒数第二个作业开始依次给剩下的作业设置最晚运行次序,作业的最晚运行次序按以下原则设置:对于任一对相邻的两个作业,如果前一个作业的期限值小于它后面作业的期限值,那么前一个作业的最晚运行次序等于它后面一个作业最晚运行次序减1,否则两个作业的最晚运行次序相同。

具体算法如下:void setJobLateRunOrder(vector* pVecPJob,int mostJobNumber){ int i;int lateRunOrder=mostJobNumber;int s=(*pVecPJob).size();((*pVecPJob)[s-1])->lateRunOrder=lateRunOrder;for(i=s-2;i>=0;i--){if(((*pVecPJob)[i])->deadlinedeadline ){lateRunOrder--;((*pVecPJob)[i])->lateRunOrder=lateRunOrder;}else ((*pVecPJob)[i])->lateRunOrder=lateRunOrder;}}1.4 求解作业集的最大效益定义一个能存储m个Job对象的数组,数组初始化为空,即未保存任何作业对象。

有限排队(Waiting Line with Limited Capacity)
若等待场所无法容纳所有需求服务的顾客，一些人会离
去，这种情况称为有限排队
2 排队管理(Waiting Line Management)
(2) 需求群体 不同群体需求不同，每一类需求的预期等待时 间(Expected Waiting Time)不同 (3)排队结构 多条排队(Multi-Line) 单一排队(Single-Line) 领号
i M1 M2
1 8 3
2 4 2
3 7 6
4 1 9
5 3 2
6 10 5
CWU-HRM
人力系
多工件多设备的排序问题启发算法
关键工件法
1983年提出 1.
2.
3.
计算每个工件的总加工时间Pi，找出加工时间最长 的工件C为关键工件 余下的工件，如果 Pi1 Pim 则按照Pi1 不减的顺 序排成序列S1，如果 Pi1 >Pim 则按照Pim 不增的顺 序排成序列S2， 序列（ S1 ，C， S2，）为所求排序
6 6 1 8 3 6
CWU-HRM
6.3 服务业作业排序
人力系
排序的对象是人而不是物；系统动态与随机性
特点比制造业更突出；排序问题与排队模型结合 在一起而产生作用
CWU-HRM
1 划分需求，进行排序
需求的分类
随机 计划（通过排序，平衡负荷(Load Balance)）
美国某医院对需求分析显示：
非预约病人周一看病人数最多，而其他时间来的相对较少。 非预约——随机 预约——可控——安排在每周后几天，使负荷稳定，减少 等待时间。
2 排队管理(Waiting Line Management)

贪⼼算法（4）：作业排序问题上⼀堂课程，我们学习了如何选择活动，使得在不发⽣冲突的前提下，能参与尽可能多的活动，这⾥没有考虑到不同的活动是否会带来不同的收益，假设它们的收益是⼀样的。

现在我们把问题修改下：有⼀系列作业，每个作业必须在各⾃的截⽌时间点之前完成，并且已知完成每个⼯作需要花费的时间以及带来的收益。

为了简单起见，假设完成每个⼯作都需要相等的单位时间，这样作业的截⾄时间点也就是单位时间的倍数。

再假设⼀次只能安排⼀个作业，完成⼀个作业后才能继续下⼀个作业。

问：如何选择作业并安排次序使它们能带来的总收益为最⼤？我们⽤例⼦A来说明。

【输⼊】有4个作业a,b,c,d。

它们各⾃的截⽌时间和能带来的收益如下：【输出】请找出⼀种能带来最⼤收益的作业执⾏次序。

在例⼦中，下列作业次序能带来最⼤的收益：｛c, a｝完成作业c，能带来的收益是40；因为做作业c，截⽌时间为1，它必须安排在0-1之间执⾏。

这样已经错过了b或d的截⽌时间点（1），因此⽆法再选择b或d，只能选择作业a，a的截⾄时间点为4，来得及完成。

做作业a的收益是20，因此完成作业c和a能带来的总收益是 40+20=60。

⽽选择其他次序的作业，都⽆法超过收益60。

参见下⾯的动图：我们再看⼀个例⼦B【输⼊】有5个作业a,b,c,d,e。

它们各⾃的截⽌时间和能带来的收益如下：请你选择和安排能获取最⼤收益的作业次序，先不给出答案，请你先思考，如何解答，然后再继续阅读。

算法分析⼀个简单粗暴的算法就是⽣成给定作业集合的所有⼦集，并检查每⼀个⼦集以确定该⼦集中作业的可⾏性，然后找出哪个可⾏⼦集可以产⽣最⼤收益。

这是⼀个典型的贪⼼算法。

算法思路如下：1）根据收益递减顺序对所有作业进⾏排序。

2）将结果序列初始化，并把已排序作业中的第⼀个作业加⼊3）依次按下⾯的规则处理剩余的n-1个作业如果把当前作业加⼊结果序列，不会错过它的截⽌时间，那么把它加⼊结果序列；否则忽略当前的作业。

有期限的作业调度算法一、典型算法贪心算法是以局部最优为原则,通过一系列选择来得到问题的一个最优解,它所做的每一个选择都是当前状态下某种意义上的最佳选择.贪心算法适合于解决这样的问题:局部的最优解能够导致最终结果的最优解。

“有限期作业安排问题”描述如下:有n个任务J1,J2,...,Jn,每个任务Ji都有一个完成期限di,若任务Ji在它的期限di内完成,则可以获利Ci(1[i[n);问如何安排使得总的收益最大(假设完成每一个任务所需时间均为一个单位时间).这个问题适合用贪心算法来解决,贪心算法的出发点是每一次都选择利润大的任务来完成以期得到最多的收益;但是对于本问题由于每一个任务都有一个完成的期限,因此在任务安排过程中除了考虑利润Ci外,还要考虑期限di.（一）算法描述1．假设用数组J存储任务,用数组C存储利润,用数组d存储期限,用数组P存储安排好的任务.按照利润从大到小的次序,调整任务的次序：对n个任务J1,J2,...,Jn进行调整,使其满足C1≥C2≥…≥Cn.2．将排序后的任务顺次插入输出数组P.A)任务J[1]排在P[1];B)若已经优先安排了k个任务,则它们满足d[P[i]] ≥i(1≤i≤k),即利润较高的k个任务能够在它们的期限内完成.那么,对于第k+1个任务J[k+1],显然C[k+1] ≤C[i](1≤i≤k);比较d[k+1]和d[P[k]]:a)若d[k+1]大于d[P[k]],那么将它排在第k+1位(P[k+1]←J[k+1]);b)若d[k+1]小于等于d[P[k]],那么,J[k]能否插入,需比较k和d[P[k]]而定:i)若k等于d[P[k]](其第k个任务已经排在可以满足的最迟时间),那么,因为Ck≥Ck+1,只好放弃任务J[k+1];ii)若k小于d[P[k]](表示第k个任务还有推后的余地):若d[k+1]=k,将第k个任务后移一位(P[k+1]←P[k]),将第k+1个任务排在第k位(P[k] ←J[k+1]).若d[k+1]<k,则继续比较任务J[k+1]与第k-1个任务,方法同上.C)重复B)直至处理完最后一个任务.3)输出P.（二）算法实现voidjob-arrangement(char*J[],intd[],intC[],intP[],intn){sort(C,J,d,n); /*按照降序调整数组C,同时对数组J!d作相应调整*/P[0]=0;d[0]=0;P[1]=1;k=1;for(i=2;i<=n;i++){r=k;while{(d[P[r]]>=d[i])&&d[P[r]]!=r}r--;if(d[P[r]]<d[i])for(h=k;h>r;h--) P[h+1]=P[h];k++;P[r+1]=i;}output(P,J,n)}（三）算法分析该算法在最坏情况下的时间复杂度是O（n²），在最好情况下的是O（n）二．利用UNION与FIND进行作业排序利用不相交集合的UNION与FIND算法以及使用一个不同的方法来确定部分解的可行性。