# Implementation of Nearest-neighbour algorithm (single machine schedueling)

**843853**Aug 18, 2009 2:34 PM

Hi,

I am a student business engineering and I have to write a program to solve a 'single machine schedueling problem with seqeunce dependent setup-times'. I have written the code but I still have some problems that I can't solve. I don't know what to do anymore and my due-date is coming closer and closer so I would be EXTREMELY gratefull if somebody could help me out a little... (it is probably not that hard for an experienced programmer but it takes a while to explain the problem)

What we get is this: a certain number of jobs (nrJobs), a matrix with the process time of each job (processTime[]), a matrix with the inital setup times for each job (initSetupTime[]) and finally a 2 dimensional matrix with the setuptimes between all jobs (setupTime[][]; for example, on place [2][4] of the matrix is the setup time that is needed to prepare job 5 after we have finished job 3). Something like this:

i/j 1 2 3 4 … n -> the number of the jobs

0 s01 s02 s03 s04 s0n -> the initial setup time for each job

1 0 s12 s13 s14 s1n }

2 s21 0 s23 s24 s2n }

3 s31 s32 0 s34 s3n } -> the setup time for job 'j' after job 'i' has been executed

4 s41 s42 s43 0 s4n }

… }

n sn1 sn2 sn3 sn4 0 }

Now we have to find the sequence of jobs that will execute all jobs in the shortest make span. We use an adaption of the nearest neighbour algorithm:

- We start with job 1

- We search the job that has the shortest setup time after job 1 (job x)

- We search the job that has the shortest setup time after job x (job y)

...

and so on, untill we have done all jobs. This way we have found our first solution (the sequence of jobs and the corresponding setup-times, when we start with job1)

++After that we do the same thing but this time starting with job 2. Again we will find a (different) solution. We do that for all n jobs and in the end we calculate the total makespan (= setup times+ process times) of every solution and we look what the best solution is (i.e has the lowest make span).

I have gotten the constructor (problemInstance()) from my professor and that constructor reads the data from a file into our matrices. Then I use the following method to get my solutions into the seqJobsSol[][] and the setupTimesSol[][] matrices. I think the idea is correct but my problem is that once the program has executed the first loop my setupTimes[][] matrix is set to -1 (I have done that to make sure he doesn't execute a job that already has been executed). I will have to read in the data from the file again I think but I have no idea how to do that. So can anybody help? Or suggest a solution where I avoid my problem?

My method is:

public int calcSolutions (){

int k = 0;

int c = 1;

for (int i = 0; i < nrJobs; ++i){+

+setupTimeSol[0]

I am a student business engineering and I have to write a program to solve a 'single machine schedueling problem with seqeunce dependent setup-times'. I have written the code but I still have some problems that I can't solve. I don't know what to do anymore and my due-date is coming closer and closer so I would be EXTREMELY gratefull if somebody could help me out a little... (it is probably not that hard for an experienced programmer but it takes a while to explain the problem)

What we get is this: a certain number of jobs (nrJobs), a matrix with the process time of each job (processTime[]), a matrix with the inital setup times for each job (initSetupTime[]) and finally a 2 dimensional matrix with the setuptimes between all jobs (setupTime[][]; for example, on place [2][4] of the matrix is the setup time that is needed to prepare job 5 after we have finished job 3). Something like this:

i/j 1 2 3 4 … n -> the number of the jobs

0 s01 s02 s03 s04 s0n -> the initial setup time for each job

1 0 s12 s13 s14 s1n }

2 s21 0 s23 s24 s2n }

3 s31 s32 0 s34 s3n } -> the setup time for job 'j' after job 'i' has been executed

4 s41 s42 s43 0 s4n }

… }

n sn1 sn2 sn3 sn4 0 }

Now we have to find the sequence of jobs that will execute all jobs in the shortest make span. We use an adaption of the nearest neighbour algorithm:

- We start with job 1

- We search the job that has the shortest setup time after job 1 (job x)

- We search the job that has the shortest setup time after job x (job y)

...

and so on, untill we have done all jobs. This way we have found our first solution (the sequence of jobs and the corresponding setup-times, when we start with job1)

