Title

Minimizing Makespan On Parallel Machines With Release Time And Machine Eligibility Restrictions

Abstract

Scheduling in the presence of machine eligibility restrictions when not all machines can process all the jobs is a practical problem into which there has been little research. Pinedo demonstrated that the least flexible job (LFJ) rule was optimal for minimizing makespan in a parallel machine environment (with equal processing times) when there are machine eligibility restrictions, the machine eligibility sets are nested, and no release time constraint exists. The results presented in this paper demonstrate that for the more realistic case when the machine eligibility sets are not nested (with unequal processing times known when a job is released), the longest processing time (LPT) rule performs better than the LFJ rule in the presence or absence of release time stipulations. The experimental results show that the order (job selection first or machine selection first) does not matter, which is consistent with Pinedo's observation. The new heuristics that are evaluated in this paper provide important results for the parallel machine scheduling problem and their applications in the semiconductor industry, which motivated this research.

Publication Date

3-15-2004

Publication Title

International Journal of Production Research

Volume

42

Issue

6

Number of Pages

1243-1256

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1080/00207540310001631584

Socpus ID

1242265218 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/1242265218

This document is currently not available here.

Share

COinS