Parallel Machine Scheduling with the Total Weighted Delivery Time Performance Measure in Distributed Manufacturing

Abstract In this paper, we address a parallel machine scheduling problem that is motivated by distributed manufacturing settings. Our objective is to minimize the total weighted delivery time (TWD) after including delivery durations for the jobs. We first analyse several special cases which can be solved to optimality in polynomial time. Based on the gained insights of the analysis, constructive algorithms are proposed for the general problem setting. A greedy randomized adaptive search (GRASP) framework is proposed to guide the subordinate heuristics to further improve algorithm performance for large-sized problem instances. Computational experiments based on randomly generated problem instances are carried out. They demonstrate that the GRASP computes competitive schedules for the special cases. For small problem instances, the GRASP is able to compute optimal solutions. Moreover, it outperforms two genetic algorithms (GAs) that differ in the way how structural properties of optimal solutions are included in terms of both solution quality and computing time.