Optimization Online


A Linear Programming-Based Method for Job Shop Scheduling

Kerem Bulbul (bulbul***at***sabanciuniv.edu)
Philip Kaminsky (kaminsky***at***ieor.berkeley.edu)

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.

Keywords: job shop; shifting bottleneck; intermediate inventory holding costs; non-regular objective; optimal timing problem; linear programming; sensitivity analysis; single machine; earliness/tardiness.

Category 1: Applications -- OR and Management Sciences

Citation: Bulbul, K. and Kaminsky, P. (2013). "A Linear Programming-Based General Method for Job Shop Scheduling." Journal of Scheduling, 16(2):161-183. doi: 10.1007/s10951-012-0270-4

Download: [PDF]

Entry Submitted: 12/26/2010
Entry Accepted: 12/26/2010
Entry Last Modified: 05/11/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society