Article ID: | iaor2001970 |
Volume: | 22 |
Issue: | 4/5 |
Start Page Number: | 137 |
End Page Number: | 143 |
Publication Date: | May 1998 |
Journal: | Operations Research Letters |
Authors: | Matsui Tomomi, McCormick S.T., Iwata S. |
Keywords: | scheduling |
Bipartite network flow problems naturally arise in applications such as selective assembly and preemptive scheduling. This paper presents fast algorithms for these problems that take advantage of special properties of the associated bipartite networks. We show a connection between selective assembly and the earliest due date (EDD) scheduling rule, and we show that EDD can be implemented in linear time when the data are already sorted. Our main result uses a Monge property to get a linear-time algorithm for selective assembly with a monotone convex loss function.