A problem expanding parametric programming method for solving the job shop scheduling problem |
| |
Authors: | G. L. Thompson D. J. Zawack |
| |
Affiliation: | (1) Graduate School of Industrial Administration, Carnegie-Mellon University, 15213 Pittsburgh, PA, USA;(2) American Airlines, P.O. Box 619616, 75261-9616 Dallas, Texas, USA |
| |
Abstract: | A new zero-one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts: (a) a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time; (b) a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to thirty-six operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government. |
| |
Keywords: | Job shop scheduling algorithm branch and bound zero-one integer program parametric linear programming problem expansion |
本文献已被 SpringerLink 等数据库收录! |
|