非单位时间任务安排问题.pdfVIP

非单位时间任务安排问题

肖瑶逸计科1101

整理ppt

问题描述：

具有截止时间和误时惩罚的任务安排问题可描

述如下：

给定n个任务的集S={1，2,3...，n}；

完成任务i需要ti时间，1≤i≤n；

任务i的截止时间di，1≤i≤n，即要求任务i在

时间di之前结束；

④任务i的误时惩罚wi，1≤i≤n，即任务i未在时

间di之前结束将招致wi的惩罚；假设按时完成

那么无惩罚。

任务安排问题要求确定S的一个时间表〔最优

时间表〕使得总误时惩罚到达最小。

整理ppt

算法分析:首先将其任务依其截止时间递增排序

设对任务1，2,3，...，i，截止时间为d的最小误

时惩罚为p(i,d),那么p(i,d)具有最优子结构性质

且满足如下递归式：

p(i,d)=min{p(i-1,d)+w(i),p(i-1,min{d,di}-

ti)}

20,t1≤d

w(1),t1d

整理ppt

算法设计：

和递推法相仿，贪心法也是从问题的某

一个初始解出发，向给定的目标递推。但

不同的是，推进的每一步不是依据某一固

定的递推式，而是做一个局部的最优选择，

即贪心选择〔在例中，这种贪心选择表现

为选择一行中的最大整数〕，这样，不断

的将问题归纳为假设干相似的子问题，最

终产生出一个全局最优解。

局部贪心的选择是否可以得出全局最优是

能否采用贪心法的关键

整理ppt

数据输入：由文件input.txt给出输入数据。第1行是1个整数n，

表示任务数。接下来的n行中，每行有3个整数a,b,c，表示完

成相应任务需要时间a，截止时间b，误时时间c。

结果输出〔例如〕：将计算的总误时惩罚输出到文件output.txt。

输入文件例如输出文件例如

input.txtoutput.txt

7110

14706

2260

1450

1340

1130

1420

3680

整理ppt

代码实现：

#includestdafx.h

#includestdio.h

#includeiostream

#includeconio.h

usingnamespacestd;

intn;//定义工作数

inttt[99];

intf[99][99];

intd;//最大需求时间

//结构体数组

structtsk

intkk[3];

}tsk[99];

structpass

intpp[3];

}pass[99];

整理ppt

//归并排序

voidmerge(intdata[],intp,intq,intr)

{

inti,j,k,n1,n2;

n1=q-p+1;

n2=r-q;

intL[];

intR[];

for(i=0,k=p;in1;i++,k++)

L[i]=data[k];

for(i=0,k=q+1;in2;i++,k++)

R[i]=data[k];

for(k=p,i=0,j=0;in1jn2;k++){