1
$\begingroup$

I have a FJSSP that I would like to solve. However, the jobs in this problem have deadlines and in addition there are setup times between two jobs. Because of this, my objective function is not just the makespan but rather a more complex (nonlinear)combination between makespan and tardiness (with respect to given deadlines) of the execution of the jobs.

I was thus wondering which solvers are available right now which offer flexibility to modify my objective functions. Or, in general, how are practitioners tackling these problems in industry currently? Can you please help?

Improve this question
$\endgroup$
4
  • $\begingroup$ Would you say, have you had any force to use a non-linear objective function? Is it possible to use e.g. the multi-objective approach, specifically, in the MIP context? $\endgroup$
    – A.Omidi
    Mar 13 at 19:36
  • $\begingroup$ @A.Omidi The problem is that machines can work different number of hours every day and I only care about the day jobs end, so it should be a linear function of a step function . I dont intend to use multiobjective techniques here. $\endgroup$
    – John D
    Mar 13 at 19:58
  • 1
    $\begingroup$ some points: 1) FJSSP is already NP-Hard in its essence and as you pointed out the number of jobs is around $400$, so it becomes more challenging. 2) There are some options to solve such a large-scale problem. First, by using a modified local-search heuristic that can handle your non-linear objective. Second, with the aim of CP/MI(NL)P solvers, and finally with special solvers like LocalSolver or Cp-SAT. (One of the best CP-SAT offered by Google or-tool). Do you try that? $\endgroup$
    – A.Omidi
    Mar 14 at 6:37
  • $\begingroup$ @A.Omidi Thanks! Yes, I am currently exploring the Google OR - tool option with CP SAT. I think the main problem will be to express my custom objective function in terms of the intervals, but we will see. Could you perhaps suggest a cool reference/tutorial on this? I think it would also help other people who have the same question. Thanks again! $\endgroup$
    – John D
    Mar 14 at 13:20

1 Answer 1

Reset to default
1
$\begingroup$

There are constraint programming solvers that support global constraints specific to job scheduling (setup times, resource sharing etc.). CPOptimizer is the one with which I am most familiar, but I am certain there are others. So a CP model is one possibility. As far as I know, CP models for scheduling can handle nonlinear objective functions.

A MIP model might also be a possibility, depending on what your nonlinear combination of makespan and tardiness looks like.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is CP going to scale well? I have around 400 jobs and 10 machines. $\endgroup$
    – John D
    Mar 13 at 16:01
  • $\begingroup$ That will of course depend on which solver you use, how well it is optimized for scheduling problems, and what hardware you have. I don't solve a lot of scheduling problems, but I think yours would be manageable ... and, of course, there's always the option to accept a less than optimal (or at least not provably optimal) intermediate solution that is "good enough". $\endgroup$
    – prubin ♦
    Mar 13 at 16:19
  • $\begingroup$ Thanks for your answer! $\endgroup$
    – John D
    Mar 13 at 16:48

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.