Optimal policies for minimizing total job completion times and deviations from common due dates in unrelated parallel machine scheduling

This paper considers an unrelated parallel machine scheduling problem with a common due date where the objective is to minimize the sum of completion times, earliness, and tardiness durations of the jobs. This paper discovers some properties of the considered problem for restricted and unrestricted common due dates. By using these properties, the paper shows the existence of some optimal policies for the problem. Furthermore, optimal policies for the problem are found. According to our main findings, optimal policies for the problem are to increase the number of early jobs, to use the shortest processing time dispatching rule for tardy jobs, and to distribute tardy jobs on machines with tardy workloads that differ from each other as much as possible. These strategies for the problem are new to the literature and the problem has the potential to be extended. Using these strategies, the paper presents a novel heuristic algorithm for the problem that is rarely studied in the literature. Furthermore, the proposed heuristic is compared with two existing algorithms by generating some test instances for experimental study. The experimental study shows that the proposed heuristic outperforms other algorithms. Furthermore, the paper discusses which components of our proposed solution approach have impacts on the solution quality.