Single machine due window assignment scheduling problem with precedence constraints and fuzzy processing times

摘要

In recent years, due window assignment scheduling problems deriving from just-in-time supply chain management have been studied extensively. However, precedence constraints and uncertain processing times of jobs are rarely involved simultaneously in the studies. In this paper, a single machine due window assignment scheduling problem with uncertain processing times, precedence constraints and due window size constraints is investigated, in which the processing times of jobs are presented by fuzzy numbers. The objective is to minimize the mean value of the total earliness-tardiness penalties. An optimal polynomial time algorithm is proposed for the problem when there are no precedence constraints among jobs. Note that the problem with general precedence constraints is NP-hard. An efficient 2-approximation algorithm is proposed for the general constraint problem based on linear programming relaxation. The experimental results show that the proposed methods are effective and promising.