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., ri < rj implies di ≤ dj). 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.
International Journal of Operational Research, 2009 Vol.4 No.3, pp.231 - 249
Available online: 17 Feb 2009 *Full-text access for editors Access for subscribers Purchase this article Comment on this article