1，问题
（问题来自：《计算机算法设计与分析（第4版）》王晓东 编著）
用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是a[i]，若由机器B来处理，则所需要的时间是b[i]。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。研究一个实例：n=6, a = {2, 5, 7, 10, 5, 2}, b = {3, 8, 4, 11, 3, 4}.
要求：用文件input.txt输入数据，文件output.txt输出数据。
输入文件示例：input.txt
6
2 5 7 10 5 2
3 8 4 11 3 4
输出文件示例：output.txt
15
2，分析
1）函数
当完成k个作业，设：
机器A花费了x时间；
机器B所花费时间的最小值肯定是x的一个函数，设：
F[k][x]表示机器B所花费时间的最小值。
则：
F[k][x]=Min{ F[k-1][x]+b[k], F[k-1][x-a[k]] }；
其中F[k-1][x]+b[k]表示第k个作业由机器B来处理（完成k-1个作业时机器A花费的时间仍是x），F[k-1][x-a[k]]表示第k个作业由机器A处理（完成k-1个作业时机器A花费的时间是x-a[k]）。
那么单个点对较大值即：
Max(x, F[k][x])，表示此时（即机器A花费x时间的情况下）所需要的总时间。
而机器A花费的时间x是变化的，即x=0,1,2……x(max)，（理论上x的取值是离散的，但为编程方便，设为整数连续的）由此构成了点对较大值序列。要求整体时间最短，取这些点对较大值序列中最小的即是。
2）举例：
对于a = {2, 5, 7, 10, 5, 2}, b = {3, 8, 4, 11, 3, 4}。
完成一个作业，求完成时两台机器花费的最少时间 ：
则0<=x<=a[0]
x=0时，F[0][0]=3，则Max(0,3)=3，机器A花费0时间，机器B花费3时间，而此时两个机器所需时间为3；
x=1时，F[0][1]=3，Max(1,3)=3；
x=2时，F[0][2]=0，则Max(2,0)=2；
当x=2时，完成第一个作业两台机器花费最少的时间为2，此时机器A花费2时间，机器B花费0时间。
完成2个作业，0<=x<=(a[0]+a[1])
令x<0时，F[1][x] = ∞（数组下标不能小于0）
x=0，则F[1][0]= Min{ F[0][0]+b[2], F[0][0-a[1]] }= Min{3+8,∞}=11，进而Max(0,11)=11；
x=1，则F[1][1]= Min{ F[0][1]+b[2], F[0][1-a[1]] }= Min{3+8,∞}=11，进而Max(11)=11；
x=2，则F[1][2]= Min{ F[0][2]+b[2], F[0][2-a[1]] }= Min{0+8,∞}=8，进而Max(2,8)=8；
x=3，则F[1][3]= Min{ F[0][3]+b[2], F[0][3-a[1]] }= Min{0+8,∞}=8，进而Max(3,8)=8；
x=4，则F[1][4]= Min{ F[0][4]+b[2], F[0][4-a[1]] }= Min{0+8,∞}=8，进而Max(4,8)=8；
x=5，则F[1][5]= Min{ F[0][5]+b[2], F[0][5-a[1]] }= Min{0+8,3}=3，进而Max(5,3)=5；
x=6，则F[1][6]= Min{ F[0][6]+b[2], F[0][6-a[1]] }= Min{0+8,3}=3，进而Max(6,3)=6；
x=7，则F[1][7]= Min{ F[0][7]+b[2], F[0][7-a[1]] }= Min{0+8,0}=0，进而Max(7,0)=7；
3，复杂度
O（n*Sum） 其中Sum为a中所有元素之和与b中所有元素之和的最小值。
4，代码
动态规划，java语言。
输入：input.txt
6,
2,5,7,10,5,2,
3,8,4,11,3,4,
package task_scheduling;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class Main {
private final static int SIZE = 50;
private final static int MAXINT = 999;
/** 任务 */
private static TaskBean taskA;
private static TaskBean taskB;
public static void main(String[] args) throws IOException {
int data;
ReadFile();
int temp = TaskScheduling.TaskScheduling(taskA, taskB);
if (0 == temp) {
System.out.println("计算出错");
} else {
// out.txt
FileUtil.writeFile("output.txt", temp + "");
}
}
/**
* Read input.txt
*
* @throws IOException
*/
private static void ReadFile() throws IOException {
int[] Data = new int[SIZE];// 文件读取到的数据转换为int存储
String[] Data_str = new String[SIZE];// 文件读取到的数据
Data_str = FileUtil.readFile("input.txt").split("\,");
int index = 0;
for (String item : Data_str) {
Data[index++] = Integer.parseInt(item);
}
int N = (int) Data[0];
int[] a = new int[SIZE], b = new int[SIZE];
for (int i = 1; i <= N; i++) {
a[i] = Data[i];
}
for (int i = 1, j = N + 1; j <= 2 * N; j++, i++) {
b[i] = Data[j];
}
taskA = new TaskBean(N, a);
taskB = new TaskBean(N, b);
}
}
package task_scheduling;
public class TaskBean {
private final int SIZE = 50;// 数组大小
private final int MAXINT = 999;
private int N;// 任务数量
private int[] task = new int[SIZE];// 处理机处理任务的时间
// 存储的计算后的数据
private int[] Sum = new int[SIZE];// 处理到第i个作业累加的时间和
private int tempSum = 0;// 和
public TaskBean(int N, int[] task) {
this.setN(N);
this.setTask(task);
for (int i = 1; i <= N; i++) {
tempSum += task[i];
Sum[i] = tempSum;
}
}
public int getN() {
return N;
}
public void setN(int n) {
N = n;
}
public int[] getTask() {
return task;
}
public void setTask(int[] task) {
this.task = task;
}
public int[] getSum() {
return Sum;
}
public void setSum(int[] sum) {
Sum = sum;
}
public int getTempSum() {
return tempSum;
}
public void setTempSum(int tempSum) {
this.tempSum = tempSum;
}
}
核心算法：
package task_scheduling;
/**
* 独立任务最优调度问题
*
* @author luo
*
*/
public class TaskScheduling {
private final static int SIZE = 50;
private final static int MAXINT = 999;// 无穷大
public static int TaskScheduling(TaskBean taskA, TaskBean taskB) {
int temp = 0;// 返回的数
int N = taskA.getN();// 任务数
int[] SumA = taskA.getSum();
int[] SumB = taskB.getSum();
int[] a = taskA.getTask();
int[] b = taskB.getTask();
// a的和、b的和min
int MinSum = (taskB.getTempSum() > taskA.getTempSum()) ? taskA.getTempSum() : taskB.getTempSum();
/// 动态二维数组
int[] MaxTime = new int[MinSum + 1];
int[][] F = new int[SIZE][N + 1];
// 初始化
SumB[0] = 0;
for (int i = 0; i < N + 1; i++) {
F[i] = new int[MinSum + 1];
F[i][0] = SumB[i];// SumB[0]没赋值，调试时会输出地址
for (int j = 1; j <= MinSum; j++) {
F[i][j] = 0;
}
}
// 计算F矩阵
for (int k = 1; k <= N; k++) {
temp = (SumA[k] > SumB[k]) ? SumB[k] : SumA[k];
for (int x = 1; x <= temp; x++) { // A最多用AB前k任务的最小值，如果B最少就全用B做。
if (x >= a[k])// 等于号不能少
F[k][x] = (F[k - 1][x] + b[k] < F[k - 1][x - a[k]]) ? F[k - 1][x] + b[k] : F[k - 1][x - a[k]];
else
F[k][x] = F[k - 1][x] + b[k];
}
}
temp = MAXINT;
//得出最优调度
for (int i = 0; i <= MinSum; i++) {
MaxTime[i] = (i > F[N][i]) ? i : F[N][i];
if (temp > MaxTime[i])
temp = MaxTime[i];
}
return temp;
}
}
package task_scheduling;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.UnsupportedEncodingException;
public class FileUtil {
/**
* 读文件 返回字符串
* @param url
* 文件地址，如："/sdcard/test.txt"
* @return
* @throws IOException
*/
public static String readFile(String url) throws IOException {
// 读取
String str = ""; // 读取到的内容
File urlFile = new File(url);
InputStreamReader isr = new InputStreamReader(new FileInputStream(urlFile), "UTF-8");
BufferedReader br = new BufferedReader(isr);
String mimeTypeLine = null;
while ((mimeTypeLine = br.readLine()) != null) {
str = str + mimeTypeLine;
}
System.out.println("FileUtil读取内容：" + str);
return str;
}
/**
* 写文件，成功返回true
* @param filePath 文件地址
* @param sourceString 待写入字符串
* @return
*/
public static boolean writeFile(String filePath, String sourceString){
//写入
try{
System.out.println("写入文件信息：" + sourceString);
byte[] sourceByte = sourceString.getBytes();
if(null != sourceByte){
File file = new File(filePath); //文件路径（路径+文件名）
if (!file.exists()) { //文件不存在则创建文件，先创建目录
file.createNewFile();
}
FileOutputStream outStream = new FileOutputStream(file); //文件输出流用于将数据写入文件
outStream.write(sourceByte);
outStream.close(); //关闭文件输出流
}
}catch(Exception e){
System.out.println("写入失败");
return false;
}
System.out.println("写入成功");
return true;
}
}
最后
以上就是坚定高跟鞋最近收集整理的关于【算法】算法-独立任务最优调度问题（双机调度问题）1，问题2，分析3，复杂度4，代码的全部内容，更多相关【算法】算法-独立任务最优调度问题（双机调度问题）1内容请搜索靠谱客的其他文章。
发表评论 取消回复