Java实现流水作业调度问题

流水作业调度问题:n个作业要求在两个机器上处理，要求先在第一个上处理，然后再在第二个处理器上处理，求如何安排使得完成后最后时间最短。

下面是程序代码：

1. import java.util.ArrayList;  
2. import java.util.Collections;  
3.   
4. class RenWu  
5. {  
6.     private int first;//第一个用的时间   
7.     private int second;//第二个用的时间   
8.     private boolean flag = false;//标志是否分配了   
9.     public RenWu(int first, int second)  
10.     {  
11.         this.first = first;  
12.         this.second = second;  
13.     }  
14.     public int getFirst()  
15.     {  
16.         return first;  
17.     }  
18.     public void setFirst(int first)  
19.     {  
20.         this.first = first;  
21.     }  
22.     public int getSecond()  
23.     {  
24.         return second;  
25.     }  
26.     public void setSecond(int second)  
27.     {  
28.         this.second = second;  
29.     }  
30.     public boolean isFlag()  
31.     {  
32.         return flag;  
33.     }  
34.     public void setFlag(boolean flag)  
35.     {  
36.         this.flag = flag;  
37.     }  
38. }  
39. class ShiJian implements Comparable  
40. {  
41.     @Override  
42.     public String toString()  
43.     {  
44.         return "ShiJian [time=" + time + ", shuYu=" + shuYu + ", diJiXiang="  
45.                 + diJiXiang + "]";  
46.     }  
47.     public ShiJian(int time, int shuYu, int diJiXiang)  
48.     {  
49.         super();  
50.         this.time = time;  
51.         this.shuYu = shuYu;  
52.         this.diJiXiang = diJiXiang;  
53.     }  
54.     private int time;//所用的时间   
55.     private int shuYu;//代表属于第几个作业   
56.     private int diJiXiang;//代表是第几个流水线上的时间   
57.       
58.     public int getTime()  
59.     {  
60.         return time;  
61.     }  
62.     public void setTime(int time)  
63.     {  
64.         this.time = time;  
65.     }  
66.     public int getShuYn()  
67.     {  
68.         return shuYu;  
69.     }  
70.     public void setShuYn(int shuYn)  
71.     {  
72.         this.shuYu = shuYn;  
73.     }  
74.     public int getDiJiXiang()  
75.     {  
76.         return diJiXiang;  
77.     }  
78.     public void setDiJiXiang(int diJiXiang)  
79.     {  
80.         this.diJiXiang = diJiXiang;  
81.     }  
82.     @Override  
83.     public int compareTo(Object arg0)  
84.     {  
85.         ShiJian obj = (ShiJian)arg0;  
86.         return this.time>obj.getTime()?1:(this.time==obj.getTime()?0:-1);  
87.     }     
88. }  
89. public class liushuizuoye  
90. {  
91.     public static void main(String args)  
92.     {  
93.         RenWu renWu = new RenWu[6];  
94.         renWu[0] = new RenWu(3,8);  
95.         renWu[1] = new RenWu(12,10);  
96.         renWu[2] = new RenWu(5,9);  
97.         renWu[3] = new RenWu(2,6);  
98.         renWu[4] = new RenWu(9,3);  
99.         renWu[5] = new RenWu(11,1);  
100.         ArrayList list = new ArrayList();//时间队列   
101.         //将时间加入到时间队列   
102.         for(int i = 0;i<6;i++)  
103.         {  
104.             list.add(new ShiJian(renWu[i].getFirst(),i,1));  
105.             list.add(new ShiJian(renWu[i].getSecond(),i,2));  
106.         }  
107.         Collections.sort(list);  
108. //      for(int i = 0;i<list.size();i++)   
109. //          System.out.println((ShiJian)list.get(i));   
110.         int result = new int[6];  
111.         int start =0;int end = 5;  
112.         for(int i = 0;i<list.size();i++)  
113.         {  
114.             ShiJian shijian = (ShiJian)list.get(i);  
115.             int num = shijian.getShuYn();//得到属于第几项任务   
116.             if(!renWu[num].isFlag())//如果未分配则分配   
117.             {  
118.                 if(shijian.getDiJiXiang() == 1)//表示的是第一项   
119.                 {  
120.                     result[start] = num;  
121.                     start++;  
122.                     renWu[num].setFlag(true);  
123.                 }  
124.                 else//如果是第二个时间   
125.                 {  
126.                     result[end] = num;  
127.                     end--;  
128.                     renWu[num].setFlag(true);  
129.                 }  
130.             }  
131.         }  
132.         System.out.println("流水作业的时间是：");  
133.         for(int i = 0;i<6;i++)  
134.             System.out.print((result[i]+1)+"  ");  
135.     }  
136.   
137. }