Single machine scheduling problem with fuzzy due date and processing time

摘要

This paper considers a single machine scheduling problem with fuzzy due date and fuzzy processing time. There are n jobs J_1, J_2, …, J_n to be processed on a single machine. Associated with each job J_j, there is a membership function of due date which describes the degree of satisfaction with respect to the completion time of J_j. The due date is structured similar to a trapezoidal fuzzy set, and the processing time is described as a triangular fuzzy set. The objective is to maximize the minimum grade of satisfaction over given jobs. In this paper. polynomial-time algorithms with O(n~2 logG) are proposed to solve the scheduling problem and are illustrated by means of an example.