A Geometric Model and a Graphical Algorithm for a Sequencing Problem

descriptionPublicationkeyboard_double_arrow_right Article 01 Dec 1963 English Publisher:Institute for Operations Research and the Management Sciences (INFORMS)Journal:Operations Research, volume 11, pages 889-900 (issn: 0030-364X, eissn: 1526-5463,

Copyright policy )

Authors: Hardgrave, W. W.; Nemhauser, G. L.;

doi: 10.1287/opre.11.6.889

A Geometric Model and a Graphical Algorithm for a Sequencing Problem

- Summary
- Subjects
- Metrics

Abstract

A geometric model is given for the problem of scheduling N jobs on M machines so that the total time needed to complete the processing of all jobs is minimized. This model leads to a graphical algorithm, the essence of which is the determination of a shortest path between two nodes in a finite network. Particular attention is given to the case of 2 jobs for which the algorithm developed is simple and efficient. The theoretical analysis is then extended to the general case. Computational problems arise in the general case primarily because of the difficulty of constructing the network.

Related Organizations

Johns Hopkins University
United States
Bell Labs
United States

Keywords

operations research

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	46
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average