P1065 [NOIP 2006 Senior] Job Scheduling Plan

We need to process $n$ jobs on $m$ machines. Each job has $m$ operations, and every operation must be completed on a specified different machine. Each operation of each job has a specified processing time. Every operation of every job is called an action. We denote an action by `j-k`, where $j$ is a number from $1$ to $n$ indicating the job ID, and $k$ is a number from $1$ to $m$ indicating the operation index. For example, `2-4` denotes the action of the $4$-th operation of job $2$. In this problem, we are also given an arrangement order for all actions. For example, when $n=3$, $m=2$, the sequence `1-1,1-2,2-1,3-1,3-2,2-2` is a given arrangement order, i.e., first arrange the $1$-st operation of job $1$, then the $2$-nd operation of job $1$, then the $1$-st operation of job $2$, and so on. On one hand, arranging each action must satisfy the following two constraints. 1. For the same job, each operation must start only after all its preceding operations have finished. 2. At any time, each machine can process at most one job. On the other hand, when arranging later actions, the working states of actions already arranged earlier cannot be changed. Since the operations of the same job are arranged in order, providing only the job IDs in the original order still yields the same arrangement order. Thus, in the input, this arrangement order is written in a shortened form as `1 1 2 3 3 2`. Note that the “arrangement order” only requires arranging each action in the given order. It is not necessarily the actual execution order on each machine. In actual execution, an action later in the list may finish earlier than one that appears earlier. For example, take $n=3$, $m=2$, with the following data (machine ID/processing time): Job ID | Operation 1 | Operation 2 -|-|- $1$ | $1/3$ | $2/2$ $2$ | $1/2$ | $2/5$ $3$ | $2/2$ | $1/4$ Then for the arrangement order `1 1 2 3 3 2`, the two implementation plans below are both valid. However, the total times required are $10$ and $12$, respectively. Plan 1, time $10$: | Time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :--------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | Machine 1 action | `1-1` | `1-1` | `1-1` | `2-1` | `2-1` | `3-2` | `3-2` | `3-2` | `3-2` | Idle | | Machine 2 action | `3-1` | `3-1` | Idle | `1-2` | `1-2` | `2-2` | `2-2` | `2-2` | `2-2` | `2-2` | Plan 2, time $12$: | Time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | :--------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | Machine 1 action | `1-1` | `1-1` | `1-1` | `2-1` | `2-1` | Idle | Idle | `3-2` | `3-2` | `3-2` | `3-2` | Idle | | Machine 2 action | Idle | Idle | Idle | `1-2` | `1-2` | `3-1` | `3-1` | `2-2` | `2-2` | `2-2` | `2-2` | `2-2` | When inserting an action into some idle interval (gap) on a machine (the final unarranged segment on a machine can also be regarded as an idle interval), it can be inserted at the front, back, or somewhere in the middle. To simplify the problem, we stipulate: under constraints (1) and (2), insert as early as possible. Moreover, if multiple idle intervals can accept the insertion, insert into the earliest one under constraints (1) and (2). Under these rules, Plan 1 above is correct, while Plan 2 is not. Clearly, with these rules, for a given arrangement order, the implementation plan consistent with it is unique. Please compute the total time required by this plan to complete all tasks.

The first line contains two positive integers $m$, $n$, separated by a space, where $m$ ($< 20$) is the number of machines and $n$ ($< 20$) is the number of jobs. The second line contains $m \times n$ integers separated by spaces, which is the given arrangement order. The next $2n$ lines each contain $m$ positive integers separated by spaces, each not exceeding $20$. The first $n$ of these lines give, in order, the machine IDs used by each operation of each job. The first number is the machine ID for the $1$-st operation, the second number is the machine ID for the $2$-nd operation, and so on. The last $n$ of these lines give, in order, the processing times of each operation of each job. You may assume all the above data are correct, and no validation is required.

A single positive integer: the minimum total processing time (makespan).

NOIP 2006 Senior, Problem 3. Translated by ChatGPT 5