๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A hybrid algorithm for the one machine sequencing problem to minimize total tardiness

โœ Scribed by V. Srinivasan

Publisher
John Wiley and Sons
Year
1971
Tongue
English
Weight
568 KB
Volume
18
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

โœฆ Synopsis

In a recent paper, Hamilton Emmons has established theorems relating to the order in which pairs of jobs are to be processed in an optimal schedule to minimize the total tardiness of performing n jobs on one machine. Using these theorems, the algorithm of this paper determines the precedence relationships among pairs of jobs (whenever possible) and eliminates the first and the last few jobs in an optimal sequence. The remaining jobs are then ordered by incorporating the precedence relationships in a dynamic programming framework. Propositions are proved which considerably reduce the total computation involved in the dynamic programming phase. Computational results indicate that the solution time goes up less than linearly with the size (n) of the problem. The median solution time for solving 50 job problems was 0.36 second on UNIVAC 1108 computer.

๐Ÿ“œ SIMILAR VOLUMES

Decomposition and hybrid simulated annea
Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem
โœ Christos Koulamas ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 93 KB ๐Ÿ‘ 2 views

A polynomial decomposition heuristic is developed for the parallel-machine tardiness problem (P//T V ) by extending the decomposition principle embedded in the single-machine tardiness problem (1//T V ) to a parallel-machine setting. The subproblems generated by the decomposition are solved by an ef

An exact algorithm for the batch sequenc
An exact algorithm for the batch sequencing problem in a two-machine flow shop with limited buffer
โœ A. Agnetis; F. Rossi; G. Gristina ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 295 KB ๐Ÿ‘ 2 views

This paper deals with the problem of makespan minimization in a flow shop with two machines when the input buffer of the second machine can only host a limited number of parts. Here we analyze the problem in the context of batch processing, i.e., when identical parts must be processed consecutively.

A Data Parallel Algorithm for Solving th
A Data Parallel Algorithm for Solving the Region Growing Problem on the Connection Machine
โœ N. Copty; S. Ranka; G. Fox; R.V. Shankar ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 696 KB

Region growing is a general technique for image segmentation, where image characteristics are used to group adjacent pixels together to form regions. This paper presents a parallel algorithm for solving the region growing problem based on the split-andmerge approach, and uses it to test and compare