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.