Scheduling of Customized Jobs on a Single Machine under Item Availability

Authors: Gerodimos A.E.¹; Glass C.A.²; Potts C.N.³

Source: IIE Transactions, Volume 33, Number 11, November 2001 , pp. 975-984(10)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

We study a problem of scheduling customized jobs on a single-machine. Each job requires two operations: one standard and one specific. Standard operations are processed in batches under item availability, and each batch requires a set-up time. Based on structural properties of the optimal solution, we introduce a generic dynamic programming scheme that builds an optimal schedule by alternately inserting blocks of operations of two distinct types. Our approach yields efficient algorithms for the sum of completion times problem with agreeable processing times and the maximum lateness problem. The number of late jobs problem is shown to be NP-hard in the ordinary sense, but is pseudo-polynomially solvable. A polynomial algorithm is also given for a special case of this problem. Our results indicate the differences between this problem and its counterpart under batch availability.

Language: English

Document Type: Regular paper

Affiliations: 1: Centre for Quantitative Finance, Imperial College, London, SW7 2BX, UK 2: Department of Actuarial Science and Statistics, City University, London, EC1V 0HB E-mail: c.a.glass@city.ac.uk 3: Faculty of Mathematical Studies, University of Southampton, Southampton, SO17 1BJ, UK

Publication date: 2001-11-01