Affiliations: [a] School of Applied Mathematics, Beijing Normal University, Zhuhai, Guangdong, China
| [b] School of International Economics and Business, Nanjing University of Finance & Economics, Nanjing, China
| [c] School of Control Science and Engineering, Dalian University of Technology, Dalian, China
| [d]
The Key Laboratory of Intelligent Control, Zhuhai, Guangdong, China
Abstract: 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.
Keywords: Fuzzy set, fuzzy number, possibilistic mean value and variance, due window assignment scheduling, precedence constraints
