车间调度算法

Question

单机问题：
有4道工序,其中工序1需要时间为4小时,要求完成时间为第6个小时之前完成.工序2需要时间为2小时,要求完成时间为第12小时之前完成.工序3需要时间为6小时,要求完成时间为18小时. 工序4要求完成时间为5小时,要求完成时间为10小时.时间从0开始算.
工作          1  2  3  4
加工时间      4  2  6  5
最迟完成时间  6  12  18  10
求他们4个工序的加工顺序,使他们都在最迟完成时间之间顺利完成. 如1、4、2、3就是一道符合要求的工序。
并行机问题：
有j1,j2,j3,j4,...,j20共20道作业，在两台并行的同功能的机器m1,m2上加工。每道作业有个最迟完成时间。如果超出了这个时间，就有个滞后时间。现在的要求是，如果将这20道作业分配到这两台机器上，使得两台机器最迟完成时间最小。比如一共需要50个小时，m1上分配30个小时，m2上分配20个小时，那么两台机器的最迟完成时间为30小时；如果m1上分配24,m2上分配26,那么两台机器的最迟完成时间为26。同时要求滞后时间之和最小。
这是公司给我的问题，请问各位有什么好的解决方法。能够给出思想就很感激了，有码当然更好。  不甚感激

Answer 1

第一题
package test;public class Order {
private void orderByTime() {
int time[] = { 4, 2, 6, 5 };
int lateTime[] = { 6, 12, 18, 10 };
int total = 0;
for (int i = 0; i < 4; i++) {
total = time[i];
if (total <= lateTime[i]) {
for (int j = 0; j < 4; j++) {
if (j != i) {
total = total + time[j];
if (total <= lateTime[j])
for (int k = 0; k < 4; k++) {
if (k != i && k != j) {
total = total + time[k];
if (total <= lateTime[k])
for (int m = 0; m < 4; m++) {
if (m != i && m != k && m != j) {
total = total + time[m];
if (total <= lateTime[m])
System.out.println(i + "-"
+ j + "-" + k + "-"
+ m);
else {
total = 0;
}
}
}
}
}
}
}
}
}
} public static void main(String[] args) {
new Order().orderByTime();
}
}