3 Replies Latest reply on Aug 27, 2009 11:51 AM by jduprez

    Implementation of Nearest-neighbour algorithm (single machine schedueling)


      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;+
      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;+
      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();

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

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

      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();


      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
        • 1. Re: Implementation of Nearest-neighbour algorithm (single machine schedueling)
          So you need a way to read the file again?

          Scanner class doesn't have a method to go back to the first line. But you can create a new instance of Scanner and read the file again.
          • 2. Re: Implementation of Nearest-neighbour algorithm (single machine schedueling)
            Yeah, but that is not a very 'elegant' solution and it will take a lot of CPU time, no? (we have to solve certain problems and give the CPU time together with our answers) So, I have been thinking that I could avoid my problem by not setting the colomns to -1. I could do that if I could just find the java-code for the statement:

            *"X not yet an element of array[][] on row r of that array"*

            Here is the code. In bold is where my problem is located

            public int [][] calcSolutions (){

            int k = 0;
            int c = 1;

            for (int i = 0; i < nrJobs; ++i){
            setupTimeSol[0] = initSetupTime[i];
            seqJobsSol[i][0] = i;
            int r = i;
            int s = setupTime[r][0];
            while (c < nrJobs){
            for (int m = 1; m < nrJobs; ++m){
            if (setupTime[r][0] > setupTime[r][m] && *"m not yet an element of seqJobsSol[] on row r"*){
            s = setupTime[r][m];
            k = m;
            setupTimeSol[r][c] = s;
            seqJobsSol[r][] = k;
            r = k;

            Like I have said before, good help would be MOST appreciated!! (also with duke-points :))
            (tnx to Psyber already!)
            • 3. Re: Implementation of Nearest-neighbour algorithm (single machine schedueling)

              several remarks.
              1) Please format code when you post it. Write or copy/paste your code in the forum post editor, select it, and click the CODE button. The non-formatted code is hardly readable, no matter what manual space indentation you try to put in the post editor.
              2) Note that I did try to help in your other thread [How to implent "X not yet an element of array[][] on row r"?|http://forums.sun.com/thread.jspa?threadID=5403877&messageID=10797364#10797364], but without the info on the context that you provide in this thread. So, although I consider my answer there logically valid (provided you accept that I ignored the partial code that was given there), it would be horrible in terms of performance.
              3) Is the algorithm you describe mandated by your professor? At first sight it seems quite inefficient (+O(log(N)N^2)+, if not +O(N^3)+). There are several documented "nearest neighbor" (or, "shortest path") algorithms. In particular your problem seems to lend itself to recursion (at least in terms of readability), and caching (at the expense of using memory, to avoid recomputing intermediate values).
              Have you considered other algorithms?
              4) Using the current algorithm: If I understand correctly, you put +-1+ in +setupTime[i][j]+ to mark that you have already used node j while computing the setup sequence starting from i (or the other way round, sorry I can't read your code)? That's a mistake: the contents of setupTimes are a given, they are input data of the problem that you should keep constant for the duration of your computation.
              Instead you should use yet another structure to hold the information "I have already traversed node j in the current sequence (which started from node i)". This structure doesn't need to be 2-dimensional: it will only list the (N) nodes during *one* sequence starting at node +i+, and doesn't need to survive when you're done with +i+ - just recreate it when starting at node +i+1+.
              In particular this structure could be a +Set<Integer>+, where you would put the various j you traverse, or a +boolean[N]+, where +(booleanArray[j]==true)+ means you have traversed node +j+.
              5) There's a language mistake in your code:
              {code}while (setupTime != negArray) ... {code}
              This code compares the +references+ (~pointers) to the 2D arrays, it does not compare the contents of the arrays. So it's definitely *not* a way to guard against one cell being -1.

              Edited by: jduprez on Aug 27, 2009 11:50 AM