《2016 A Linear Programming Based Method for Job Shop Scheduling》.pdf

A Linear Programming-Based Method for Job Shop Scheduling Kerem Bulbul ¨ ¨ Sabancı University, Manufacturing Systems and Industrial Engineering, Orhanlı-Tuzla, 34956 Istanbul, Turkey bulbul@sabanciuniv.edu Philip Kaminsky Industrial Engineering and Operations Research, University of California, Berkeley, CA kaminsky@ieor.berkeley.edu A: 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 schedul- ing 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. 1. Introduction The job shop scheduling problem, in which each job in a set of orders requires processing on a unique subset of available resources, is a fundamental operations research problem, encompassing many additional classes of problems (single machine scheduling, flow shop scheduling, etc). While from an application perspective this