What is this problem called?

Question

I'm trying to look up this problem but I don't know what it's called. The premise is this:

Given m machines and j jobs, where each job can only be assigned to machines i through j, I need to assign the jobs to machines so that I maximize busy machines at one time. I am only concerned with how they are assigned at time 0. I am not concerned with how I would schedule remaining jobs after a job is completed.

Once a job and a machine are assigned to each other, no other job or machine can act on either member.

Answer 1

Scheduling algorithm

Answer 2

Sounds like a scheduler.

Answer 3

As others said, what you described is a problem, not an algorithm. There are many techniques you could use to solve your problem. Which one you should choose depends on your needs. If you need the optimal solution, you must use a technique called integer programming. If you want a very good solution, not necessarily the optimal one, there are many heuristics you could use.

Answer 4

As other have said, it's a scheduler.

It's also a classic problem used to demonstrate OOPS development, and in particular it used to be used as a very common sample application for Smalltalk programming.

Answer 5

Like they have said you are basically writing a 'scheduler'.

As your 'j' jobs seem to be having equal priority may be you are looking at 'Round robin - time sliced scheduling algorithm'.

Answer 6

The problem is a variant of the bin packing problem, which has a wider variety of literature than processor scheduling.

Typical real world OS multi-processor scheduling algorithms don't operate with knowledge of how the long jobs will take, and account for other issues such as memory affinity, and trading the scheduler's complexity with the benefit of scheduling.

I have encountered get this kind of problem in modular avionics systems where you are apportioning jobs to nodes, and there you do know the expected timing and memory requirements for their jobs prior to the jobs executing.