Subtask A

It is obvious that an optimal schedule can be modified in such a way that each machine starts processing at time ~0~ and never idle until performing the operation on all jobs that are scheduled for that machine.

The maximal number of jobs that can be processed within time ~t~ by machine ~m~ of type ~Op~ is ~t \operatorname{div} PTime[Op,m]~. Therefore the minimal amount of time that is needed to perform operation ~Op~ on all ~N~ jobs is the least number ~t~ such that:

$$\displaystyle \sum_{i=1}^{M[Op]} (t \operatorname{div} PTime[Op,i]) \ge N$$

The following algorithm computes the total processing time for operation ~Op~ in variable ~t~:

t:=0;
Repeat
  Inc(t);
  Processed:=0;
  For i:=1 To M[Op] Do
    Processed:=Processed+(t Div PTime[Op,i]);
Until Processed>=N;

Subtask B

It is obvious that the schedule for type A machines is the same as in the case of subtask A.

Let ~TAB~ be the minimal amount of time that is necessary to perform both operations on all ~N~ jobs.

We may assume that each machine of type B finishes processing exactly at time ~TAB~ and never idle between executing two consecutive jobs. If this is not the case originally then we can modify the optimal schedule accordingly, since if a job is available at a time in the intermediate container then this job will be available later too.

Let ~d~ be the time when processing of the first job by a machine of type B starts according to the optimal schedule. Denote by ~TB~ the minimal amount of time that is necessary to perform single operation B on all ~N~ jobs. By the same argument as in case of subtask A, we have that ~TAB = d+TB~. We already have an algorithm to compute the value ~TB~, hence it remains to develop an algorithm which computes the delay time ~d~.

Let ~Finish(Op,t)~ be the number of jobs that are finished at time ~t~ according to an optimal schedule for a single operation ~Op~.

The delay time ~d~ is the least number that satisfies the following condition:

For every ~t~ ~(0 \le t < TB)~, at least ~Finish(B,TB-t)~ number of jobs are available in the intermediate container at time ~d+t~.

We can check for a given ~d~ whether it satisfies the above condition. Therefore the value ~d~ could be computed by starting at ~d = 1~ and incrementing ~d~ while the condition does not hold.

We have faster computation by using incremental method. This method works as follows. The starting value for ~d~ is ~1~. Suppose that the above condition holds for a given ~d~ and ~t~ values ~0, \dots, ts~. If the condition does not hold for ~t~ value ~ts+1~ then increase ~d~ until the condition holds.