每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理,然后再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f=F2i,称为该作业调度的完成时间和。此时要找出最小的完成时间和
给出一个例子:
根据问题描述可知,需要计算出每个作业在机器二完成的时间,计算例子如下(以下以作业调度为1.2.3为例)
由上图可知
作业1在机器2完成处理时间是3
作业2在机器2完成处理时间是6(要算上前面作业1在机器2处理时占用的时间)
作业2在机器2完成处理时间是10
因此完成时间和是19
从例子中可以看出需要变量m[][](各个作业在机器一机器二的处理时间),f1(机器一的处理时间),f2[i](第i个作业在机器二的处理时间),f(完成时间和),通过比较f1和f2[i-1],取其大加上该作业在机器二的处理时间成为f2[i]
各个作业的不同排列就是该题的解空间
例题的解空间为{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}
由例题可知,该解空间结构为排列数
因为要找出最小的,所以在不可能出现最优解的时候即可进行剪枝,所以只需f<bestf即可
package FlowShopProblem;
import java.util.Scanner;
public class FlowShop {
//以下涉及到数组的变量,第一个元素即第0个都是不会用到的,所以数组元素个数都需+1
int n;//作业个数
int f;//当前作业完成时间总和
int bestf;//当前最优完成时间和
int[] x;//当前作业调度
int[] bestx;//最优作业调度
int[][] m;//各个作业需要的时间
int f1;//机器一处理的时间
int[] f2;//机器二处理的时间
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];
}
//在Java中交换数组的两个元素下标位置不能直接进行交换
//要通过引用来交换,直接交换没有指向同个对象(数组)
private void swap(int[] x,int i, int j) {
int temp=x[i];
x[i]=x[j];
x[j]=temp;
}
public void backtrack(int t) {
if(t>n) {
//此处不需要再次判别f<bestf,因为在进行backtrack(t+1)前就已经判别了
for(int i=1;i<=n;i++) {
bestx[i]=x[i];
}
bestf=f;
}
else {
for(int j=t;j<=n;j++) {
f1+=m[x[j]][1];
f2[t]=((f2[t-1]>f1)? f2[t-1]:f1)+m[x[j]][2];//特别注意在当t=1时,f2[t-1]需赋值为0,这也是为什么不从第一个元素记录实际数据
f+=f2[t];
if(f<bestf) {
swap(x,t,j);
backtrack(t+1);
swap(x,t,j);
}
f1-=m[x[j]][1];
f-=f2[t];
}
}
}
public static void main(String[] args) {
System.out.println("请输入作业个数:");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[][] m= new int[n+1][3];//m的下标从1开始,因此第一行的0和每一行第一列的0无用
System.out.println("请输入作业在机器一和机器二的处理时间\n(第一行全输入0,每一行第一列输入0)");
for(int i=0;i<m.length;i++)
for(int j=0;j<3;j++)
m[i][j]=sc.nextInt();
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("最优调度所需的最短时间为:\n"+f.bestf);
}
}
文章浏览阅读349次,点赞10次,收藏11次。2.SQL语句可以使用空格/缩进来增强语句的可读性。1.SQL语句可以单行或多行书写,以分号结尾。3.MySQL数据库的SQL语句不区分大小写。
文章浏览阅读519次。打开vs,工具-->选项-->项目和解决方案-->在右侧选中"总是显示解决方案"-->确定_vs 无法创建resx清单名称
文章浏览阅读4.2k次,点赞8次,收藏15次。CMC曲线(累计匹配曲线)CMC曲线在人脸识别,行人重识别等领域使用的非常多,但却很少有文章去详细的介绍CMC曲线,这是我在researchgate网页上某个博主主页上找到的关于CMC曲线的介绍,个人觉得通过例子讲解的形式来介绍CMC使得更加通俗易懂,让人一看就明白。以下是原文:I think that understanding a CMC curve is much easierb..._cmc曲线
文章浏览阅读1.3k次,点赞42次,收藏41次。CompletableFuture的异步执行通过ForkJoinPool实现,ForkJoinPool在于可以充分利用多核CPU的优势,把一个任务拆分成多个小任务,把多个小任务放到多个CPU上并行执行,当多个小任务执行完毕后,再将其执行结果合并起来。
文章浏览阅读958次。objShell.SendKeys “{F5}” ’ 模拟鼠标中键点击。WScript.Sleep(300000) ’ 延时5分钟。_windows防锁屏bat脚本
文章浏览阅读2.3k次。CentOS快速安装配置NVIDIA Container Toolkit_nvidia container toolkit
文章浏览阅读1.4k次。一、数据结构与线程构造方法由于已经看到了ThreadPoolExecutor的源码,因此很容易就看到了ThreadPoolExecutor线程池的数据结构。图1描述了这种数据结构。图1 ThreadPoolExecutor 数据结构其实,即使没有上述图形描述ThreadPoolExecutor的数据结构,我们根据线程池的要求也很能够猜测出其数据结构出来。_线程之 1.7 doacquiresharedinterruptibly解析
文章浏览阅读4.8w次,点赞3次,收藏21次。快速获取图片的宽高其实是为了预先做好排版样式布局做准备,通过快速获取图片宽高的方法比onload方法要节省很多时间,甚至一分钟以上都有可能,并且这种方法适用主流浏览器包括IE低版本浏览器。我们一步一步进入这个过程。一、简陋的获取图片方式1234567891011_图片 src和onload 哪个快
文章浏览阅读6.3k次。严重: 在路径为/book的上下文中,Servlet[jsp]的Servlet.service()引发了具有根本原因的异常java.lang.ClassNotFoundException:这种报错,除了其他人的:还有一种可能:名字不一样,哪怕是空格哪怕是一个空格!..._严重: 在路径为/bookmanage的上下文中,servlet[jsp]的servlet.service()引发了具
文章浏览阅读6.2k次。frida-ios-dump源码地址:GitHub - AloneMonkey/frida-ios-dump: pull decrypted ipa from jailbreak devicefrida-ios-dump是基于frida开发的一键砸壳工具,需要配置frida环境手机配置1)越狱状态2)安装openssh3)安装fridaMac配置1)安装frida,命令行:sudo pip install frida-tools (没有安装pip的话需要先安装pip)_ios砸壳需要 闪退怎么砸
文章浏览阅读2.6k次,点赞3次,收藏2次。1.制作系统应用程序。 ios的程序分为mobile和root权限模式,我们一般用xcode开发的app取得的是mobile权限,但是ios越狱后安装的app如:Cydia、91助手、PP助手等均为系统级应用程序。系统级app的好处是:用不无法手动删除、取得完全的root权限、可设置开机启动项等等功能。通过xcode打包的ipa是无法安装成为系统app的,所以我们需要另外一种打包方式:_depends libundirect.depends firmware
文章浏览阅读254次,点赞5次,收藏2次。继承1. 继承的基本概念1.1 继承的定义1.2 继承基类成员访问方式的变化2. 基类和派生类对象赋值转换3. 继承中的作用域1. 继承的基本概念继承是面向对象程序设计使代码复用的最重要的手段,允许在保持原有类特性的基础上进行扩展,增加功能,产生新的类,称为派生类/子类。继承是类设计层次的复用。1.1 继承的定义派生类 : 继承方式 基类class Student : public Person1.2 继承基类成员访问方式的变化父类成员在子类中的访问权限(除过父类中的私有成员):_什么是赋值转换