A fast bipartite network flow algorithm for selective assembly

A fast bipartite network flow algorithm for selective assembly

0.00 Avg rating0 Votes
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: , ,
Keywords: scheduling
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.