Title: Scheduling a burn-in oven with non-agreeable release times and due dates

Authors: M. Mathirajan, Appa Iyer Sivakumar

Addresses: Department of Management Studies, Indian Institute of Science, Bangalore 560 012, India. ' School of Mechanical and Aerospace Engineering, Nanyang Technological University, Singapore MIT Alliance, 50, Nanyang Avenue, 639798, Singapore

Abstract: We consider the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modelled as batch processing machines. Most of the studies assume that ready times and due dates of jobs are agreeable (i.e., r_i < r_j implies d_i ≤ d_j). In many real world applications, the agreeable property assumption does not hold. Therefore, in this paper, scheduling of a single burn-in oven with non-agreeable release times and due dates along with non-identical job sizes as well as non-identical processing of time problem is formulated as a Non-Linear (0-1) Integer Programming optimisation problem. The objective measure of the problem is minimising the maximum completion time (makespan) of all jobs. Due to computational intractability, we have proposed four variants of a two-phase greedy heuristic algorithm. Computational experiments indicate that two out of four proposed algorithms have excellent average performance and also capable of solving any large-scale real life problems with a relatively low computational effort on a Pentium IV computer.

Keywords: scheduling; burn-in ovens; makespan; nonlinear integer programming; greedy heuristics; computational experiments; release times; due dates; semiconductor manufacturing; batch processing.

DOI: 10.1504/IJOR.2009.023283

International Journal of Operational Research, 2009 Vol.4 No.3, pp.231 - 249

Published online: 17 Feb 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article