algorithms – Dynamic job scheduling with earliest time and deadline

I have a real life algorithmic problem and I’m trying to find out if there is any similar widely known algorithmic problem with known solutions that I could adapt to my particular use case.

I want to solve a kind of scheduling problem: I have a machine that will be processing jobs and I want to fit them into a schedule.

The capacity of the machine is limited within discrete time units (for example hours). During every given time unit $t$ the machine can process a limited number of work units – $u(t)$.

There are job queries coming one by one (they aren’t all known upfront), each job $j$ has:

  • the earliest time it can start to be processed by the machine $j_{et}$ – so it can only be processed if $t ge j_{et}$
  • the deadline $j_{ft}$ when it has to be finished – so it can only be processed when $t lt j_{ft}$
  • number of work units it takes to process it – $j_u $

The job has to be finished “in one go” – once a job is started by the machine the job has to be finished before any other job is started.

For each incoming job query I need to be able to:

  • tell if it is possible to add the job to the schedule or it has to be rejected
  • add the job to the schedule if possible

The closest problems I’ve found are:

Is there anything ‘closer’ to what I described? I would appreciate any hints or references that could inspire me solve this particular problem.