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.
