Online scheduling with Lookahead: Multipass assembly lines

Online scheduling with Lookahead: Multipass assembly lines

0.00 Avg rating0 Votes
Article ID: iaor19991208
Country: United States
Volume: 10
Issue: 3
Start Page Number: 331
End Page Number: 340
Publication Date: Jun 1998
Journal: INFORMS Journal On Computing
Authors: ,
Abstract:

This article describes our use of competitive analysis and the on-line model of computation in a product development setting; specifically, we use competitive analysis to evaluate on-line scheduling strategies for controlling a new generation of networked reprographic machines (combination printer–copier–fax machines servicing a network) currently being developed by companies such as Xerox Corporation. We construct an abstract machine model, the multipass assembly line, which not only models networked reprographic machines but also models several common manufacturing environments such as a robotic assembly line or a mixed product assembly line. We consider on-line algorithms with finite lookahead because these machines typically have limited knowledge of the future. We first prove some lower bounds on the performance of any online algorithm with finite lookahead. We then show that simple greedy algorithms achieve competitive ratios that are close to these general lower bounds. In particular, we show that lookahead improves the competitive ratio of these simple greedy algorithms from approximately 2 (with no lookahead) to being arbitrarily close to 1 (for large lookahead). This implies these simple greedy algorithms are realistic candidates for field use in future reprographic products.

Reviews

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