A 2-Approximation Algorithm for the Single Machine Due Date Assignment Scheduling Problem in Fuzzy Environment to Minimize the Total Costs

In this paper, we consider the singe machine due date assignment problems with fuzzy processing time and precedence constraints. The objective is to minimize the crisp possibilistic mean value of the total earliness-tardiness penalties. The problems is NP-hard [20]. We put forward an efficient 2-approximation algorithm for this problem based on solving a linear programming relaxation of the problem. The numerical example show the algorithm given in this paper is effective.