Title: Single machine scheduling to minimise number of expedited jobs

Authors: S.S. Panwalkar

Addresses: Carey Business School, Johns Hopkins University, 100 International Drive, Baltimore, MD 21202, USA

Abstract: We consider a static, deterministic, n jobs-single machine model in which jobs have release dates that can be expedited, if needed, to keep the machine busy without idle time. The objective is to minimise the number of expedited jobs. We propose a polynomially-bounded solution procedure [O(n log n)] that is antithetic to a well-known procedure for minimising the number of tardy jobs.

Keywords: single machine scheduling; expediting; expedited jobs; release dates; idle time; tardy jobs.

DOI: 10.1504/IJPS.2013.059674

International Journal of Planning and Scheduling, 2013 Vol.1 No.4, pp.235 - 241

Received: 07 Apr 2012
Accepted: 14 Oct 2012
Published online: 30 Jun 2014 *