Hits:

Indexed by:期刊论文

Date of Publication:2011-12-01

Journal:COMPUTERS & MATHEMATICS WITH APPLICATIONS

Included Journals:Scopus、SCIE、EI

Volume:62

Issue:11

Page Number:4126-4139

ISSN No.:0898-1221

Key Words:Scheduling; Earliness-Tardiness costs; Due date assignment; Customer service level; The weighted possibilistic mean value and variance

Abstract: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.