Assignment Problem: Find the minimum number of job sequences

Question

I have N different jobs. Some jobs can be done in succession.

It is necessary to arrange consecutive jobs to form a sequence of jobs so that the number of job sequences M is minimum.

The problem is in the form of Maximum cardinality matching.

But is it sure that when Maximum cardinality matching, the number of job sequences is the minimum?

I'm looking for an algorithm to solve it.

Example

N=6

The following jobs can be followed:

Job 1 can then go to jobs 2, 5.

Job 2 can then go to job 3.

Job 4 can then go to jobs 2, 5.

Job 5 can then go to job 6.

Performing job assignments, we get the following 2 jobs sequences:

1-2-3

4-5-6

Then M=2.

This can be seen as a problem to find the minimum number of crew to make all flights (jobs).

Answer 1

This problem is related to Topological Sorting.

Think about every job as a node of a graph. The rest of the approach is same as top sort.

Procedure to solve the problem:

1. Initially, in-degree of every node is 0.

2. Now change the in-degree of all nodes based on the given job relations.

3. Now run DFS or BFS from nodes whose in-degree is 0. Rest of the procedure is same as Topological Sorting.

Let's consider your given input.

1 -> 2

1 -> 5

2 -> 3

4 -> 2

4 -> 5

5 -> 6

inDegree[1] = 0

inDegree[2] = 2 (1->2, 4->2)

inDegree[3] = 1 (2->3)

inDegree[4] = 0

inDegree[5] = 2 (1->2, 4->5)

inDegree[6] = 1 (5->6)

If we run DFS from node 1 first, mark it's corresponding nodes as done then, 1, 2, 3 nodes will be processed. As relation between these nodes (1->2->3).

Note: Here it processed nodes could be 1, 5, 6 based on the relation 1->5->6. It'll also give the right answer. Which nodes will be processed first, it depends on the way you make the adjacency list.

Then 4 will be left as the unprocessed node whose in-degree is 0. So if we run DFS from 4, then 4, 5, 6 will be processd. As relation between these nodes (4->5->6).

So you've your answer, which is 2.

Note: After processing a path, new node can be found which is left unprocessed and whose in-degree is 0. For example, consider the relation 1->2, 2->3, 2->4.

If you first process the path 1->2->3, 4 will be left unprocessed.

If you first process the path 1->2->4, 3 will be left unprocessed.

Just following the basic Topological Sorting procedure will give you the answer. You'll have to count, from how many unprocessed nodes with in-degree 0, you're running the DFS.

Helpful resources to learn about topological sorting:

• Topological Sorting CP-Algorithms

• Topological Sorting GFG

• Topological Sort Tutorials & Notes | HackerEarth