Accession Number : AD0722822

Title :   A Hybrid Algorithm for the One Machine Sequencing Problem to Minimize Total Tardiness.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Srinivasan,V.

Report Date : NOV 1970

Pagination or Media Count : 24

Abstract : 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 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 only linearly with the size (n) of the problem. The median solution time for solving 50 job problems was 0.36 seconds on UNIVAC 1108 computer. (Author)

Descriptors :   (*DYNAMIC PROGRAMMING, ALGORITHMS), (*MACHINE SHOP PRACTICE, *SCHEDULING), MATRICES(MATHEMATICS), SET THEORY, MANAGEMENT PLANNING AND CONTROL, OPTIMIZATION

Subject Categories : Operations Research
      Mfg & Industrial Eng & Control of Product Sys

Distribution Statement : APPROVED FOR PUBLIC RELEASE