问题描述：

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

批处理作业调度

给定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

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

实验目的

加深对作业概念的理解；

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

预备知识

.

实验内容

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

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

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

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博客作者塞上名猪的原创作品，如需转载，请注明出处，否则将追究法律责任