-
回溯法 批处理作业调度_回溯算法——批处理作业调度
2020-12-24 08:32:27批处理作业调度问题要求对于给定的n个作业,制定一个最佳的作业调度方案,使其完成时间和达到最小。批处理作业调度问题的一个常见例子是在计算机系统中完成一批n个作业,每个作业都要完成先计算,然后将计算机结果...成为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的
n
个作业
,
制定一个最佳的作业调度方案
,
使其完成时间和达到最小。
批处理作业调度问题的一个常见例子是在计算机系统中完成一批
n
个作业,每个作业都要完成先计算,然
后将计算机结果打印输出这两项任务
。
计算任务由计算机的中央处理器完成
,
打印输出任务由打印机完成。
因此在这种情况下,计算机的中央处理器是机器
1
,打印机是机器
2
。
关于输入
要求输入:
1
、作业数
2
、每个作业完成时间表,如下
;
作业完成时间
机器
1
机器
2
作业
1
2
1
作业
2
3
1
作业
3
2
3
分析:给定
n
个作业的集合
{J1,J2,…,Jn}
。每个作业必须先由机器
1
处理,然后由机器
2
处理。作业
Ji
需
要机器
j
的处理时间为
tji
。对于一个确定的作业调度,设
Fji
是作业
i
在机器
j
上完成处理的时间。所有作
业在机器
2
上完成处理的时间和称为该作业调度的完成时间和。
这
3
个作业的
6
种可能的调度方案是
1,2,3
;
1,3,2
;
2,1,3
;
2,3,1
;
3,1,2
;
3,2,1
;
它们所相应的完成时间和分别是
19
,
18
,
20
,
21
,
19
,
19
。易见,最佳调度方案是
1,3,2
,其完成时间和
为
18
。
以
1,2,3
为例
:
作业
1
在机器
1
上完成的时间为
2,
在机器
2
上完成的时间为
3
作业
2
在机器
1
上完成的时间为
5,
在机器
2
上完成的时间为
6
作业
3
在机器
1
上完成的时间为
7,
在机器
2
上完成的时间为
10
3+6+10=19
,所以是
19
。
-
批处理作业调度
2019-12-18 22:39:46批处理作业调度 临近考试,又仔细复习了一遍,感觉比以前刚刚学的时候更加深刻和理解。以下是算法思想和代码。有不对的地方请指教。 给定n个作业,每一个作业都有两项任务分别在2台机器上完成。每个作业ji必须先有...批处理作业调度
临近考试,又仔细复习了一遍,感觉比以前刚刚学的时候更加深刻和理解。以下是算法思想和代码。有不对的地方请指教。
给定n个作业,每一个作业都有两项任务分别在2台机器上完成。每个作业ji必须先有机器1处理,然后再由机器2处理。作业需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f=F2i,称为该作业调度的完成时间和。
- 简单描述
对于给定的n个作业,指定最佳作业调度方案,使其完成时间和达到最小。
- 算法设计
类Flowshop的数据成员记录解空间的结点信息,M输入作业时间,bestf记录当前最小完成时间和,bestx记录相应的当前最佳作业调度。在递归函数Backtrack中,当i>n时,算法搜索至叶子结点,得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。当i<n时,当前扩展结点在i-1层,以深度优先方式,递归的对相应子树进行搜索,对不满足上界约束的结点,则剪去相应的子树。
- 算法描述
class Flowshop{ friend Flow(int * *,int,int[]); private: void Backtrack(int i); int * * M, * x, * bestx, * f2, f1, f, bestf, n; }; void Flowshop::Backtrack(int i){ if(i>n){ if(f>bestf){ for(int j=1;j<=n;j++) bestx[j]=x[j]; bestf = f; } else{ for(int j=i;j<=n;j++){ f1+=M[x[j]][i]; f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2]; f+=f2[i]; if(f<bestf){ Swap(x[i],x[j]); Backtrack(i+1); Swap(x[i],x[j]); } f1 -= M[x[j]][1]; f -= f2[i]; } } } int Flow(int * * M,int n,int bestx[]){ int ub = INT_AMX; Flowshop X; X.x = new int [n+1]; X.f2 = new int [n+1]; X.M = M; X.n = n; X.bestf = ub; X.bestx = bestx; X.f1 = 0; X.f = 0; for(int i=0;i<=n;i++){ X.f2[i] = 0; X.x[i]=1; } X.Backtrack(1); delete [] X.x; delete [] X.f2; return X.bestf; }
-
回溯法 批处理作业调度_回溯法之批处理作业调度
2021-01-14 07:07:57回溯法之批处理作业调度1. 问题描述n个作业集合{1, 2, ..., n}。每个作业先由机器1处理,再由机器2处理。作业i需要机器j处理的时间为Mij 。Mij机器1机器2作业121作业231作业323对于一个确定的作业调度,设Fij 是...回溯法之批处理作业调度
1. 问题描述
n个作业集合{1, 2, ..., n}。每个作业先由机器1处理,再由机器2处理。作业i需要机器j处理的时间为Mij 。
Mij
机器1
机器2
作业1
2
1
作业2
3
1
作业3
2
3
对于一个确定的作业调度,设Fij 是作业i在机器j上完成的具体时间。所有作业在机器2上完成的具体时间(时刻)之和f称为该作业调度的完成时间和。
要求:对于给定的n个作业,制定最佳作业调度方案(一个排列),使其完成时间和达到最小
2. 问题分析
3个作业的6种可能的调度方案是1-2-3;1-3-2;2-1-3;2-3-1;3-1-2;3-2-1;它们所相应的完成时间和分别是19,18,20,21,19,19。易见,最佳调度方案是1-3-2,其完成时间和为18。
Fi1、Fi2表示事件i分别在机器1和机器2上完成的时间。
作业顺序
Fi1
Fi2
f
begin
0
0
0
①
2
3
3
③
4
7
10
②
7
8
18
假设此时1-2-3的作业调度已经完成计算,遍历到了1-3-2的序列。
首先是①,将调用f1 += M[x[j]][1];表示作业1在机器1需要2时间才能完成,接下来使用f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + M[x[j]][2];比较F02 和 F11 的大小,即需要等待前一个作业在机器2完成计算才能在机器2开始本次作业,再使用F02 和 F11的较大值F11+作业2在机器2的工作时间1得到F12为3,在使用f += f2[i],将3赋值给f。
到③,调用f1 += M[x[j]][1];,F21变为2+2=4,再比较F12和F21,将较大的F21+3=7赋值给F22。f变为10。
到②,F31变为7,比较F22和F31,将7+1=8复制给F32,最终将f变为18,得到最终结果。
3. 代码求解
该问题的解空间:排列树:
使用到的全局变量:
M 各作业所需的处理时间
x 当前作业调度
bestx 当前最优作业调度
f2 机器2完成的处理时间
f1 机器1完成的处理时间
f 完成时间和
bestf 当前最优值
n 作业数
核心求解代码:
void BackTrack(int i) {
// i > n表示已经访问到叶子结点,即一个作业调度遍历完成
// 将此时的最优解暂时保存到bestx中
if (i > n) {
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
bestf = f;
}
} else {
// 若没找到此时的最优解,则对当前的求解树的子节点遍历求解
for (int j = i; j <= n; j++) {
// 上述的问题求解过程
f1 += M[x[j]][1];
f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + M[x[j]][2];
f += f2[i];
// 如果f小于当前的最小值,代表这个分支可以继续运算,否则直接裁去该分支,达到优化算法的目的
if (f < bestf) {
swap(i, j);
// 递归求解
BackTrack(i + 1);
// 递归运算后,需要回退到上一层排列树
swap(i, j);
}
// 本条路径求解结束后回退到原本的状态
f1 -= M[x[j]][1];
f -= f2[i];
}
}
}
4. 完整代码
/**
* 回溯法求解批处理作业调度问题
*
* 主要由BackTrack函数递归调用求解问题
* 使用bsetf保存最优解,bestx保存最优的作业调度序列
**/
#include
#include
#define MAXROW 4
#define MAXCOL 3
/**
* M 各作业所需的处理时间
* x 当前作业调度
* bestx 当前最优作业调度
* f2 机器2完成的处理时间
* f1 机器1完成的处理时间
* f 完成时间和
* bestf 当前最优值
* n 作业数
**/
int M[MAXROW][MAXCOL], x[MAXROW], bestx[MAXROW], f2[MAXROW], f1, f, bestf, n;
// 值交换函数
void swap(int i, int j) {
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
void BackTrack(int i) {
// i > n表示已经访问到叶子结点,即一个作业调度遍历完成
// 将此时的最优解暂时保存到bestx中
if (i > n) {
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
bestf = f;
}
} else {
// 若没找到此时的最优解,则对当前的求解树的子节点遍历求解
for (int j = i; j <= n; j++) {
f1 += M[x[j]][1];
f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + M[x[j]][2];
f += f2[i];
if (f < bestf) {
swap(i, j);
BackTrack(i + 1);
swap(i, j);
}
f1 -= M[x[j]][1];
f -= f2[i];
}
}
}
void main() {
n = 3;
bestf = INT_MAX;
M[1][1] = 2;M[1][2] = 1;
M[2][1] = 3;M[2][2] = 1;
M[3][1] = 2;M[3][2] = 3;
for (int i = 0; i <= n; i++) {
f2[i] = 0;
x[i] = i;
}
BackTrack(1);
printf("%d\n", bestf);
for (int i = 1; i <= n; i++) {
printf("%d ", bestx[i]);
if (i != n)
printf("-> ");
}
printf("\n");
system("pause");
}
-
回溯法 批处理作业调度_算法java实现--回溯法--批处理作业调度问题
2021-01-14 07:07:59批处理作业调度问题的java实现(回溯法)具体问题描述以及C/C++实现参见网址http://blog.csdn.net/liufeng_king/article/details/8764319/*** 批处理作业调度问题--回溯法(排列树)* @author Administrator**/public ...批处理作业调度问题的java实现(回溯法)
具体问题描述以及C/C++实现参见网址
http://blog.csdn.net/liufeng_king/article/details/8764319
/**
* 批处理作业调度问题--回溯法(排列树)
* @author Administrator
*
*/
public class FlowShop {
int n;//作业数
int f1;//机器1完成处理时间
int f;//完成时间和
int bestf;//当前最优值
int[][] m;//各作业所需的处理时间
int []x;//当前作业调度
int[] bestx;//当前最优作业调度
int[] f2;//机器2完成处理时间
public FlowShop(int n,int[][] m){
this.n=n;
this.m=m;
f1=0;
f=0;
bestf=10000;//给定初始值
bestx=new int[n+1];
x=new int[n+1];
//初始化,x[i]为原始排序
for(int i=1;i<=n;i++){
x[i]=i;
}
f2=new int[n+1];
}
public void swap(int[] x,int i,int j){
int temp=x[i];
x[i]=x[j];
x[j]=temp;
}
public void backtrack(int i){
if(i>n){
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestf=f;
}
else{
for(int j=i;j<=n;j++){
f1+=m[x[j]][1];//作业x[j]在第一台机器的时间
f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2];//f2[i]等于f2[i-1]和f1中较大者加上作业x[j]在第2台机器的时间
f+=f2[i];
if(f
swap(x,i,j);
backtrack(i+1);
swap(x,i,j);
}
f1-=m[x[j]][1];
f-=f2[i];
}
}
}
public static void main(String[] args) {
int n=3;
int[][] m={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};//m的下标从1开始,因此第一行的0和每一行第一列的0无用
FlowShop f=new FlowShop(n,m);
f.backtrack(1);
System.out.println("最优批处理作业调度顺序为:");
for(int i=1;i<=n;i++)
System.out.print(f.bestx[i]+" ");
System.out.println();
System.out.println("最优调度所需的最短时间为:"+f.bestf);
}
}
/*
运行结果:
最优批处理作业调度顺序为:
1 3 2
最优调度所需的最短时间为:18
*/
-
回溯法 批处理作业调度_回溯法——批处理作业调度
2020-12-24 08:32:20问题描述:给定n个作业的集合J=(J1,J2,... ,Jn)。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理,然后再由机器2...简单描述:对于给定的n个作业,指定最佳作业调度方案,使其完成时间... -
回溯法 批处理作业调度_回溯法之批处理作业调度问题
2020-12-24 08:32:26对于一个确定的作业调度,设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f是指把F2i将i从1-n求和,称为该作业调度的完成时间和。2、简单描述对于给定的n个作业,指定最佳作业调度方案,使... -
回溯法 批处理作业调度_批处理作业调度(回溯法)
2020-12-24 08:32:26对于一个确定的作业调度,设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和,称为该作业调度的完成时间和。即F12+F22+F32+…..+Fn2简单描述:对于给定的n个作业,指定最佳作... -
回溯法 批处理作业调度_算法设计与分析——批处理作业调度(回溯法)
2020-12-24 08:32:28之前讲过一个相似的问题流水作业调度问题,那一道题最开始用动态规划,推到最后得到了一个Johnson法则,变成了一个排序问题,有兴趣的可以看一下https://www.cnblogs.com/wkfvawl/p/11667092.html一、问题描述给定n... -
回溯法 批处理作业调度_使用回溯法解批处理作业调度问题<算法分析>
2020-12-24 08:32:17package saunfafenxi;import java.util.Scanner;... //作业总数static int[] T1 = new int[worknum];//第i个任务在机器一上面执行的时间static int[] T2 = new int[worknum];//第i个任务在机器一上面执行的时... -
批处理作业调度-回溯法
2018-12-06 23:46:17批处理作业调度不同于流水作业的地方在于要求所有作业完成的时间总和最小。packagetest; importjava.util.ArrayList; importjava.util.List; /** *Createdbyzuohaoon2018/12/9. *批处理作业调度 */ ... -
Java批处理调度_批处理作业调度问题·回溯法·java版
2021-03-08 06:21:27问题描述:/*************************************************************批处理作业调度给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一... -
批处理作业调度问题
2018-12-29 15:12:00给定n个作业的集合J={J1,J2,…,Jn}。每一个作业有两项任务分别在两台机器上完成。每个作业必须先由机器1处理,再由机器2处理。作业Ji需要机器j的处理时间为tji,i=1,2,…n,j=1,2。... 批处理作业调度问题... -
批处理作业调度回溯法
2019-07-23 22:32:45问题描述: 给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,...批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小。 例:设n=3,考虑以下实例: 这3个作业... -
题目1 多道批处理作业调度模拟程序
2020-04-14 16:48:38题目1 多道批处理作业调度模拟程序 一、目的: 熟悉作业调度算法及其实现 二、内容: 编写一个程序完成多道批处理作业调度 三、要求: 只考虑1个CPU的资源,其他资源不考虑 使用响应比高者优先算法 程序采用键盘输入... -
批处理作业调度(回溯)
2020-04-29 09:18:00批处理作业调度(回溯) 一、题目描述: 给定n个作业的集合J=(J1,J2, .. Jn)。每个作业J都有两项任务分别在两台机器上完成。每个作业必须先由机器1处理,再由机器2处理。作业i需要机器j的处理时间为tji(i=1,2, ..... -
回溯算法批处理作业调度问题
2019-11-25 21:33:221、问题描述 给定n个作业的集合J={j1,j2,j3,…jn},每一个作业都有两项任务分别在两台机器上完成。...批处理作业调度问题要求对于给定的N个作业,制定最佳作业调度方案,使其完成时间和达到最小。其中最... -
Java实现的批处理作业调度问题算法
2011-06-17 09:35:53这是一个用Java实现解决批处理作业调度问题的算法 -
分支界限法问题java_批处理作业调度-分支界限法
2021-03-08 03:25:22批处理作业调度-分支界限法package test;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;/*** Created by saishangmingzhu on 2018/12/6.* 批处理...