Some Optimum Algorithms for Scheduling Problems with Changeover Costs
T.C. Hu,
Department of Computer Science,
University of Californai, San Diego, USA.
Y.S. Kuo,
Department of Computer Science??,
National Chiao Tang University, Hsinchu, Taiwan
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
We consider a production line that can produce one of n
items per day.
The demand schedule for all items is known in advance, and all items
must be produced on or before their deadlines.
We want a production schedule that meets all demand deadlines and
minimizes the total changeover cost.
The changeover cost has a special structure: it is (i) one dollar
if the production line changes from producing item i to
item j and i is less than j, and (ii) zero
if i is greater than or equal to j.
We also consider multiple identical production lines with all demands
due at the end of every month, and assume that there is exactly
enough demand at the end of every month.
We obtain optimum production schedules for both the singleline and
multipleline case.

The pdf file. (From JSTOR)

Please send me a note
if you download a copy  Thanks!

Appears in Journal of the Operations Research Society of
America (JORSA), 35 (1987) 9499.
Selected papers that refer to this paper:

A. Barlatt, A. Cohn, Y. Fradkin, O. Gusikhin and C. Morford,
Using composite variable modeling to achieve realism
and tractability in production planning: An example from
automotive stamping,
IIE (Institute of Industrial Engineers) Transactions, 41 (2009) 421436.

Jans, R., Degraeve, Z.,
Modeling industrial lot sizing problems: A review,
International Journal of Production Research 46 (6), 2008, pp. 16191643.

Veeramani, D., Wang, K.J.,
Bid construction scheme for job flow time reduction in auctionbased
fullydistributed manufacturing systems,
International Journal of Advanced Manufacturing Technology 28 (56),
2006, pp. 541550.

Mikhail Y. Kovalyov , Marcus Pattloch , G. Schmidt,
A polynomial algorithm for lotsize scheduling of two type tasks,
Information Processing Letters, v.83 n.4, p.229235, 31 August 2002.

Chen, J.F.,
Unrelated parallel machine scheduling with secondary resource
constraints,
International Journal of Advanced Manufacturing Technology 26 (3),
2005, pp. 285292.

David M. Miller , HuiChuan Chen , Jessica Matson , Qiang Liu,
A Hybrid Genetic Algorithm for the Single Machine Scheduling Problem,
Journal of Heuristics, v.5 n.4, p.437454, December 1999.
Back to list of publications.