关键词：
问题：
给定n个作业的集合J1,J2,…,Jn。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需(1≤i≤n)要机器j(1≤j≤2)的处理时间为 tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为 该作业调度的完成时间和。
要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
| tji | 机器1 | 机器2 |
|---|---|---|
| 作业1 | 2 | 1 |
| 作业2 | 3 | 1 |
| 作业3 | 2 | 3 |
分析：
由于机器有两个，每个作业必须从机器1处理，再到机器2处理，所以会两个作业同时处理，例如对上面的表格按照（1,2,3）的顺序调度：
(括号内代表作业序号)
机器1 机器2
2(1)
3(2) 1(1)
2(3) 1(2)
3(3)
每一个作业的处理时间 = 机器2的处理时间 + 机器2等待处理的时间（包括了之前作业的时间 和 本作业在机器1处理的时间）
所以我们求作业的处理时间，就是求该作业从开始到机器2处理完的时间：
作业1的处理时间：2+1 = 3
作业2的处理时间：2 + 3 + 1 = 6 （作业1的在机器1的处理时间，作业2的在机器1的处理时间 和 作业1在机器2的处理时间的较大时间（因为两者是同时进行的），作业2在机器2的处理时间）
作业3的处理时间：2 + 3 + 2 + 3 = 10所以（1,2,3）顺序的作业调度得到的作业调度时间为19
再看问题，问题要求得到最优作业调度方案和最小调度时间，也就是要得到使作业调度时间最小的作业处理顺序
因此这是一个 排列树 的问题，用排列树的算法框架：
代码实现
排列树的算法框架有两种实现方式：
（1）用visted方式
#define MAX 200
#include<iostream>
using namespace std;
int number;//作业数量
int x1[10];//作业在机器1运行的时间
int x2[10];//作业在机器2运行的时间
int sum = 0;//作业完成的总时间
int bestsum = MAX;//作业完成的最优时间
int order[10];//作业完成的次序,要用于交换
int bestorder[10];//作业完成的最优的顺序
int f1 = 0;//机器1累计的时间
int f2[10];//作业在机器2处理完累计的时间，即每一个作业的调度时间
int vis[10];//记录作业以否已被选
void backtrack(int cur) //cur表示正在赋值的位置，cur+1去到下一层子节点，i递增，在当前层遍历兄弟节点
if(cur>number)
for(int i=1; i<=number; i++) bestorder[i]=order[i];
bestsum=sum;
else
for(int i=1; i<=number; i++) //遍历number，尝试填第一位
if(!vis[i])
vis[i] = 1;
f1+=x1[i];
//本作业的在机器1的处理时间 和 上一个作业在机器2的处理时间的较大时间（因为两者是同时进行的）
f2[cur]=( f2[cur-1] > f1 ? f2[cur-1] : f1) + x2[i];
sum+=f2[cur];
order[cur] = i;
if(sum<bestsum) //剪枝，如果当前sum都大于bestsum了，则不再遍历此节点
backtrack(cur+1);
//每计算一次，为了不影响父节点和兄弟节点，运算完都要复位
sum-=f2[cur];
f1-=x1[i];
vis[i] = 0;
int main()
cout << "请输入作业的数量： ";
cin >> number;
int i;
cout << "请输入每个作业在机器1的运行时间：" << endl;
for(i=1; i<=number; i++)
cin >> x1[i];
cout << endl << "请输入每个作业在机器2的运行时间：" << endl;
for(i=1; i<=number; i++)
cin >> x2[i];
//初始化第一个序列，从1开始到number
for(i=1; i<=number; i++)
order[i] = i;
backtrack(1);
cout<<"最节省的时间为："<<bestsum<<endl;
cout<<"对应的方案为：";
for(i=1;i<=number;i++) cout<<bestorder[i]<<" ";
cout<<endl;
（2）用swap交换方式
除了backtrack，其它代码都没有改变，只贴出backtranck函数的代码：
void backtrack(int cur)
//到达边界
if(cur > number)
for(int i=1; i<=number; i++)
bestorder[i] = order[i];
bestsum = sum;
else
//cur表示正在赋值的位置，cur+1去到下一层子节点，i递增，在当前层遍历兄弟节点
for(int i=cur; i<=number; i++)
f1 += x1[order[i]];
f2[cur] = (f2[cur - 1] > f1 ? f2[cur -1] : f1) + x2[order[i]];
sum += f2[cur];
/*例如cur为2，i=3时，表示正在为作业队列的第2个位置赋作业3的值，所以此时的队列作业顺序应该是1，3,2, 所以要把i和cur的位置换掉；
同理例如cur为1，i=2时，表示正在为作业队列的第1个位置赋作业2的值，此时的顺序是2，1,3，好好理解这一点
swap函数就是要做这个事情
*/
swap(order[cur], order[i]);
if(sum < bestsum)//剪枝，如果当前sum都大于bestsum了，则不再遍历此节点
backtrack(cur+1);
swap(order[cur], order[i]);
sum -= f2[cur];
f1 -= x1[order[i]];
输入上面表格的数据，得出结果：
实验4贪心法（作业调度问题）(代码片段)
1.问题的已知设有n个独立的作业1,2,…,n，由m台相同的机器M1,M2,…,Mm进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。2.所求的目标要求给... 查看详情
算法与程序设计：回溯法
目录背景一、概念1.1回溯法的算法框架1.2详解说明二、举例2.1批作业调度问题2.2装载问题背景一、概念回溯法有“通用解题法”之称，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法... 查看详情
c_cpp【分支限界法】批处理作业调度(代码片段)
多机调度问题
【问题】设有n个独立的作业{1,2,3，...，n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。多机... 查看详情
最佳调度问题_分支限界法(代码片段)
...首先列个七乘三的二维数组了解算法思路： 我们知道回溯法其实是穷举法加剪枝函数，我们的函数用到递归，层层返回。一共七层，每层的除去叶子节点都有三个孩子每搜索到叶子节点就更新一次maxnum值（小于maxnum则更新）... 查看详情
处理机调度与死锁
...、处理机调度的层次 2.1高级调度 高级调度又称为作业调度或长程调度，主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存，调度的对象是作业。 作业，包含了程序、数据、作业说明 查看详情
拉丁矩阵问题利用回溯法的c++实现方案
...后查看。1.题目要求2.算法思想这个题目基本思想是利用回溯法，对于m行n列，本质上就是一个二维数组，我们可以将问题的解写成x[1],x[2],x[3]…x[m*n],那么对于每个点x[i]的取值实际上是[1,n],套用回溯法的算法框架，... 查看详情
八皇后（回溯法）(代码片段)
...式，沿行、列、对角线都可以攻击其它皇后基本思想使用回溯法（穷举法）所有的回溯问题都是由三个步骤组成：choose、explore、unchoose因此对每个问题需要知道： choose what？ 对于这个问题，我们选择每个字... 查看详情
作业调度算法
...序完成的。 处理机调度 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度（也称为高级调度）和进程调度（也称为低级调度）两个过程才... 查看详情
操作系统-处理机调度
...层次高级调度高级调度的调度对象是作业，只要用于多道批处理程序，在分时和实时系统中不设置高级调度作业作业是一个比程序更为广泛的概念，不仅包含了通常的程序和数据，还配有一份作业说明书，它和进程，线程一样有... 查看详情
模拟处理机作业调度---短作业优先调度算法(代码片段)
短作业优先调度原理短作业优先调度算法是指对短作业优先调度的算法。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。算法流程图 JCB代表一个作业，JCB的结构... 查看详情
三级调度
... 高级调度，称作业调度或长程调度(Long-termScheduling)。在批处理操作系统中，作业首先进入系统在辅存上的后备作业队列等候调度，因此，作业调度是必须的。它将按照系统预定的调度策略，决定把后备队列作业中的哪些作业调... 查看详情
Windows 2008 服务器任务调度程序不运行 .bat 批处理作业 [关闭]
】Windows2008服务器任务调度程序不运行.bat批处理作业[关闭]【英文标题】：Windows2008servertaskschedulerdoesnotrun.batbatchjob[closed]【发布时间】：2011-07-0209:21:39【问题描述】：我在Windows2008服务器上有一个批处理文件，当从命令行调用它... 查看详情
进程调度算法
...AFCFS调度算法属于不可剥夺算法。从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略... 查看详情
os中处理机调度模型和调度算法
...调度模型和调度算法调度层次1.1.高级调度（长程调度，作业调度）功能：依据某种算法。把在外存队列上处于后备队列的那些作业调入内存。以作业为操做对象。作业：比程序更为广泛的概念，不仅包括通常的程序和数据。还... 查看详情
回溯法
什么是回溯法最笨的搜索法是穷举搜索，在穷举搜索的基础上，提出了一些启发式的搜索方法。回溯法的本质就是搜索，通过剪枝策略，提高搜索的效率。回溯法也称为试探法，在搜索过程中向前试探，走不通时向后回溯。适用... 查看详情
（贪心）多机调度问题
某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间。 输入第... 查看详情
每天一个知识点：贪婪算法——一个简单的调度问题
...是使用非预占调度(nonpreemptivescheduling)：即一旦开始一个作业，就必须把该作业运行完。假设现在有四个作业：该调度总的代价C为即：可以看到，第一个求和与作业的排序无关，因此只有第二个求和影响到总开销。设在一个排序... 查看详情