2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$
    – Community Bot
    May 8, 2022 at 18:10
  • 1
    $\begingroup$ @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. $\endgroup$
    – A.Omidi
    May 11, 2022 at 10:06
  • 1
    $\begingroup$ Also, there is a good presentation here. $\endgroup$
    – A.Omidi
    May 11, 2022 at 10:14
  • $\begingroup$ @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. $\endgroup$
    – ashorj
    May 12, 2022 at 14:11

1 Answer 1

Reset to default
2
$\begingroup$

Since you did not say otherwise, I am going to assume that (a) all jobs are available for release at time 0, (b) each machine can handle any of the jobs and (c) your criterion is minimizing makespan (time the last job completes).

You can use mixed integer linear programming (MILP) or constraint programming (CP) to find a provably optimal schedule. Because genetic algorithms (GAs) are metaheuristics, they do not always find optimal solutions (although they sometimes do), and even when they do you do not get a proof of optimality (so typically you cannot be sure the solution is optimal).

That said, if you want to use a GA, one approach is to use a permutation chromosome. Some GA solvers support permutations directly; if not, you can work around that limitation.

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks for the suggestion! Should the chromosome have 2*n elements where the first n elements represent the priority for the 2 machines available for stage 1 of the job and the remaining n elements represent the priority for the 2 machines for the second stage of the job $\endgroup$
    – ashorj
    May 12, 2022 at 13:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    May 12, 2022 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.