How to implement a "generic" solver for scheduling problems?

Question

I have been accepted for an internship for 6 months. The aim of this internship is to implement a "generic" solver for scheduling/production planning problems. This solver will bill a small prototype for a saas product.

I am aware that there is a huge number of this kind of problems. It seems that this is a very ambitious (or even a non-realistic) goal to finish within only 6 months. It's frustrating and I don't know where to start, in particular because there is no OR expert in the company. So I need to really focus on a small part of the problems.

So, my questions are, 1) What to do in order to progress as much as possible, how to filter the problems to focus on? 2) What are the easiest methods to use when solving etc. (I do not need necessarily exact methods, I am thinking about metaheuristics)? 3) Is there some examples of these kind of solvers?

Any other suggestion/idea/advice/resource/etc. that could help making the experience less frustrating is welcome.

EDIT: The main issue that is causing the frustration is how to identify the "common" problem(there is far more than a single problem in scheduling), I don't know how to proceed or even where to start.

I believe you should choose a solver in a programming language you are comfortable with and search for an example that could be used as a starting point. Good luck! — Stradivari, Feb 04 '20 at 10:08
I really liked ortools after seeing these examples: https://github.com/google/or-tools/blob/stable/examples/python/jobshop_ft06_distance_sat.py and https://github.com/google/or-tools/blob/stable/examples/python/shift_scheduling_sat.py — Stradivari, Feb 04 '20 at 20:53
Take a look at other generic solvers that are open source, such as OptaPlanner (github), Choco, Oscar, etc. Reading source code is a great way to learn. — Geoffrey De Smet, Feb 21 '20 at 10:13

score 10 · Answer 1 · answered Feb 04 '20 at 09:40

As you mentioned about "scheduling/production planning problems", I refer it to manufacturing planning and detailed schedule. Also, I know that there are specific methods to solve other planning and scheduling problems. (E.g. vehicle routing problem variants). Planning and Scheduling, specifically in the real application, will need to survey from some essential aspects:

1) Understanding, which kind of problem you have faced? For example, in the machinery area, what is the specification of the environment? job shop, open shop, etc?

2) How much your problem scales?

3) Which one method, (exact or (meta)heuristics), could be used to solve the problem?

4) How do you want to represent your problem results?

Based on the above questions (also there are others) you could try implementing your own/specific solver.

Also, it should be noted that:

If you are going to develop a mathematical program, it would be considered usually, each problem needs a specific MP and you might have to develop many models.
If your problem's scale is large and your model is straight forward, you would expect to solve the problem using open-source solvers otherwise, you should use the commercial solvers which need more cost or you will need some professional skills to use an advanced approach like decomposition method.
As per, many real problems should be solved in a reasonable time, (meta) heuristics like CP, genetic algorithm, etc can be applied.
As MSExcel is frequently used in industry and what you are looking for is based on excel, you can try developing an excel-based solver.
If you are interested to develop a friendly user-interface, using a programming language (like C++, Python, etc) might be interested. Specifically, combining with the solver.

Finally, some references and related questions, which I hope to be useful, are:

As far as I know, MIP solvers(especially open-source) are not too good to solve all kind of scheduling problem, some problems are harder than other. Am I right? If so, what is the class of problems that I can easily treat with MIP solvers ?. Another question : a decomposition method gives a bound on the problem, I believe that I need to apply a heuristic to find a feasible solution, Am I right ? — Antarctica, Feb 05 '20 at 02:34
State-of-art solvers like CPLEX or GUROBI can solve the scheduling models (MIPs) even in the large scale sense. Cplex has CPO engine which has been designed to solve the large scale models efficiently. Some open-source solvers like coin-CBC can solve large scale models if the problem formulation has been straight forward. To know what classes can be solved using MIPs, the best way is searching in articles or trying yourself. please, see this question. — A.Omidi, Feb 05 '20 at 05:51
As other community members mentioned too, one of the best ways to attack the real planning and scheduling problem is using heuristic methods. If you are interested in the programming language you could try writing your heuristic algorithm. AFAIK, some decomposition variants like branch-cut-price can solve the large scale scheduling problem and it's an exact method. But as I said, it needs some professional skills. I hope it would be useful. :) — A.Omidi, Feb 05 '20 at 05:57

