Job scheduling for a 2 stage job with 2 machines available for each stage

I am trying to solve a problem where I am provided a list of jobs that need to be scheduled to minimize the processing time. Every job has to be performed in 2 stages where the second stage can be done only after the first one is finished.

There are 2 machines available for each job i.e. there are 2 machines available for stage 1 and 2 machines for stage 2. A stage 1 machine can only perform stage 1 jobs and the same holds for stage 2 machines.

According to google genetic algorithms are recommended for such problems. I am slightly familiar with genetic algorithms, but do not know how to represent this problem as a chromosome and what type of cross-over would be suitable here.

• Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.
– Community Bot
May 8 at 18:10
• @ashorj, Wellcome to ORSE. Are you having any force to use GA to solve the problem? There are already other heuristic methods to solve this problem with very good results. May 11 at 10:06
• Also, there is a good presentation here. May 11 at 10:14
• @A.Omidi thanks for the presentation. It is indeed well explained. I wonder if a single chromosome of length 'n' representing the job priority would be enough. Wouldn't it be better to have a chromosome of twice the length of the number of jobs '2n', where the first n genes would represent the job priority for the the available machines for stage 1 of the job and the remaining n genes would represent the job priority for the available machines for 2nd stage of the problem. May 12 at 14:11

Assuming there are $$n$$ jobs, your chromosome represents a permutation of the indices $$1,\dots,n$$ indicating job priorities. Whenever a machine in either stage becomes available, it is assigned the highest priority job in the queue for that stage. If a job encounters two idle machines (which will happen at the very outset in the first stage, and at least once in the second stage), assign it to the machine which will process it faster, breaking ties arbitrarily. Since GAs maximize fitness and you want to minimize makespan, the fitness of a chromosome is the difference between an upper bound on the makespan and the actual makespan for the schedule (chromosome).
• You could certainly try that. I suspect that most GA libraries that support permutation chromosomes only support a single permutation, so you would need to decode a permutation of $1,\dots,2n$ into a permutation of $1,\dots,n$ and another permutation of $1,\dots, n,$ which is not that hard to do.