Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes. (English) Zbl 1198.90174
Summary: 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.
References:
| [1] | DOI: 10.1080/00207540410001711863 · doi:10.1080/00207540410001711863 |
| [2] | DOI: 10.1016/j.mcm.2005.01.005 · Zbl 1099.90018 · doi:10.1016/j.mcm.2005.01.005 |
| [3] | DOI: 10.1109/TEPM.2006.887355 · doi:10.1109/TEPM.2006.887355 |
| [4] | DOI: 10.1016/0167-6377(86)90104-5 · Zbl 0594.90045 · doi:10.1016/0167-6377(86)90104-5 |
| [5] | DOI: 10.1080/00207540500525254 · Zbl 1095.90039 · doi:10.1080/00207540500525254 |
| [6] | DOI: 10.1080/002075499192020 · Zbl 0939.90537 · doi:10.1080/002075499192020 |
| [7] | DOI: 10.1287/opre.40.4.764 · Zbl 0759.90046 · doi:10.1287/opre.40.4.764 |
| [8] | Morton TE, Heuristic scheduling systems: with applications to production systems and project management (1993) |
| [9] | Pearn WL, IIE Transactions 34 pp 211– (2002) |
| [10] | DOI: 10.1016/S0377-2217(98)00391-9 · Zbl 0971.90033 · doi:10.1016/S0377-2217(98)00391-9 |
| [11] | DOI: 10.1080/00207549408957026 · Zbl 0906.90095 · doi:10.1080/00207549408957026 |
| [12] | DOI: 10.1080/00207540412331270450 · Zbl 1114.90394 · doi:10.1080/00207540412331270450 |
| [13] | Wolsey LA, Integer programming, 1. ed. (1998) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
