I have a problem that requires finding a plan to execute a job on two machines, A and B, or moving the job between machines to maximize the number of executed steps. Specifically, in each time interval, the job can be executed on A or B for a certain number of steps, or moved between machines without executing any steps. I've attached the question below.
We have two machines, A and B, and a job J that can be executed on either machine A or B, or moved between the machines in each time interval ti of t1,..,tn. The job can execute ai > 0 steps on machine A or bi > 0 steps on machine B at time interval i, or it can be moved from one machine to the other without executing any steps.
We need to design a dynamic programming algorithm that takes as input the lists a1,..,an and b1,..,bn representing the number of steps that the job can execute on machines A and B at each time interval, respectively. The algorithm should find a plan that maximizes the number of executed steps by deciding to run the job on A or B or move it between the machines for each time interval. The job can be executed on either machine A or B at time t1.
I have been trying to solve this problem using dynamic programming, but I'm having trouble defining the subproblems. Could someone please help me with this?
Here's what I've tried so far:
- I defined the subproblems as finding the maximum number of executed steps up to time I .
- I represented the state as OPT(i )= the maximum steps a job can execute from time t1 to ti
- I came up with the recurrence relation OPT(i) = OPT(i - 1) if we move job on time ti, otherwise OPT(i) = max(OPT(i - 1) + ai, OPT(i - 1)+bi).
However, I'm not sure if this is correct or how to to include the requirement that "The job can be executed on either machine A or B at time t1" into the recurrence relation. Any help would be greatly appreciated!
Thank you in advance.