流水作业调度Java代码

import javax.swing.*;

import ng.*;

import java.io.*;

public class FlowS{

static class Elememt

{

int key;

int index;

boolean job;

private Elememt(int kk,int ii,boolean jj)

{

key=kk;

index=ii;

job=jj;

}

}

public static int flowShop(int []a,int []b,int []c) //a[]放的是N1 b[]放的是N2

{ //c[]放的是作业排好序列的顺序

int n=a.length;

Elememt []d=new Elememt[n];

for(int i=0;i<n;i++){

int key=a[i]>=b[i]? b[i]:a[i]; //按johnson 法则分别取对应的b[i]或 a[i]值作为关键字

boolean job=a[i]<b[i]; //给符合条件a[i]<b[i]的放入N1子集大标记true d[i]=new Elememt(key,i,job);

System.out.println("d["+i+"] "+key+" "+i+" "+job);

}

mergeSort(d); // 对数组d 按关键字升序进行排序

System.out.println();

System.out.println("输出排序后的相关值");

for(int i=0;i<n;i++) //输出排序结果

System.out.println("d["+i+"] "+d[i].key+" "+d[i].index+" "+d[i].job);

int j=0,k=n-1;

for(int i=0;i<n;i++){

if(d[i].job)c[j++]=d[i].index; //将排过序的数组d，取其中作业序号

else c[k--]=d[i].index; //属于N1的从前面进入，属于N2的从后面进入

} //从而实现了N1的非减排序，N2 的非增排序

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]];

}

return k;

}

public static void mergeSort(Elememt[] e)

{

int k=e.length-1;

Elememt a;

for(int i=0;i<k;i++)

for(int j=i+1;j<=k;j++)

if(e[i].key>e[j].key){

a=e[i];

e[i]=e[j];

e[j]=a;

}

}

public static void main(String args[])

{

//int []x={2,4,3,6,1};

//int []y={5,2,3,1,7};

String s=JOptionPane.showInputDialog(null,"输入作业个数n的大小：",

"0-1背包问题",JOptionPane.QUESTION_MESSAGE);

int n=Integer.parseInt(s);

System.out.println("输出n的值:"+n);

System.out.println();

//构建数组

int []x=new int[n];

//数组赋值及输出

System.out.println("n个作业的ai值数组：");

for(int i=0;i<=n-1;i++){

String s1=JOptionPane.showInputDialog(null,"输入v["+i+"]：", "0-1背包问题",JOptionPane.QUESTION_MESSAGE);

x[i]=Integer.parseInt(s1);

System.out.print(x[i]+" ");

}

System.out.println();

int []y=new int[n];

//数组赋值及输出

System.out.println( );

System.out.println("n个作业的bi值数组：");

for(int i=0;i<=n-1;i++){

String s1=JOptionPane.showInputDialog(null,"输入w["+i+"]：", "0-1背包问题",JOptionPane.QUESTION_MESSAGE);

y[i]=Integer.parseInt(s1);

System.out.print(y[i]+" ");

}

System.out.println();

//int n=x.length;

int []z=new int[n];

System.out.println();

System.out.println("完成作业所需最短时间 "+flowShop(x,y,z)); System.out.println();

System.out.println("作业编号自0开始，作业执行顺序为 "); for(int j=0;j<n;j++)

System.out.print(" "+z[j]);

System.out.println();

}

}

本文来源：https://www.bwwdw.com/article/kuij.html