给定n个作业的集合J=(J1,J2,...,Jn)。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先由机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji；i=1,2,...n；j=1,2。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。则所有作业在机器2上完成处理的时间和f=F21+F21+...+F2n成为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
分析：批处理作业调度问题要从n个作业的所有排列中找出最小完成时间和的作业调度，所以批处理作业调度的解空间是一颗排列树。按照回溯法搜索排列树的算法框架，设开始时x=[1,2,...,n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列构成。
【算法和数据结构|【回溯法】批处理作业调度问题】递归回溯
#include
using namespace std;
class Flowshop;
int Flow(int **,int, int []);
void Swap(int &a, int &b)
{
int temp=a;
a=b;
b=temp;
}class Flowshop
{
friend int Flow(int **,int, int []);
private:
void Backtrack(int i);
int **M,//各作业所需的处理时间
*x,//当前作业调度
*bestx,//当前最优作业调度
*f2,//机器2完成处理的时间
f1,//机器1完成处理的时间
f,//完成时间和
bestf,//当前最优值
n;
//作业数
};
void Flowshop::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)// 因为问题的解空间是一颗由x[1:n]的所有排列构成的排列树
{ // 所以第i次所调度的作业是从序号为i到n的作业中选择一个座位子树分支
f1 += M[x[j]][1];
// +第i次所调度的作业在机器1上的处理时间
f2[i] = ((f2[i-1]>f1) ? f2[i-1] : f1) + M[x[j]][2];
f += f2[i];
//+第i次所调度的作业在机器2上的处理时间
if(fin_avail()+1);
return 0;
} 推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络