A linear programming‐based method for job shop scheduling

A linear programming‐based method for job shop scheduling

0.00 Avg rating0 Votes
Article ID: iaor20132814
Volume: 16
Issue: 2
Start Page Number: 161
End Page Number: 183
Publication Date: Apr 2013
Journal: Journal of Scheduling
Authors: ,
Keywords: programming: linear, heuristics
Abstract:

We present a decomposition heuristic for a large class of job shop scheduling problems. This heuristic utilizes information from the linear programming formulation of the associated optimal timing problem to solve subproblems, can be used for any objective function whose associated optimal timing problem can be expressed as a linear program (LP), and is particularly effective for objectives that include a component that is a function of individual operation completion times. Using the proposed heuristic framework, we address job shop scheduling problems with a variety of objectives where intermediate holding costs need to be explicitly considered. In computational testing, we demonstrate the performance of our proposed solution approach.

Reviews

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