3
$\begingroup$

I am new to the fields of operations research. I have a Binary IP model for solving a scheduling problem and I am seeking to find information whether I can somehow transform it to a problem that can be solved using local search techniques. Is it possible? If yes, can you point me to some further materials on the topic?

I am aware the branch and bound technique builds a graph for the solution space. However, solving the problem does not scale particularly well due to the symmetry in scheduling problems and I wanted to explore an alternative technique such as local search. I am also happy to hear alternative suggestions.

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you need a provably optimal solution, or are you willing to consider heuristics? $\endgroup$
    – prubin ♦
    Nov 25, 2022 at 0:03
  • $\begingroup$ I am willing to consider heuristics $\endgroup$
    – Pia MiA
    Nov 25, 2022 at 0:29
  • 1
    $\begingroup$ Can you introduce symmetry-breaking constraints? $\endgroup$
    – Richard
    Nov 25, 2022 at 0:36
  • $\begingroup$ @Richard Actually I am not really sure whether I can do that. Is it something I need to explore before implementing the local search technique? $\endgroup$
    – Pia MiA
    Nov 25, 2022 at 0:55
  • $\begingroup$ @PiaMiA: This answer discusses symmetry breaking. You don't need this to solve your problem, but it can significantly reduce time-to-solution. $\endgroup$
    – Richard
    Nov 26, 2022 at 2:41

1 Answer 1

Reset to default
3
$\begingroup$

Constraint programming is often a good way to solve scheduling problems. You might want to look into that.

Beyond that, any advice on heuristics, local search etc. may be contingent on the specific nature of the problem. For some job shop problems, I have had good luck using genetic algorithms with a permutation-type chromosome. Given $n$ jobs to be scheduled on one machine, each chromosome would be a permutation of $1,\dots, n.$ Given $n$ jobs to be assigned to $m < n$ machines (multiple jobs per machine, one machine per job) I've used a variation on the permutation chromosome. I can't say, though, that GAs are a good choice for every type of scheduling problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @prubim Thank you for the provided information! That sounds as an interesting approach. Regarding the constraint programming approach, the problem I am considering is preemptive and considers parallel machines. For example [1] mentions it is sometimes very tricky to model preemptive scheduling. Is that the case? If so, would you give any additional advise? [1] math.unipd.it/~mpini/fse-doc/scheduling/preemptive-resource.pdf $\endgroup$
    – Pia MiA
    Nov 25, 2022 at 7:39
  • $\begingroup$ Preemption certainly complicates the problem. How hard it would be to implement in constraint programming is difficult to say, partly because it depends on the details of the problem and partly because it depends on the types of variables and "global" constraints implemented by the particular CP solver being used. $\endgroup$
    – prubin ♦
    Nov 25, 2022 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.