score 7 · Answer 2 · answered Feb 04 '20 at 21:09

The "generic" aspect of the solver might just mean that management has, um, inflated expectations. That said, and focusing on the use of metaheuristics, I'll throw out a few ideas.

Where possible, use a (well-crafted) third-party library to do the actual metaheuristic computations, rather than writing your own. It's likely to be faster than what you would produce, it will certainly save you development time, and if you are using parallel threading it may save you some sleepless nights.
After ascertaining just how generic this solver is supposed to be, look for common elements among the problems it is intended to solve, and then look for metaheuristics designed for problems with those elements. As an example of what I mean, a lot of scheduling problems largely boil down to some combination of ordering a list of activities and maybe winnowing out some. There's a variant of genetic algorithms called random-key genetic algorithms that are easy to implement for problems of that type. (I don't know how their performance compares to other metaheuristics, but I do know they are fairly easy to implement.)
You do not have to limit yourself to one metaheuristic. You could code the program to run metaheuristic races one each problem (e.g., one thread running simulated annealing, another thread running 2-opt or 3-opt, another thread or two doing a GA), possibly with solution swapping among the methods (restart method 1 at some point using method 2's best solution ...), and then give the user the overall winner.

On using different methods: What do you think about using some exact algorithms for some problems(e.g;. problems in $P$) and/or a MILP open source solvers for some others? What is the class of problems that I can easily treat with MIP solvers? What do you think about decomposition methods(e.g. branch-cut-price)? (AFIK decomposition methods are not widely used in industry and they have a considerable implementation effort.)
On the complementarity of the methods Is your 3rd point still doable with methods of different families? How to ensure some "complementarity" across the methods? — Antarctica, Feb 06 '20 at 02:12
I hesitate to declare any problem type "easily treat[able] with MIP solvers", with one exception: if the problem is a pure integer problem, the data is all integer and the constraint matrix is totally unimodular, you can solve it as an LP, which makes it easy. I don't really know if BPC is useful for scheduling problems (never having tried it). As far as complementarity goes, I don't think can (or need to) ensure it. You just roll the dice and take your chances. — prubin, Feb 07 '20 at 22:20

score 7 · Answer 3 · answered Feb 06 '20 at 13:12

Before you even start worrying about algorithms, you need to figure out the solver's architecture. You can do so by posing and answering questions such as the ones I ask below. The answers will be a function of the goals of the project, the help & know-how of the people who employ you and, crucially, what you can realistically do in 6 months. Keep in mind that writing an interface you've never seen before can easily take a month or two so experiment first before committing.

what language are you going to use?
what build system are you going to use?
what types of OSs will you support?
do you have a way of getting the math in the solver or so you need to write a parser?
will you code the LP/MILP part yourself or link third party? If you code it, you'll need to identify, write an interface to, and link, a factorisation library.
if you use third party, you'll have to write the interfaces. Ideally, pick libraries with ok-ish interfaces to the language you're using.
how is the user going to retrieve the result? What are the exit flags/convergence conditions going to be?
are you going to use a parallel framework? If so, and you choose multithreading, are your dependencies thread-safe?
what framework are you going to use for integration testing/unit testing?
are you going to support non-linear functions? If so, you'll need computational graphs and ways to get derivatives.
are you going to use a sparse container to represent your coefficient matrix? If so, which one and from what library?
do you need to support callbacks/signal handling?
is your software going to be use standalone or invoked as a library?
how are you going to handle exceptions?

Thanks for you detailed answer, I already have some answers but I am not sure that I understand all of your questions. 1. I'am going to use Python, 2. What do you mean by "build system", 3. Windows & Mac, 4. What do you mean by "getting the math in the solver or so you need to write a parser", 5. I have the possibility to use open-source solvers so I will not code the MIP/MLIP part on my own, Is that what you meant?, 6. What do you mean exactly by interface in "if you use third party, you'll have to write the interfaces." — Antarctica, Feb 06 '20 at 14:09

score 6 · Answer 4 · edited Feb 04 '20 at 19:45

Generally speaking the most generic scheduling problem is the RCPSP. However, even that tends to need extensions for many practical problems. See Hartmann, Sönke, and Dirk Briskorn. "A survey of variants and extensions of the resource-constrained project scheduling problem." European Journal of operational research 207.1 (2010): 1-14. for a structured overview of the extentions that have been discussed before 2010.

Generally speaking the more tailored to the specific problem the model and algorithm are, the better it will perform. However, there are generic solvers, even open source versions, see List of Implementations for common OR problems. Their performance is typically strongly influenced by the exact model and its implementation.

Solving real world problems is to a large extend about "finding the problem" that means modelling, looking at where data/information lies and how it flows, where decisions are made, and what exactly can be automated. Then just using any solver / metaheuristic or even a local search will often get you 80% of the way. The 20% that remain are actually about fine tuning solution methods / exact algorithms. This is why open source solver companies still have a business model. They don't make their money with the solver, but with the consulting around it.

score 4 · Answer 5 · answered Feb 10 '20 at 09:48

First of all, congratulations on your internship. It is a great opportunity to put your skills into practice, and for the organization to get an understanding of what OR can be used for. But for the project to be successful, it is important that you are aligned on the problem you are solving. It currently sounds like you have a very broadly defined task which gives the huge risk that, even if you are doing a great job building the solver, that you end up with something that is different than what the company is hoping to get out of it. A solver is only valuable if it can help the company or its customers answer valuable questions.

I think when you have a more well-defined project, it will be easier to make the right technical choices, and there are a few other good answers around that so I will leave the technical aspects out of this answer. Here is a way to approach it:

Define what a successful project would look like

It is very important that you understand why the management decided to do the internship. You should ask them what they are hoping to get out of it, and what the ideal outcome would be. Since they don't have any OR-experts, a likely goal is to understand if OR can bring value to them and their customers. But it could also be some very specific challenges that are top-of-mind for them that they hope you can help with.

Define what the most important KPI's or questions to answer is

You write that the company wants a generic solver which is very broad, so you need to find a place to start. Together with the management, you should define a very specific challenging problem either they or a customer are having. From this, you can start to understand what the most important objectives are which you then can use to decide what model you need to build. There are quite many different possibilities e.g.

Shorten the production time
Minimize labor costs
Increase the capacity of the system
Maximize profit by choosing what to produce

But it could also be some more strategic questions they want to answer

How much can we increase capacity if we buy 2 more machines?
How should we replan if one of our machines breaks down for 8 hours?

Understand the decision-maker and decision process

The solver you are building needs to be used by someone. You should try to get as deep understanding of their job as possible. What are the key decisions and how does it link to the earlier defined objectives. You should ask if you can sit with the person for minimum an hour to ask them questions about their job and potentially watch them perform it while they tell what they do. This is also an opportunity to gather data you will need as input to your solver.

Start building and iterate

You should now be able to formulate the first version of your model and can start building your solver. I think there are other good answers around what methods you can use, but I will just highlight that it is important that you don't bury yourself into the code until the end of the project. In the end, people will care about the results they can get out of your solver, not the solver by itself. You should try to schedule some touchpoints at least once a month with the end-user where you can demo and show results and get some feedback to understand if you are moving in the right direction.

Every company and problem is different which will affect where your biggest challenges will be, but I hope they above can help you get started. Good luck!

Thanks for this detailed answer! It has already given me a direction to follow. I will do my best to get some touchpoints, I didn't think of it before you answer, but now, it seems obvious. Having someone to report the problem for me instead of having direct contact is, somehow, a loss of information and will have a considerable consequence on the final product. For example, I noticed that a lot of people do not distinguish between a constraint and an objective function! — Antarctica, Feb 13 '20 at 02:44
Also, I will try to avoid the code, but, since it's a mandatory internship to get my master's degree, I can't just write a model and call a solver :/ I don't think it can be that appreciated by my teachers. I just knew that the company has tried to do a saas for scheduling but they failed so they are now considering using operations research. I will try to find out the reasons why they failed, it may be helpful. Again, thanks a lot Michael :) — Antarctica, Feb 13 '20 at 02:44
Sounds like you have a good approach forward! ..and a very good idea to understand why they failed previously. I don't think you need to avoid the code, it is just important to remember to use it to generate new insights for the company :-) — Michael Lindahl, Feb 13 '20 at 12:06

How to implement a "generic" solver for scheduling problems?

5 Answers5

Define what a successful project would look like

Define what the most important KPI's or questions to answer is

Understand the decision-maker and decision process

Start building and iterate