2
$\begingroup$

Due to the answers to this and this questions, I was able to find the optimal solution for scheduling problem. However, if there are many tasks that must be scheduled, e.g. 1000+, then the solver takes obviously more time to solve it and OS terminates the program due to RAM lack with the following message: Process finished with exit code 137 (interrupted by signal 9: SIGKILL). My PC specs are:

  • OS: Ubuntu 20.04.4 LTS
  • CPU: Intel Core i5-8265U; 4 cores; 8 threads
  • RAM: 32 GB

What I've tried first of all is setting the log_search_progress = true flag and saw that for 1000 jobs the solver creates 2000000 literals described in this line: #kBoolAnd: 2000 (#enforced: 2000) (#literals: 2000000).

The next line: [Symmetry] Problem too large. Skipping. You can use symmetry_level:3 or more to force it. hints to try to use setSymmetryLevel(3). With this set, program will also get terminated. Solver uses all 8 threads available.

With this in mind, my question is: should this be run on the server hardware to improve performance or can I optimise the model much better? Talking about the model optimisation, I've found answer of Laurent Perron to this issue that it is a challenge for the solver to schedule so many intervals without decomposition. My team leader suggested that we can firstly take tasks of higher priority jobs, schedule them and then try to schedule those tasks that left. Say, take first 100 tasks of highest priority jobs and initialize their intervals, constraints and circuit between them and solve the problem. If the solution is found, add equalities and hints to the solver to schedule next tasks. What are your thoughts about that?

Full source code in Java

log_search_progress output

Improve this question
$\endgroup$
5
  • $\begingroup$ You are scheduling 1k tasks on 1 k machines ? $\endgroup$
    – Laurent Perron
    Aug 22, 2022 at 13:42
  • $\begingroup$ Not sure if you have read the linked questions, but there's only one machine for all tasks. $\endgroup$
    – Artem Popov
    Aug 22, 2022 at 13:46
  • $\begingroup$ so why 1M booleans ? $\endgroup$
    – Laurent Perron
    Aug 22, 2022 at 13:50
  • $\begingroup$ I got it. You have setup times. So your model is quadratic. $\endgroup$
    – Laurent Perron
    Aug 22, 2022 at 13:54
  • $\begingroup$ Yes about the model, each task is connected to each another task. Since each edge has a literal associated with that, 1000 * 1000 = 1M literals. $\endgroup$
    – Artem Popov
    Aug 22, 2022 at 13:54

1 Answer 1

Reset to default
2
$\begingroup$

A stack overflow does not necessarily mean that you ran out of RAM usually being out of RAM throws a java.lang.OutOfMemoryError: Java heap space. To verify this, check ram usage just before the program dies or temporarily rent server with much more memory and see if that helps. If the program dies but RAM is not full, increase the maximum stacksize of the JVM until the problem vanishes. The stack is a data structure stored in RAM, the JVM limits stack size to prevent an accidental recursion from eating all the RAM on the system as that would adversely affect other services on the same machine. You can increase those limits.

The scheduling batches with decreasing priority approach will usually not give you a global optima. Many configurations with equal objective value for higher priorities only can give you very different results down the line as "fragmentation" which will not matter at first will result in not being able fit lower priority tasks between the higher priority tasks unless all tasks have the same length.

enter image description here

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thank you for the answer! I'm sorry that I've misled you saying that JVM terminates the program. Actually, it's the OS which does it and I'll edit the question. Due to this, I do not get StackOverflowError per se, but the following line that indicates the excessive memory usage: Process finished with exit code 137 (interrupted by signal 9: SIGKILL) . Talking about your last sentence, I'm not sure if you have read the related questions, but the objective is to schedule as many tasks of higher-priority jobs as possible. Thus, we rather care about tasks of higher-priority jobs. $\endgroup$
    – Artem Popov
    Aug 22, 2022 at 10:56
  • 1
    $\begingroup$ It depends what you store between 2 phases. After selecting and scheduling high priority jobs, you can decide to keep which one were selected, and forget when they were scheduled, then schedule the next tier. $\endgroup$
    – Laurent Perron
    Aug 22, 2022 at 13:56
  • $\begingroup$ Thank you for the idea. What I've tried is sorting the jobs based on their priority and iterate over these sorted jobs. For each iteration the solver: initializes circuit, schedules tasks based on it and after the solution has been found uses addHint and addEquality for next solutions. The issue I can't cope with is that in each next circuit the first scheduled task in it overlaps with the first scheduled tasks scheduled in given circuit. Please see SortedJobsSchedulerRunner class in the updated source code if you're interested. $\endgroup$
    – Artem Popov
    Aug 23, 2022 at 7:45
  • $\begingroup$ For example, each job has only 1 task which lasts for 1 second. There are 100 jobs and 9 priorities. In this case, task 8 of job 8 has priority of 8 and starts at 20:00:00 and task 0 of job 0 has priority of 0 starts at 20:00:00 also. I think this happens due to the start literals which are unique for each circuit and they imply x[taskId]. I tried model.addEquality(x[taskId], solver.booleanValue(x[taskId])) if solver.booleanValue(x[taskId]) == true, but this results in only scheduling tasks of highest priority jobs and ignoring lower-priority ones. $\endgroup$
    – Artem Popov
    Aug 23, 2022 at 7:54
  • $\begingroup$ Rather then spending much engineering hours, i just spend a bit of money instead ovhcloud.com/de/public-cloud/prices/#419 these are cheap high ram instances, located in EU for GDPR compliance. $\endgroup$
    – worldsmithhelper
    Aug 23, 2022 at 7:58

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.