Allocation Formula

Question

I have car repair services shop, there are many services(Diagnosis, Engine Repair. Electrical repairs...) Sequence conservation does not matter

And then I know how much time does one current car needs for single services, for example:

1. Ford - 120 minutes for diagnosis, 360 for engine and 80 for electric repairs
2. BMW - 90 minutes for diagnosis, 480 for engine and 140 for electric repairs
3. Mercedes - 90 minutes for diagnosis, 42 for engine and 160 for electric repairs

Etc. And there is big list of cars.

So is there any good algorithm or mathematical formula which allocates cars optimally into service boxes such don't waste time of boxes and get best result with minimal waiting of cars.

Answer 1

This is an example of a so-called "Open-Shop" problem. The difference to Job Shop Scheduling is that in the latter the sequence in which jobs are executed on machines is relevant, while this is not the case in your example.

Unfortunately, the problem is NP hard for your case. (For two machines is could be solved in polynomial time.) No need to despair, as there are a number of algorithms that will probably work just fine for your problem size.

Wikipedia has a few good starting points under "Open-Shop Scheduling", with a reference to a classical paper in this area.