Classification of job shop scheduling problems

Question

I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory.

• The factory has several types of machines (say, locksmith, miller, welding)
• There are few machines of each type. (say, 3 locksmiths, 2 millers, 3 welders)
• There are several types of operations (some machines do more than one operation on the job, say, locksmith does soldering and assembling).
• The jobs on the machines have different times, all known beforehand.
• The jobs have dependencies on jobs done before (say, a product's made of 10 screws and 4 subparts, each of which needs 4 screws).

From what I searched, this looks sort of like a Flow Shop problem. The difference is in the dependencies and in the same machine doing different operations with different times on a job.

---

My main question is:

Is there some kind of a classification of these problems? A summary telling the differences?

For example, I don't understand much of how do these differ: Open Shop, Job Shop, Flow Shop, Permutation Flow Shop. And whether or not I missed something similar that could fit better to my problem.

---

As a side question, what approach do you think could help me best with the unusual requirements I've posted above? I'm writing my current approach below.

So far I've been able to work with the tree of dependencies without regard to the makespan times: just making a plan - a list of IDs, really - of what comes after what, from looking at the tree of what's been done so far and what are the leaves (nodes having done all their dependencies).

This allows for fast creation of meaningful individuals in the Genetic Algorithm population, but there seems to be no computationally cheap way to learn the individual's makespan time (which I have as the fitness function).

For that I have to create a calendar, or Gantt chart, if you will, to which I put the operations on the jobs in the earliest place possible, in the machine queue that's free at that moment, etc. The whole plan has to materialize and that seems the most costly computation of the whole problem.

Answer 1

In searching around for an online presence for one of the classics in this field (Coffman, Denning: Operating Systems Theory, Prentice Hall, 1983) I came upon what looks like a comprehensive textbook with a Google books preview Pinedo: Scheduling: Theory, Algorithms, and Systems, Springer 2008. The author's homepage also has pages devoted to each of his books. It has chapters for multiprocessor scheduling, open shop scheduling, flow shop scheduling and job shop scheduling.

The flow shop problem has $n$ jobs with $m$ machines. Each job needs to visit machines in the exact order $1,2,\ldots,m$. There are $nm$ parameters $d_{ij}$, which is the amount of time job $i$ demands on machine $j$. There is no constraint on the order in which machines service jobs. (The constraint is on the order in which jobs need machines.)

The permutation flow shop problem seems to add the constraint that every machine must service the jobs in the same order. So the goal is to permute the jobs to minimize the makespan of pipelining each job through the machines in order.

The open shop problem completely relaxes the ordering constraints. Each job demands time on each machine, but in no particular order. (And, of course, the amount of time demanded by job $i$ on machine $j$ can be 0.)

The flow-shop problem and open-shop problems are special cases of the more general job shop problem with precedence constraints: We are given a set of jobs $J=\{J_1,\ldots,J_n\}$ and a set of resources $R=\{R_1,\ldots,R_m\}$. Each job $J_i$ consists of a set of operations $O^i=\{O_1^i,\ldots,O_p^i\}$. Each operation $O_k^i$ requires a set of resources $R_k^i \subseteq R$ for a time $t_k^i$, and for each job, $J_i$ there is a set of precedence constraints (i.e., a partial order or directed graph) on the operations, $O_k^i \xrightarrow[\mathrm{before}]{} O_l^i$, stating that operation $O_k^i$ needs to finish before $O_l^i$ starts.

Your problem is a job-shop problem with an additional generalization that there are classes of identical resources ("3 locksmiths") and the operations can use any resource in the class. This brings in an aspect of the multiprocessor scheduling problem.

N.B., I believe that I've used the terminology that is used in the books by Coffman and Denning, and by Pinedo. The wikipedia pages are an utter disaster. The wikipedia page on job shop scheduling gives a definition of the open-shop problem that contradicts the wikipedia page on open shop scheduling. The wikipedia page on the flow shop problem is incomprehensible. And wikipedia is confused about the difference between multiprocessor scheduling, which involves $m$ interchangeable resources, and job-shop scheduling. For example, the wikipedia page on the Coffman-Graham list scheduling algorithm calls it a solution to the job-shop scheduling problem, although Coffman and Graham use the term "multiprocessor", not job-shop in the titles of their papers. (And note that the author of the wikipedia page on multiprocessor scheduling seems unaware of the original variant with precedence constraints.)