A linear programming-based method for job shop scheduling

Bülbül, Kerem and Kaminsky, Philip (2010) A linear programming-based method for job shop scheduling. (Submitted)

There is a more recent version of this item available.

Preview

PDF (This is a RoMEO green publisher -- author can archive pre-print (ie pre-refereeing)) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
470Kb

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.

Item Type:	Article
Uncontrolled Keywords:	job shop; shifting bottleneck; intermediate inventory holding costs; non-regular objective; optimal timing problem; linear programming; sensitivity analysis; single machine; earliness/tardiness.
Subjects:	T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
ID Code:	16251
Deposited By:	Kerem Bülbül
Deposited On:	29 Dec 2010 12:06
Last Modified:	17 Feb 2012 10:23

Available Versions of this Item

A linear programming-based method for job shop scheduling. (deposited 29 Dec 2010 12:06) [Currently Displayed]
- A linear programming-based method for job shop scheduling. (deposited 17 Feb 2012 10:23)

Repository Staff Only: item control page