精华内容
下载资源
问答
  • 2021-01-14 07:07:59

    批处理作业调度问题的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

    */

    更多相关内容
  • 这是一个用Java实现解决批处理作业调度问题的算法
  • 本例是java实现的批处理作业调度程序,采用的是回溯法,排列集合的方式,参考书籍为:算法设计与分析
  • 问题描述:/*************************************************************批处理作业调度给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一...

    问题描述:

    /*************************************************************

    批处理作业调度

    给定n个作业的集合{J1,J2,…,Jn}。

    每个作业必须先由机器1处理,然后由机器2处理。

    作业Ji需要机器j的处理时间为tji。

    对于一个确定的作业调度,设Fji是作业i在机器j上完成处理的时间。

    所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。

    f = F21 + F22 + F23 + ... + F2n

    批处理作业调度问题要求对于给定的n个作业,

    制定最佳作业调度方案,使其完成时间和达到最小。

    *************************************************************/

    public class FlowShop

    {

    int n,         //作业数;

    f1,        //机器1完成处理时间;

    f,         //完成时间和;

    bestf;     //当前最优值;

    int [][]m;      //各作业所需的处理时间;

    int []x;        //当前作业调度;

    int []bestx;    //当前最优作业调度;

    int []f2;       //机器2完成处理时间;

    private  void backtrack(int i)

    {

    if(i>n)

    {

    for (int j=1;j<=n;j++)

    {

    bestx[j]=x[j];

    System.out.print(x[j]+" ");

    }

    System.out.println();

    bestf=f;

    System.out.println("每条深度优先搜索结果为:"+bestf);

    }

    else

    for(int j=i;j<=n;j++)

    {

    f1+=m[x[j]][0];

    f2[i]=((f2[i-1]>f1)? f2[i-1]:f1)+m[x[j]][1];

    f+=f2[i];

    //      if(f

    if(true)

    {

    MyMath.swap(x,i,j);

    backtrack(i+1);

    MyMath.swap(x,i,j);

    }

    f1-=m[x[j]][0];

    f-=f2[i];

    }

    }

    public void ShowTest()

    {

    n=3;

    bestf=Integer.MAX_VALUE;

    f1=0;

    f=0;

    int [][]m={{0,0},{2,1},{3,1},{2,3}};

    int []x={0,1,2,3};

    int []bestx={0,1,2,3};

    f2=new int[4];

    this.m = m;

    this.x=x;

    this.bestx=bestx;

    this.f2=f2;

    backtrack(1);

    System.out.println("当前最优值:"+bestf);

    System.out.println("当前最优作业调度");

    for(int i=1;i<=n;i++)

    {

    System.out.print(bestx[i]+"  ");

    }

    }

    public static void main(String[] args)

    {

    // TODO Auto-generated method stub

    FlowShop fs=new FlowShop();

    fs.ShowTest();

    }

    }

    class MyMath

    {

    public MyMath(){}

    public static int[] swap(int[] x,int i,int j)

    {

    // int[] returnString=new int[3];

    int ss;

    ss=x[j];

    x[j]=x[i];

    x[i]=ss;

    return x;

    }

    }

    展开全文
  • 批处理系统的作业调度java实验 批处理系统的作业调度实验目的加深对作业概念的理解;深入了解批处理系统如何组织作业、管理作业和调度作业。预备知识.实验内容编写程序完成批处理系统中的作业调度,要求采用响应比高...

    批处理系统的作业调度java

    实验 批处理系统的作业调度

    实验目的

    加深对作业概念的理解;

    深入了解批处理系统如何组织作业、管理作业和调度作业。

    预备知识

    .

    实验内容

    编写程序完成批处理系统中的作业调度,要求采用响应比高者优先的作业调度算法。实验具体包括:首先确定作业块的内容和组成方式;然后完成作业调度;最后编写主函数,对所做工作进行测试。

    import java.util.Scanner;

    public class JCB {

    public String name; //作业名

    public int length; //作业长度

    public int print; //打印机数量

    public int tape; //磁带机数量

    public int runTime;

    public int waitTime;

    public int next; //指针

    }

    class Action{

    public final int n=10; //后备队列中JCB的最大数量

    JCB[] jTable=new JCB[n]; //作业表

    public int jCount; //作业表中当前作业数量

    public int head; //作业表头指针

    //初始化函数

    public void Init()

    {

    head=-1;

    jCount=0;

    }

    //入队函数

    public void pushQueue(JCB jcb){

    if(jCount>=n)

    {

    System.out.println("队列已满!不能再加入!");

    return ;

    }

    if(head==-1)

    head=0;

    //System.out.println(jTable[jCount]);

    jTable[jCount]=new JCB();

    jTable[jCount].length=jcb.length;

    jTable[jCount].name=jcb.name;

    jTable[jCount].print=jcb.print;

    jTable[jCount].tape=jcb.tape;

    jTable[jCount].runTime=jcb.runTime;

    jTable[jCount].waitTime=jcb.waitTime;

    jTable[jCount].next=-1;

    jCount++;

    }

    //出队函数

    public void popQueue(int num)

    {

    if(jCount==0)

    {

    System.out.println("空的队列!不能出队!");

    return ;

    }

    if(num>=jCount)

    {

    System.out.println("队列中不存在该元素!");

    return ;

    }

    if(jCount==1)

    {

    head=-1;

    jTable[0].next=-1;

    jCount=0;

    }else{

    jTable[num-1].next=jTable[num].next;

    jTable[num].next=-1;

    jCount--;

    }

    }

    public int memory=64*1024; //主存大小64MB

    public int tape=4; //磁带机数量

    public int print=2; //打印机数量

    //作业调度函数

    public void dispatch()

    {

    int currJcb,maxJcb;

    double currJcbRate,maxJcbRate;

    while(head!=-1)

    {

    currJcb=maxJcb=head;

    currJcbRate=maxJcbRate=0;

    //找出响应比最大的作业

    while(true)

    {

    //找出满足资源的作业

    if(jTable[currJcb].length<=memory&&jTable[currJcb].tape<=tape&&jTable[currJcb].print<=print)

    {

    //计算响应比

    currJcbRate=(double)jTable[currJcb].waitTime/jTable[currJcb].runTime

    展开全文
  • 用动态规划、分支限界、回溯解决01背包、批处理作业调度问题
  • 操作系统小作业
  • 批处理作业调度-分支界限法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.* 批处理...

    批处理作业调度-分支界限法

    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.

    * 批处理作业调度

    */

    public class BatchJobSchedulingProblem {

    public static void main(String[] arg) {

    new BatchJobSchedulingProblem().branchAndBoundMethod();

    }

    /**

    * 分支界限法-优先队列式

    * 优先队列式求解时,到达第一个没有子结点的活结点时,即为最优解

    */

    public void branchAndBoundMethod() {

    List taskList=new ArrayList<>();

    taskList.add(new Task("J1",2,1));

    taskList.add(new Task("J2",3,1));

    taskList.add(new Task("J3",2,3));

    Node root=new Node();

    root.setT1(0);

    root.setT2(0);

    root.setSt(0);

    for (Task task:taskList){

    Node node=new Node();

    node.setTask(task);

    node.setT1(task.getA());

    node.setT2(task.getA()+task.getB());

    node.setSt(node.getT2());

    root.getChildNodeList().add(node);

    }

    List nodeList=new ArrayList<>();

    nodeList.add(root);

    while (nodeList.size()>0){

    addNode(nodeList.get(0),nodeList);

    Collections.sort(nodeList, new Comparator() {

    @Override

    public int compare(Node o1, Node o2) {

    return o1.getSt()-o2.getSt();

    }

    });

    }

    }

    public void addNode(Node parentNode,List nodeList){

    //移除活结点

    nodeList.remove(parentNode);

    int t1=parentNode.getT1();

    int t2=parentNode.getT2();

    int st=parentNode.getSt();

    if (parentNode.getChildNodeList().size()==0){

    //第一次执行到这里时其实已经得到最优解

    for (Task task:parentNode.getTaskList()){

    System.out.print(task.getName()+",");

    }

    System.out.println();

    System.out.println(parentNode.getSt());

    return;

    }

    for (Node node:parentNode.getChildNodeList()){

    Task task=node.getTask();

    Node newNode=new Node();

    int nextt1=t1+task.getA();

    int nestt2=(t2-t1)>task.getA()?t2+task.getB():nextt1+task.getB();

    newNode.setTask(task);

    newNode.setT1(nextt1);

    newNode.setT2(nestt2);

    newNode.setSt(st+nestt2);

    List newTaskList=new ArrayList<>();

    newTaskList.addAll(parentNode.getTaskList());

    newTaskList.add(task);

    newNode.setTaskList(newTaskList);

    List newChildNodeList=new ArrayList<>();

    newChildNodeList.addAll(parentNode.getChildNodeList());

    newChildNodeList.remove(node);

    newNode.setChildNodeList(newChildNodeList);

    nodeList.add(newNode);

    }

    }

    class Node{

    private Task task;

    private int t1;

    private int t2;

    private int st;

    private List childNodeList=new ArrayList<>();

    private List taskList=new ArrayList<>();

    public List getChildNodeList() {

    return childNodeList;

    }

    public void setChildNodeList(List childNodeList) {

    this.childNodeList = childNodeList;

    }

    public Task getTask() {

    return task;

    }

    public void setTask(Task task) {

    this.task = task;

    }

    public int getT1() {

    return t1;

    }

    public void setT1(int t1) {

    this.t1 = t1;

    }

    public int getT2() {

    return t2;

    }

    public void setT2(int t2) {

    this.t2 = t2;

    }

    public int getSt() {

    return st;

    }

    public void setSt(int st) {

    this.st = st;

    }

    public List getTaskList() {

    return taskList;

    }

    public void setTaskList(List taskList) {

    this.taskList = taskList;

    }

    }

    class Task{

    private String name;

    private int a;

    private int b;

    public Task(String name, int a, int b) {

    this.name = name;

    this.a = a;

    this.b = b;

    }

    public String getName() {

    return name;

    }

    public void setName(String name) {

    this.name = name;

    }

    public int getA() {

    return a;

    }

    public void setA(int a) {

    this.a = a;

    }

    public int getB() {

    return b;

    }

    public void setB(int b) {

    this.b = b;

    }

    }

    }

    ©著作权归作者所有:来自51CTO博客作者塞上名猪的原创作品,如需转载,请注明出处,否则将追究法律责任

    展开全文
  • 批处理作业调度 问题描述 每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理,然后再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理...
  • 一.问题描述 给定n个作业的集合J=(J1, J2, … , Jn)。每一作业Ji都有两项 任务要分别在2台机器上完成. 每一作业须先由机器l处理, 再由机器2...批处理作业调度问题要从n个作业的所有排列中找出有最小完成时间和的作业
  • 回溯法批处理作业调度问题(java实现) 问题描述:设有 n个作业{J1,J2,……Jn}需要处理,每个作业Ji(1≤ i ≤ n)都有两项任务组成。两项任务需要分别在2台机器即机器1和机器2上处理。要求每个作业Ji 的第一项...
  • 【分支限界法】批处理作业调度问题 给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理的时间...
  • 1、问题描述 每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理,然后再...批处理作业调度旨在求出使其完成时间和达到最小的最佳调度序列; 流水线调度问题旨在求出使其最后一个作业的完成时
  • 批处理作业调度分支限界算法(1)问题分析:给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理...
  • n个作业{1, 2, …, n}要在两台机器上处理,每个作业必须先由机器1处理,然后再由机器2处理,机器1处理作业i所需时间为ai,机器2处理作业i所需时间为bi(1≤i≤n),批处理作业调度问题要求确定这n个作业的最优处理...
  • import java.util.Scanner;public class shiyan5 {static int worknum=3; //作业总数static int[] T1 = new int[worknum];//第i个任务在机器一上面执行的时间static int[] T2 = new int[worknum];//第i个任务在机器...
  • 批处理作业调度问题【回溯法】

    千次阅读 2020-03-20 14:01:25
    对于一个确定的作业调度,设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和,称为该作业调度的完成时间和。即F12+F22+F32+…+Fn2 简单描述: 对于给定的n个作业,指定最佳作...
  • c++实现的批处理作业调度问题·优先队列式分支限界法·回溯法包括了FlowShop和make类模板,有测试数据data
  • 批处理作业调度问题

    千次阅读 2017-07-17 15:13:09
    Name: 批处理作业调度问题 Copyright: free Author: 巧若拙 Date: 17-07-17 14:12 Description: 问题描述:  给定n个作业,集合J=(J1,J2,J3)。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业...
  • 给定n个作业的集合J=(J1,J2,…,Jn)。每一个作业Ji都有两项任务分别是在2台机器上完成。每个作业必须先由机器1处理,然后再由机器2处理。作业Ji需要的处理事件时Tji,i=1,2,…n;j=1,2。 例: 考虑如下情况: 作业 ...
  • 问题描述:给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由...批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小。 这3个作业的6种可能的调度方案是1,2...
  • 问题描述 给定 n 个作业的集合 j = {j1, j2, ..., jn}。每一个作业 j[i] 都有两项任务分别在两台机器上完成。每一个作业必须先由机器1 ...调度,设F[j][i]是作业 i 在机器 j 上的完成处理的时间。所
  • ******##1这是课程作业的简单分享 ******##2肯定会有地方对特殊的数据没有考虑到,欢迎改进 ******##3使用的 java version "1.8.0_131",eclipse上编辑 设计要求 1. 用可视化编程工具编制程序,在机器上调试运行,...
  • import java.util.*; public class FlowShop { static int n; // 作业数 static int f1; // 机器1完成处理时间 static int f; // 完成时间和 static int bestf; // 当前最优值 static int[][] m; // 各作业所...
  • 批处理作业调度问题的java实现(优先队列式分支限界法) 具体问题描述以及C/C++实现参见网址 http://blog.csdn.net/liufeng_king/article/details/8952161
  • 回溯法解决批处理作业调度问题

    千次阅读 2016-06-16 22:33:48
    唉,这是作为一个失败的开端。但是,我不害怕失败的!今天稍微晚点睡觉,因为中午多睡啦~最近被王晓东老师的《计算机算法设计与分析》(第4版)折磨得够呛。不会说些文雅的话,这的确是事实。...每一个作业Ji都有两项任
  • 具体的要求是这样的:编写程序完成批处理系统中的作业调度,要求采用响应比高者优先的作业调度算法。实验具体包括:首先确定作业控制块的内容,作业控制块的组成方式;然后完成作业调度;最后编写主函数对所作工作...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,029
精华内容 3,211
关键字:

批处理作业调度java

java 订阅