Scheduling parallel machines with resource-dependent processing times

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