# 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.