Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes
Authors:
- 30 June 2009
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 47 (18) , 5109-5128
Abstract
This paper considers the parallel batch processing machine scheduling problem which involves the constraints of unequal ready times, non-identical job sizes, and batch dependent processing times in order to sequence batches on identical parallel batch processing machines with capacity restrictions. This scheduling problem is a practical generalisation of the classical parallel batch processing machine scheduling problem, which has many real-world applications, particularly, in the aging test operation of the module assembly stage in the manufacture of thin film transistor liquid crystal displays (TFT-LCD). The objective of this paper is to seek a schedule with a minimum total completion time for the parallel batch processing machine scheduling problem. A mixed integer linear programming (MILP) model is proposed to optimise the scheduling problem. In addition, to solve the MILP model more efficiently, an effective compound algorithm is proposed to determine the number of batches and to apply this number as one parameter in the MILP model in order to reduce the complexity of the problem. Finally, three efficient heuristic algorithms for solving the large-scale parallel batch processing machine scheduling problem are also provided.Keywords
This publication has 13 references indexed in Scilit:
- Multiple Orders Per Job Compatible Batch SchedulingIEEE Transactions on Electronics Packaging Manufacturing, 2006
- Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizesInternational Journal of Production Research, 2006
- Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready timesComputers & Operations Research, 2005
- Mixed integer formulation to minimize makespan in a flow shop with batch processing machinesMathematical and Computer Modelling, 2004
- Minimizing makespan on parallel batch processing machinesInternational Journal of Production Research, 2004
- Minimizing the total machine workload for the wafer probing scheduling problemIIE Transactions, 2002
- Minimizing makespan on a single burn-in oven in semiconductor manufacturingEuropean Journal of Operational Research, 2000
- Minimizing makespan on a single batch processing machine with dynamic job arrivalsInternational Journal of Production Research, 1999
- Efficient Algorithms for Scheduling Semiconductor Burn-In OperationsOperations Research, 1992
- Efficient scheduling algorithms for a single batch processing machineOperations Research Letters, 1986