0
$\begingroup$

Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the hardware, it would be beneficial to the users to have a tool for deciding whether or not a job should be ran locally versus on the cloud. Two important factors would be how much time the user can afford to wait and the funds available to the user.

If we were only optimizing for cost, of course, we'd send every job to the local resources. It gets interesting when you optimize for both cost and time, considering there's a finite amount of machines locally (other users' jobs creates a queue) and the cloud can provide better/faster hardware.

Ultimately, say you have some amount of money and a time frame. After providing this information and a list of jobs (each with varying CPU nodes requested, memory required, estimated job time, etc.), this tool should be able to make a near-optimal decision about which jobs to run locally and which to run on the cloud.

Considering the optimization nature of this problem, Google's OR-Tools library looks great to start with. They provide guides (check left side bar there) to several "problem types". I'm having trouble deciding which category this problem falls into.

For those unable to visit the OR-Tools link, the problem types are:

  • Linear Optimization
  • Integer Optimization
  • Constraint Optimization
  • Assignment
  • Routing
  • Bin Packing
  • Network Flows
  • Scheduling

What problem type category does this best fall into, and what are some ideas on how to formulate said problem?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

In order to pin down a problem type, you will have to answer a number of questions about the application.

  1. How are you going to deal with the cost-time conflict? There are quite a few methods for dealing with multiple criteria, including taking a weighted sum, constraining one while optimizing the other (fastest turn-around within a budget, cheapest solution meeting a time limit), goal programming, ... Also, if you are simultaneously scheduling jobs for multiple customers, do they independently set time/cost tradeoffs (some impatient free-spenders, some patient tight-wads) or is there one tradeoff that applies to all of them.
  2. Is this an "online" application (schedule gets updated each time a new job comes in) or a "batch" application (accumulate a gaggle of jobs, schedule them all, accumulate more jobs, schedule those, ...). In the latter case, are previously schedules but as yet unrun jobs subject to being delayed in favor of new jobs? (I'm assuming, somewhat charitably, that there will be no preemptions of running jobs.)
  3. If in batch mode, are batches sufficiently far apart in time not to affect each other? If not (decisions on the last batch affect the next batch), you have to deal with "horizon effects". Decisions that look good in the short term can adversely affect long term results. As an example, you do daily batches, and on Monday you schedule enough cheap jobs locally to tie up the local resources through Wednesday. On Tuesday, an urgent job comes in with a truly ghastly cloud cost. Oops.

There are probably more questions, but I would start with those.

Improve this answer
$\endgroup$

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.