Machine scheduling problem

Question

i have a combinatoric problem as such:

You are given N testers.

Each tester is one of M different types.

Each tester can be configured to use one of P different configs. .

You have L lots of products to test,

Each product can only be tested on specific Tester type,

Each product can only be tested by Tester configured with specific Configs. Some of the Configs can be applied on multiple products. Any tester can change its config during production, but each change on tester config will incur additional time U . Each lot has a lot size that determines its test-time, Q.

Now i need to come out a lot scheduling algorithm such that the time to finish testing all lots is minimum.

What are the best approaches to tackle this kind of problem ?

Answer 1

It can be modelled as a Job-Shop problem (JSP) with setup times where the job size is 1. Unfortunately it gets pretty hard to find an optimum when the number of jobs > 10.

There are many free solver implementations out there that contain Job-Shop as a sample problem: If you're using C++, Gecode is good. If you're free to choose, ECLiPSe Prolog contains source code for the JSP.

If you can do with a good solution (instead of an optimal one), I suggest using a greedy algorithm (for the JSP, greedy algorithms give solutions typically within 10% of the optimum - I had some experience with this). I'm gonna think about one and get back here (the problem is what are called 'setup time constraints', i.e. the constraints coming from changing tester configuration).