Scheduling parallel dedicated machines under a single non-shared resource

The scheduling problem of minimizing the makespan for m parallel dedicated machines under single resource constraints is considered. For different variants of the problem the complexity status is established. Heuristic algorithms employing the so-called group technology approach are presented and their worst-case behavior is examined. Finally, a polynomial time approximation scheme is presented for the problem with fixed number of machines.

Hall conditions for edge-weighted bipartite graphs

A weighted variant of Hall's condition for the existence of matchings is shown to be equivalent to the existence of a matching in a lexicographic product. This is used to introduce characterizations of those bipartite graphs whose edges may be replicated so as to yield semiregular multigraphs or, equivalently, semiregular edge-weightings. Such bipartite graphs will be called semiregularizable. Some infinite families of semiregularizable trees are described and all semiregularizable trees on at most 11 vertices are listed. Matrix analogues of some of the results are mentioned and are shown to imply some of the known characterizations of regularizable graphs.