SINGLE MACHINE DUE DATE ASSIGNMENT SCHEDULING PROBLEM WITH PRECEDENCE CONSTRAINTS AND CONTROLLABLE PROCESSING TIMES IN FUZZY ENVIRONMENT

Abstract

In this paper, a due date assignment scheduling problem with precedence constraints and controllable processing times<br /> in uncertain environment is investigated, in which the basic processing time of each job is assumed to be the symmetric trapezoidal fuzzy number, and the linear resource consumption function is used.<br />The objective is to minimize the crisp possibilistic mean (or expected) value of a cost function that<br />includes the costs of earliness, tardiness, makespan and resource consumption jointly by scheduling the jobs under precedence constraints and determining the due date and the resource allocation amount<br /> satisfying resource constraints for each job. First, the problem is shown to be NP-hard. Furthermore, an optimal algorithm with polynomial time for the special case of this problem is put forward. Moreover,<br /> an efficient 2-approximation algorithm is presented based on solving the relaxation of the problem. Finally, the numerical experiment is given, whose results show that our method is promising.