An n×m minimum-makespan general job-shop scheduling (JSSP) problem is a problem where there is a set of n jobs, where there is at least one job, and a set of m machines.
Each job has a set sequence and order of machines that the job has to go through to complete the job, i.e, J1 must go through M1, M2, and M3. The time each job needs at a machine can be different. A job cannot be interrupted when it is being processed by a machine, and the goal is to find a schedule that minimizes the time required to complete all the jobs, L, also called the makespan.
Heuristic methods for solving JSSPs have genes where each gene represents a heuristic used at each step of generating a schedule.
The order of genes in the chromosome represent the priority of the rules that will be applied to the remaining jobs to be scheduled. One example rule is SOT-rule, which is similar to a greedy algorithm where the operation selected is the one with the shortest immediate processing time.
