Scheduling parallel machines with resource-dependent processing times

Ling-Huey Su and Chun-Yuan Lien

International Journal of Production Economics, 2009, vol. 117, issue 2, 256-266

Abstract: Scheduling parallel machines with resource-dependent processing time is common in many operations management, especially in breaking processing bottlenecks in the Theory of Constraint and lean production. This study considers the problem of scheduling a set of jobs on parallel machines when the processing time of each job depends on the amount of resource consumed. Such scheduling aims to determine the allocation of resources to jobs and jobs to machines to minimize the makespan. The problem has been proven to be NP-hard even for the fixed job processing times. This study first proposes a heuristic called CL for minimizing makespan in the parallel machines problem [short parallel]Cmax) and then compares it with the LISTFIT heuristic of Gupta and Ruiz-Torres (2001), which is currently regarded as the best heuristic for solving this problem. Experimental results indicate that the CL heuristic outperforms the LISTFIT heuristic in terms of solution quality and computation time. Two distinct procedures, RA1 and RA2, which optimally allocate resources with and without a fixed job sequence, respectively, are applied to evaluate the benefits of resource flexibility. Two heuristics, H1 and H2, are proposed by combining the CL procedure with RA1 and RA2, respectively, to solve the problem of combining P[short parallel]Cmax with resource allocation. Computational experiments show the average solution quality of H2 is 99.65%, ensuring that resources should be distributed to jobs in advance.

Keywords: Parallel; machines; Resource-dependent; processing; times; Heuristics; Makespan (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925-5273(08)00361-7
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:117:y:2009:i:2:p:256-266

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().