If I have a scheduling problem, is it possible that Hall's theorem can be applied? I was thinking that the graph representation of the scheduling problem can be the preferences of the people / workers getting scheduled. Is there any such result or counter-claim?


1 Answer 1


A Characterization of Open Shop Scheduling Problems Using the Hall Theorem and Network Flow, a thesis by Arunasri Chitti may provide what you need.

The abstract reads:

Open shop scheduling problems are combinatorial problems where jobs with certain processing requirements on a number of different machines must be arranged in such a way that objectives related to completion time are optimized. Such problems have applications over a wide spectrum including such as communications, routing and manufacturing.

Many open shop problems are NP-hard but there are a number of special cases which possess polynomial solutions in the case of few machines or few jobs or when preemption of jobs is permitted. Many such solutions are based in the theory of matching or Hall’s theorem, or more generally network flow. The primary focus of this thesis is to describe a number of polynomial-time solutions which are constructed using these related concepts and methods.

The paper discusses the problem of scheduling resources to needs in a reasonably optimized fashion, Open Shop Scheduling, and how a particular subset of those scheduling problems "are a number of special cases that do have polynomial solutions and those solutions often come from the theory of matching, network flow and Hall’s theorem, which are related concepts and methods." See What is an NP-complete in computer science as well as What are the differences between NP, NP-Complete and NP-Hard?. Also see the Wikipedia topics NP-hardness and NP-completeness.

Scheduling in the context of the paper is defined as:

Scheduling deals with the arrangement of a given set of jobs, on the given machine such that the provided resources are assigned to the jobs in an optimal way. Scheduling provides us the starting and the completion time for each operation or job.

A Scheduling problems in the context of the paper is defined as:

According to Peter Brucker [1], a Scheduling problem is defined as following: Given m machines Mj (j= 1, 2...m) and n jobs Ji (i= 1, 2…n), a schedule now is allocation of one or more time intervals for each job on one or more machines.

The thesis goes on to demonstrate the use of applying flow theory to a particular subset of matching resources to needs using graphs. The thesis concludes with:

Open Shop Scheduling problem is different from other scheduling problems. This shop problem is very closely related to matching. Although, we have surveyed number of problems where Hall technique works, yet there are unexplored problems where matching is applied. The connection between algorithms of parallel machines and open shop are more close than other shop problems. In this thesis, we have learnt flow techinques are useful and seem to be one of the strongest tools available for non-NP Complete scheduling problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.