标题:用动态规划解决流水作业调度问题(我的程序的问题,请指教)
只看楼主
housan321
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-5-29
 问题点数:0 回复次数:3 
用动态规划解决流水作业调度问题(我的程序的问题,请指教)

请帮我看看我的程序错在哪里,输出结果不对呀!谢谢!
class Element1 implements Comparable
{
int key;
int index;
boolean job;

Element1(int kk,int ii,boolean jj)
{
key=kk;
index=ii;
job=jj;
}

public int compareTo(Object x)
{
int xkey=((Element1)x).key;
if(key<xkey)return -1;
if(key==xkey)return 0;
return 1;
}
}
class MergeSort //合并排序
{

public static void mergeSort(Comparable []a)
{
Comparable []b=new Comparable[a.length];
int s=1;
while(s<a.length){
mergePass(a,b,s);//合并到数组b
s+=s;
mergePass(b,a,s);//合并到数组a
s+=s;
}
}
public static void mergePass(Comparable []x,Comparable[]y,int s)
{
//合并大小为s的相邻子数组
int i=0;
while(i<=x.length-2*s)
{//合并大小为s的相邻2段子数组
merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;
}
//剩下的元素个数少于2s
if(i+s<x.length)
merge(x,y,i,i+s-1,x.length-1);
else
//复制到y
for(int j=i;j<x.length;j++)
y[j]=x[j];
}
public static void merge(Comparable []c,Comparable[]d,int l,int m,int r)
{
//合并c[l:m]和c[m+1:r]到d[l:r]
int i=1,
j=m+1,
k=1;
while ((i<=m)&&(j<=r))
if (c[i].compareTo(c[j])<=0)
d[k++]=c[i++];
else d[k++]=c[j++];
if(i>m)
for(int q=j;q<=r;q++)
d[k++]=c[q];
else
for (int q=i;q<=m;q++ )
d[k++]=c[q];
}
}

public class flowshop
{

public static void main(String arg[])
{
int a[]={9,2,3,4,8,51,34,4}; //自实定作业的任务1
int b[]={6,6,9,15,6,21,5,8}; //自实定作业的任务2

int c[]=new int[b.length];
int h=flowShop(a,b,c);
System.out.println(h);
}
public static int flowShop(int[]a,int[]b,int[]c)
{
int n=a.length;
Element1 []d=new Element1[n];
for(int i=0;i<n;i++){
int key=a[i]>b[i]? b[i]:a[i];
boolean job=a[i]<=b[i];
d[i]=new Element1(key,i,job);
}
int j=0,k=n-1;
for(int i=0;i<n;i++){
if(d[i].job) c[j++]=d[i].index;
else c[k--]=d[i].index;

}

j=a[c[0]];
k=j+b[c[0]];
for(int i=1;i<n;i++){
j+=a[c[i]];
k=j<k? k+b[c[i]]:j+b[c[i]];
}
for(int i=0;i<n;i++)
{
System.out.println(c[i]+1); //输出调度的次序
}
return k; //返回最优调度时间

}
}

搜索更多相关主题的帖子: 动态规划 int key 流水作业 
2006-05-29 15:40
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
得分:0 
,请楼主把完整的题目发上来吧,不然不知道正确的输出是什么,也不大好给你的程序改错.

我的征途是星辰大海
2006-05-30 08:02
housan321
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-5-29
得分:0 
我现在把题目和分析发上来了,请大家帮帮我吧!谢谢!!!!!!!!!

个作业 要在由两台机器M1M2组成的流水线上完成加工.每个作业加工的顺序都是先在M1加工,然后在M2上加工。M1M2加工作业 所需的时间分别为 。流水作业调度问题要求确定这 个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2加工完成所需的时间最少。

直观上,一个最优调度应使机器M1没有空闲时间,且机器M2的空闲时间最少。在一般情况下,机器M2上会有机器空闲和作业积压两种情况。

设全部作业的集合为 N的作业子集。在一般情况下,机器M1开始加工S中作业时,机器M2还在加工其他作业,要等时间 后才可利用。将这种情况下完成S中作业所需的最短时间记为 。流水作业调度问题的题的最优值为

1. 最优子对结构性质

流水作业调度问题具有最优子结构性质。

是所给 个流水作业的一个最优调度,它所需的加工时间为

其在 是在机器M2的等待时间为 时,安排作业 所需的时间。

,则有

事实上,由T的定义知 。若 ,设 是作业集S在机器M2的等待时间为 情况下的一个最优调度。则 N的一个调度,且该调度所需时间为 。这就证明了流作业调度问题具有最优子结构的性质。

2006-05-30 17:45
housan321
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-5-29
得分:0 

怎么数学公式发不上来,显示不了呀?

2006-05-30 17:48



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-68271-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.771325 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved