Я запускаю симуляцию алгоритма планирования заданий с двумя машинами. В настоящее время у меня 2 машины по 10 заданий в каждой, и у меня уже не хватает памяти ... Моя задача состоит в том, чтобы запустить 2 машины по 20 заданий в каждой; Судя по всему, я действительно очень далек от этой цели. Поэтому я надеюсь, что вы можете дать мне все советы и рекомендации по управлению памятью. Пожалуйста, не стесняйтесь бросать в меня что-нибудь.
Класс, который определяет атрибуты задания
public class Job {
final static int WAITING = 0;
final static int ASSIGNED = 1;
final static int COMPLETE = 2;
int num;
int machine;
int time;
int weight;
int due;
int resUse;
int resGain;
int parent;
int status = 0;//0:incomplete 1:assigned 2:complete
public Job() {
}
public Job(int num, int machine, int time, int weight, int due, int resUse, int resGain, int parent, int status) {
super();
this.num = num;
this.time = time;
this.machine = machine;
this.weight = weight;
this.due = due;
this.resUse = resUse;
this.resGain = resGain;
this.parent = parent;
this.status = status;
}
public String toString() {
return "n=" + num + " m=" + machine + " t=" + time + " w=" + weight + " d=" + due + " a=" + resUse + " b=" + resGain + " p=" + parent + " s=" + status;
}
}
Это мой класс "узел"
public class Machine {
int job[] = new int[Algo.NUM_MACHINES];
int remTime[] = new int[Algo.NUM_MACHINES];
int res = Algo.RESOURCE;
int time = 0;
int tardy = 0;
//Job jobTree[] = new Job[Algo.NUM_JOBS];
ArrayList<Integer> jobsFinished = new ArrayList<Integer>();
int id;
boolean visited = false;
Machine parent = this;//so that root node points to himself
ArrayList<Machine> children = new ArrayList<Machine>();
int duplicate = 0;//duplicate (sj-sj-sj-sj-...) flag
public Machine() {
jobsFinished.add(0);
}
/**
* cloning constructor
* @param shadow
*/
public Machine(Machine shadow) {
this.job = shadow.job.clone();
this.remTime = shadow.remTime.clone();
this.res = shadow.res;
this.time = shadow.time;
this.tardy = shadow.tardy;
this.parent = shadow;
this.duplicate = shadow.duplicate;
this.jobsFinished.addAll(shadow.jobsFinished);
}
/**
* method used to obtain machine state
* @return 0 if both machines are idle, 1 if one machine is busy, and 2 if both machines are
* busy
*/
public int getMachineState() {
if (remTime[0] == 0 && remTime[1] == 0)
return 0;
else if (remTime[0] != 0 && remTime[1] != 0)
return 2;
else
return 1;
}
public String toString() {
String jobStr = " job[]=";
for (int i = 0; i < job.length; i++)
jobStr += job[i] + " ";
String timeStr = "rem[]=";
for (int i = 0; i < remTime.length; i++)
timeStr += remTime[i] + " ";
return "id=" + id + jobStr + timeStr + "time=" + time + " parent=" + parent.id + " tardy=" + tardy + " res=" + res + " dup=" + duplicate;
}
}
Представляю плохо написанный алгоритм:
public class Algo {
final static int NUM_MACHINES = 2;
final static int NUM_JOBS = 20 + 1;
final static int RESOURCE = 15;
final int LOWER_BOUND = 1;
final int DUPLICATE = 1;
/*
p11 = 3 w11 = 7 d11 = 16 alpha = 3 beta = 6
p12 = 6 w12 = 1 d12 = 11 alpha = 7 beta = 16
p13 = 8 w13 = 3 d13 = 15 alpha = 8 beta = 3
p21 = 5 w21 = 6 d21 = 8 alpha = 7 beta = 3
p22 = 4 w22 = 10 d22 = 6 alpha = 6 beta = 2
*/
final Job jobTree[] = { new Job(0, 0, 999, 0, 999, 999, 0, 0, Job.COMPLETE),
new Job(1, 0, 95, 1, 246, 9, 8, 0, Job.WAITING),
new Job(2, 0, 10, 6, 184, 8, 6, 1, Job.WAITING),
new Job(3, 0, 63, 4, 367, 3, 9, 2, Job.WAITING),
new Job(4, 0, 71, 9, 353, 18, 19, 3, Job.WAITING),
new Job(5, 0, 10, 1, 305, 7, 14, 4, Job.WAITING),
new Job(6, 0, 97, 7, 239, 3, 2, 5, Job.WAITING),
new Job(7, 0, 83, 2, 132, 4, 5, 6, Job.WAITING),
new Job(8, 0, 24, 2, 354, 5, 10, 7, Job.WAITING),
new Job(9, 0, 59, 5, 371, 15, 2, 8, Job.WAITING),
new Job(10, 0, 10, 2, 260, 1, 15, 9, Job.WAITING),
new Job(11, 1, 36, 7, 145, 3, 13, 0, Job.WAITING),
new Job(12, 1, 88, 6, 270, 13, 19, 11, Job.WAITING),
new Job(13, 1, 30, 4, 229, 10, 16, 12, Job.WAITING),
new Job(14, 1, 47, 7, 118, 11, 6, 13, Job.WAITING),
new Job(15, 1, 88, 3, 180, 11, 19, 14, Job.WAITING),
new Job(16, 1, 40, 2, 141, 1, 9, 15, Job.WAITING),
new Job(17, 1, 18, 6, 245, 17, 5, 16, Job.WAITING),
new Job(18, 1, 18, 8, 250, 17, 18, 17, Job.WAITING),
new Job(19, 1, 6, 6, 207, 8, 6, 18, Job.WAITING),
new Job(20, 1, 53, 5, 159, 5, 6, 19, Job.WAITING) };
ArrayList<Machine> mLeastTardy = new ArrayList<Machine>();
Machine mRoot;
int index = 0;
int minTardy = 99999;
ArrayList<HashMap> mDuplicate = new ArrayList<HashMap>();
public void init() {
System.out.println("advAlgo3");
mRoot = new Machine();
mRoot.id = index++;
//mState.add(root);
}
public void run() throws Exception {
init();
//int minTardyStateIndex = 0;
Machine state = mRoot;
Machine minTardyState = null;
//begin algorithm
while (true) {
//System.out.println("run() " + state);
if (state.visited == false) {
switch (state.getMachineState()) {
case 0://both machines are free
for (Job job : jobTree)
scheduleJob(state, job);
break;
case 1:
scheduleWork(state);
for (Job job : jobTree)
scheduleJob(state, job);
break;
case 2:
scheduleWork(state);
break;
}
state.visited = true;
}
//begin min-tardy analysis
if (state.jobsFinished.size() == NUM_JOBS) {//if all jobs are finished
if (state.tardy < minTardy) {//if the schedule is least tardy
minTardyState = state;
minTardy = minTardyState.tardy;
mLeastTardy.clear();//renew the leastTardy path
while (minTardyState.id != 0) {
mLeastTardy.add(minTardyState);
minTardyState = minTardyState.parent;
}
}
}
//garbage collection
if (state.children.isEmpty()) {//if this is a leaf node (no children)
state.parent.children.remove(state);
}
//traverse to the next node
Machine nextState = state.parent;//default is to traverse up
for (Machine childState : state.children) {
if (childState.visited == false) {//but if you can find a child that hasn't been visited yet
nextState = childState;//traverse down
break;
}
}
state = nextState;
//when all nodes have been traversed
if (nextState.id == 0) {//if traverse back to root
boolean finish = true;
for (Machine child : nextState.children) {
if (child.visited == false)//if root still has an unvisited child
finish = false;
}
if (finish == true) {
break;
}
}
}//end algorithm
/*
//begin backward analysis
ArrayList<Machine> minTardy = new ArrayList<Machine>();
while (minTardyState.id != 0) {
minTardy.add(minTardyState);
minTardyState = minTardyState.parent;
}*/
//print path & gnatt chart
String gnattChart[] = new String[Algo.NUM_MACHINES];
for (int i = 0; i < gnattChart.length; i++)
gnattChart[i] = "";
state = mRoot;
for (int i = mLeastTardy.size() - 1; i >= 0; i--) {
Machine nextState = mLeastTardy.get(i);
System.out.println(nextState);
for (int j = 0; j < Algo.NUM_MACHINES; j++) {
if (nextState.remTime[j] == 0) {
int t = nextState.time - state.time;
for (int k = 0; k < Algo.NUM_MACHINES; k++) {
for (int l = 0; l < t; l++) {
if (state.job[k] < 10)
gnattChart[k] += state.job[k];
else {
gnattChart[k] += '#';
}
}
}
}
}
state = nextState;
}
System.out.println("# of Nodes=" + index);
System.out.println("# of Duplicates=" + mDuplicate.size());
System.out.println("Gnatt chart:");
for (String gnatt : gnattChart) {
System.out.println(gnatt);
}
//generateGraph();
}
private void scheduleJob(Machine parent, Job job) {
if (parent.res >= job.resUse) {//if there's enough resource to run the job
if (parent.remTime[job.machine] == 0) {//if the dedicated machine is idle
if (parent.jobsFinished.contains(job.parent)) {//if the preceeding job is complete
if (!parent.jobsFinished.contains(job.num)) {//but this isn't
//create a copy of the current state
Machine child = new Machine(parent);
child.id = index++;
//assign the job to the machine
child.job[job.machine] = job.num;
//set the machine's running time
child.remTime[job.machine] = job.time;
//deduct the resources
child.res -= job.resUse;
//update the job tree
//child.jobTree[job.num].status = Job.ASSIGNED;
//duplicate analysis
if (DUPLICATE == 1) {
child.duplicate++;
if (child.duplicate == NUM_MACHINES) {//if sj-sj
boolean new_dup = true;
for (HashMap dupmap : mDuplicate) {//compare against duplicate list
if (child.time == (Integer) dupmap.get("time")) {
int num_dup = 0;
for (int jNum : child.job) {
if (((ArrayList<Integer>) dupmap.get("dupJob")).contains(jNum)) {
num_dup++;
} else {
break;
}
}
if (num_dup == NUM_MACHINES) {
child.visited = true;
new_dup = false;
break;
}
}
}
if (new_dup) {//if this is a new combo, append this combo to the duplicate list
ArrayList<Integer> dup = new ArrayList<Integer>();
for (int jNum : child.job) {
dup.add(jNum);
}
HashMap dupmap = new HashMap();
dupmap.put("time", child.time);
dupmap.put("dupJob", dup);
//System.out.println(dupmap);
mDuplicate.add(dupmap);
}
}
}
//
parent.children.add(child);
//System.out.println("sj() " + child + " # " + job);
//add this state to the tree
//mState.add(child);
}
}
}
}
}
private void scheduleWork(Machine parent) {
//find the machine with the shortest remaining processing time
int shortestTime = 99999;
for (int i = 0; i < NUM_MACHINES; i++) {
if (parent.remTime[i] < shortestTime && parent.remTime[i] != 0) {
shortestTime = parent.remTime[i];
}
}
//schedule Work node for ALL machines working on a job with the shortest remaining processing time
for (int i = 0; i < NUM_MACHINES; i++) {
if (parent.remTime[i] == shortestTime) {//if this machine is working on a job with the shortest remaining processing time
Job finishingJob = jobTree[parent.job[i]];
//create a copy of the current state
Machine child = new Machine(parent);
child.id = index++;
//move the time pointer forward
child.time += shortestTime;
//increase tardiness
if (child.time > finishingJob.due) {
child.tardy += (child.time - finishingJob.due) * finishingJob.weight;
}
if (LOWER_BOUND == 1) {
if (child.tardy > minTardy) {
child.visited = true;
}
}
//return resources
child.res += finishingJob.resGain;
//free the machine
child.job[i] = 0;
for (int j = 0; j < NUM_MACHINES; j++)
if (child.remTime[j] > 0)
child.remTime[j] -= shortestTime;
//update the job tree
child.jobsFinished.add(finishingJob.num);
//reset the duplicate flag
if (DUPLICATE == 1) {
child.duplicate = 0;
}
//
parent.children.add(child);
//System.out.println("sw() " + child);
//add the state to the tree
//mState.add(child);
}
}
}
/*
private void generateGraph() throws Exception {
Undirectgraph ug = new Undirectgraph();
int stateNum = mState.size();
ug.createMatrix(stateNum);
for (int i = 0; i < stateNum; i++) {
int childNum = mState.get(i).children.size();
for (int j = 0; j < childNum; j++)
ug.addEdge(i + 1, mState.indexOf(mState.get(i).children.get(j)) + 1, mState.get(i).children.get(j).tardy);
}
System.out.println(ug.toGraphviz());
}*/
}
И, наконец, основной класс, который выполняет алгоритм
public class Main {
public static void main(String args[]) throws Exception {
Algo program = new Algo();
program.run();
}
}