非单位时间任务安排问题

《非单位时间任务安排问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、非单位时间任务安排问题肖瑶逸计科1101问题描述：具有截止时间和误时惩罚的任务安排问题可描述如下：给定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的一个时间表（最优时间表）使得总误时惩罚达到最小。算法分析:首先将其任务依其截止时间递增排序。设对任务1，2,3，...，i，截止时间为d的最小误时惩罚为p(i,d),则p(i,d)具有

2、最优子结构性质且满足如下递归式：p(i,d)=min{p(i-1,d)+w(i),p(i-1,min{d,di}-ti)}20,t1≤dp(1,d)=w(1),t1>d算法设计：和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键数据输入：由文件input.txt给出输入数据。第1行是

3、1个整数n，表示任务数。接下来的n行中，每行有3个整数a,b,c，表示完成相应任务需要时间a，截止时间b，误时时间c。结果输出（示例）：将计算的总误时惩罚输出到文件output.txt。输入文件示例输出文件示例input.txtoutput.txt711014706226014501340113014203680代码实现：#include"stdafx.h"#include"stdio.h"#include#include"conio.h"usingnamespacestd;intn;//定义工作数inttt[9

4、9];intf[99][99];intd;//最大需求时间//结构体数组structtsk{intkk[3];}tsk[99];structpass{intpp[3];}pass[99];//归并排序voidmerge(intdata[],intp,intq,intr){inti,j,k,n1,n2;n1=q-p+1;n2=r-q;intL[99];intR[99];for(i=0,k=p;i

5、r(k=p,i=0,j=0;iR[j]){data[k]=L[i];i++;}else{data[k]=R[j];j++;}}if(j

6、r(inti=0;i<=d;i++)if(tsk[0].kk[0]<=i)f[0][i]=0;elsef[0][i]=tsk[0].kk[2];for(inti=1;ij?j:tsk[i].kk[1];if(jj>tsk[i].kk[0]&&f[i][j]>f[i-1][jj-tsk[i].kk[0]])f[i][j]=f[i-1][jj-tsk[i].kk[0]];}}}int_tma

7、in(intargc,_TCHAR*argv[]){cout<<"pleaseputyourworknum";cin>>n;//工作数for(intm=0;m>tsk[m].kk[0];cout<<"pleaseputyour"<>tsk[m].kk[1];cout<<"pleaseputyour"<>tsk[m].kk[2];