Production optimization - what type of problem?

Question

I want to make an algorithm that distributes orders $O_1,O_2,\dots$ to equipment $E^1,E^2,\dots$ so they can be processed in an optimal way.

Different orders require different equipment for the processing steps, but which equipment may be used for which step is already known in the form of a tuple e.g. $(E^3,E^8,E^9)$.

For every piece of equipment there may be more than one instance: $E^k_l, l \in \{1,\dots,p \} $

The time $t \in \mathbb{R}^+_0$ spent on each equipment is determined by the amount of material to process (as specified by the order) and the speed of the equipment (as a property of the equipment).

Each equipment may process exactly one order at any given time.

The processing steps have to happen in the order specified in the tuple

It is possible to have more than one choice of equipment for a certain processing step, I will write this as $(\{E^3,E^4\},E^8,E^9)$. So it may be quicker to process on a certain machine if that one is available.

The optimization goal would be to process as many orders as possible during the available time $T \in \mathbb{R}^+_0$.

It should be possible to assign higher weights to certain orders so they get preferential treatment.

I may include more constraints later, but at this point I would like to keep it "simple".

I have a background in mathematics and some practical experience in programming and simple optimization.

At this point my problem is to find a start in tackling the problem since I don't really know what type of problem this is, and to check if I'm formalizing this meaningfully. Please excuse (and correct) my notation, I've been away from university for quite a while...

I am looking for a numerical solution and a decent approximation should suffice - it competes with solving the problem with excel and possibly some pieces of paper.

Answer 1

This is called parallel machine scheduling or also the job-shop problem. Small instances can be solved to optimality by formulating the problem as Mixed Integer Programming problem. For larger problems we can use a MIP model and just stop before optimality. That will give often very good solutions (a MIP solver will even give some information about how the gap could be between the best found solution and the best possible solution). For larger problems many heuristic approaches have been developed, including interesting meta-heuristics (such as genetic algorithms). These methods provide good solutions but no feedback about the quality (how good).

Typical pictures of solutions are:

Answer 2

In this particular situation there will be queuing of task (orders) for the equipment resources. Each order has a deterministic requirement for a certain amount of time on a particular type of equipment, so from the point of view of an order, there is no mystery about where the order needs to go "next"; it must be sent to a queue for that type of equipment.

The Question anticipates that there may be multiple instances of an equipment type, so these queues can have multiple "servers". That is, the types of equipment will in general be "single queue/multiple servers".

Note that an order requires, at any point in time, only one resource to progress (a server of the type of equipment next in its processing plan). Therefore it is impossible for resource deadlocks to occur.

A type of greedy algorithm for scheduling is the following. Eliminate all orders which cannot be fulfilled, even with open resource availability, within time $T$. The problem is to complete as many of the remaining orders as possible within that time constraint.

The queues should be dynamically reorganized when a step of one order is completed, and the order leaves its current server to go into the queue for its next processing step. Since it is desired to complete as many orders as possible, the queue should prioritize those orders whose time-to-fulfillment is least (adding up all the time required for all unfinished processing steps), using as a tie-breaker the least time required by the equipment type of the current queue.

After a feasible schedule for $N$ orders to be completed is found, it is possible to review the results of "greedy" scheduling for improvement opportunities. In particular there may be task whose critical path involved a lot of time on otherwise underutilized equipment, and by randomly prioritizing these task ahead of some that required less overall time but on "bottleneck" types of equipment, it is sometimes possible to obtain additional throughput.