++After that we do the same thing but this time starting with job 2. Again we will find a (different) solution. We do that for all n jobs and in the end we calculate the total makespan (= setup times+ process times) of every solution and we look what the best solution is (i.e has the lowest make span).

I have gotten the constructor (problemInstance()) from my professor and that constructor reads the data from a file into our matrices. Then I use the following method to get my solutions into the seqJobsSol[][] and the setupTimesSol[][] matrices. I think the idea is correct but my problem is that once the program has executed the first loop my setupTimes[][] matrix is set to -1 (I have done that to make sure he doesn't execute a job that already has been executed). I will have to read in the data from the file again I think but I have no idea how to do that. So can anybody help? Or suggest a solution where I avoid my problem?

My method is:

public int calcSolutions (){

int k = 0;

int c = 1;

for (int i = 0; i < nrJobs; ++i){+

+setupTimeSol[0]

*= initSetupTime[i];+*

+seqJobsSol[i][0] = i;+

+setupTime[j][i] = -1;+

+}+

+int s = setupTime[r][0];+

+while (setupTime != negArray){ // negArray[][] is an 2-dimensional array I have filled with -1 to be able to compare with setupTime[][])+

+if (setupTime[r][0] > setupTime[r][m] && setupTime [r][m] >= 0){+

+s = setupTime[r][m];+

+}+

+}+

+setupTimeSol[r][c] = s;+

+seqJobsSol[r][c] = k;+

+setupTime[l][k] = -1;+

+}+

+++c;+

+}+

+}+

+}+

+{+

+processTime = new int[nrJobs];+

processTime[i] = s.nextInt();

s.nextLine();

initSetupTime = new int[nrJobs];

for (int i = 0; i < nrJobs; i++)

initSetupTime[i] = s.nextInt();

s.nextLine();

setupTime = new int[nrJobs][];

for (int i = 0; i < nrJobs; i++)

{

setupTime[i] = new int[nrJobs];

for (int j = 0; j < nrJobs; j++)

setupTime[i][j] = s.nextInt();

}

s.close();

}

PLEASE HELP!

Edited by: mdcnuydt on Aug 18, 2009 2:26 PM

Edited by: mdcnuydt on Aug 18, 2009 2:30 PM

Edited by: mdcnuydt on Aug 18, 2009 2:33 PM+seqJobsSol[i][0] = i;+

*for (int j = 0; j < nrJobs;*+j){++setupTime[j][i] = -1;+

+}+

*int r = i;*+int s = setupTime[r][0];+

+while (setupTime != negArray){ // negArray[][] is an 2-dimensional array I have filled with -1 to be able to compare with setupTime[][])+

*for (int m = 1; m < nrJobs;*+m){++if (setupTime[r][0] > setupTime[r][m] && setupTime [r][m] >= 0){+

+s = setupTime[r][m];+

*k = m;*+}+

+}+

+setupTimeSol[r][c] = s;+

+seqJobsSol[r][c] = k;+

*for (int l = 0; l < nrJobs;*+l){++setupTime[l][k] = -1;+

+}+

+++c;+

*r = k;*+}+

+}+

+}+

*The constructor we got from our professor is this:**public ProblemInstance(String fileName) throws FileNotFoundException*+{+

*Scanner s = new Scanner(new File(fileName));**nrJobs = s.nextInt();**s.nextLine();*+processTime = new int[nrJobs];+

*for (int i = 0; i < nrJobs; i*+)processTime[i] = s.nextInt();

s.nextLine();

initSetupTime = new int[nrJobs];

for (int i = 0; i < nrJobs; i++)

initSetupTime[i] = s.nextInt();

s.nextLine();

setupTime = new int[nrJobs][];

for (int i = 0; i < nrJobs; i++)

{

setupTime[i] = new int[nrJobs];

for (int j = 0; j < nrJobs; j++)

setupTime[i][j] = s.nextInt();

}

s.close();

}

PLEASE HELP!

Edited by: mdcnuydt on Aug 18, 2009 2:26 PM

Edited by: mdcnuydt on Aug 18, 2009 2:30 PM

Edited by: mdcnuydt on Aug 18, 2009 2:33 PM

- 61 Views
- Tags: none (add)