Minimizing makespan on parallel machines with release time and machine eligibility restrictions

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 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.