点击次数：

论文类型：期刊论文

发表时间：2011-12-01

发表刊物：COMPUTERS & MATHEMATICS WITH APPLICATIONS

收录刊物：Scopus、SCIE、EI

卷号：62

期号：11

页面范围：4126-4139

ISSN号：0898-1221

关键字：Scheduling; Earliness-Tardiness costs; Due date assignment; Customer service level; The weighted possibilistic mean value and variance

摘要：In this paper, it is investigated how to sequence jobs with fuzzy processing times and predict their due dates on a single machine such that the total weighted possibilistic mean value of the weighted earliness-tardiness costs is minimized. First, an optimal polynomial time algorithm is put forward for the scheduling problem when there are no precedence constraints among jobs. Moreover, it is shown that if general precedence constraints are involved, the problem is NP-hard. Then, four reduction rules are proposed to simplify the constraints without changing the optimal schedule. Based on these rules, an optimal polynomial time algorithm is proposed when the precedence constraint is a tree or a collection of trees. Finally, a numerical experiment is given. (C) 2011 Elsevier Ltd. All rights reserved.