دستگاه واحد با توجه به تخصیص تاریخ مشکل زمان بندی همراه با سطح خدمات مشتری در محیط فازی

Due date assignment scheduling problems with deterministic and stochastic parameters have been studied extensively in recent years. In this paper, we consider a single machine due date assignment scheduling problem with uncertain processing times and general precedence constraint among the jobs. The processing times of the jobs are assumed to be fuzzy numbers. We first propose an optimal polynomial time algorithm for the problem without precedence constraints among jobs. Then, we show that if general precedence constraint is involved, the problem is NP-hard. Finally, we show that if the precedence constraint is a tree or a collection of trees, the problem is still polynomially solvable.

The supply chain management in modern enterprises demands that the suppliers deliver goods as close to the required dates as possible in order to reduce the inventory costs. The customers may demand that the suppliers meet contracted delivery dates or face large penalties [47]. With the current emphasis on the just in time (JIT) production philosophy, it is crucial to meet the target due date [6]. An early job completion results in inventory carrying costs, such as storage and insurance costs. On the other hand, a tardy job completion results in penalties, such as loss of customer goodwill and damaged reputation [27]. Hence, meeting due dates has always been one of the most important objectives in scheduling and supply chain management [1], [3], [4], [5], [9], [12], [24], [29], [37] and [46]. Pioneering research in the area of due date assignment scheduling problems was done by Seidmann et al. [45] and Panwalkar et al. [40] in 1980s. Seidmann et al. studied a distinct due date assignment scheduling problem with the objective to assign a due date for each job and find an optimal schedule of all jobs such that the total penalties are minimized. An optimal procedure was proposed to assign due dates and sequence all jobs. Panwalkar et al. investigated a common due date assignment problem with the objective to assign a common due date to all jobs and schedule the jobs such that the total penalties reach the minimal value. An optimal polynomial bound scheduling algorithm was proposed. Since then numerous extensions and special cases with deterministic parameters have been studied, as reflected in many of the 130 references mentioned in the survey paper of Gordon et al. [23]. Due to the uncertainty inherent in production scheduling, mainly uncertainty in processing times, many scholars applied conventional concepts of randomness and probability distributions to study the due date assignment scheduling problem [7], [10], [11], [42], [43], [49] and [51]. For example, Cheng [11] considered a job sequencing and distinct due date assignment problem with random processing times on a single machine. The objective is to find the optimal combination of due dates and job sequence that jointly minimize the expected value of the total cost of assigning long due dates and missing the due dates. A polynomial bound algorithm was given to assign due dates and find the optimal job sequence. Soroush [49] studied the scheduling problem of simultaneous due-date determination and sequencing of a set of the jobs on a single machine where processing times are random variables and job earliness and tardiness costs are distinct. The objective is to determine the optimal sequence and the optimal due-dates that jointly minimize the expected total earliness and tardiness cost. Two efficient heuristics with time complexity O View the MathML source(nlogn) were proposed. Xia et al. [51] investigated the job sequencing and a distinct due date assignment for a single machine shop with random processing times. The customer service level is taken into consideration in [42] and [43] for due date assignment problem in stochastic environment. An asymptotically optimal due dates setting procedure with optimal customer service level and O View the MathML source(nlogn) time complexity to minimize expected total early-tardy cost was given in [43]. However, in real world production scheduling problems, probability distributions for some parameters cannot be obtained with complete confidence in some cases in which there is no evidence recorded in the past, or there is lack of evidence available, or simply the evidence does not exist. In order to make full use of the imprecise data or incomplete information available, some scholars use the fuzzy sets to treat different sources of uncertainty, particularly when intuition and judgement play an important role [44] and [48]. There has been some successful applications for using fuzzy sets to model various manufacturing parameters such as fuzzy customer demand [41], fuzzy due dates and fuzzy processing times [18], [21], [22], [30], [31], [32], [35], [38], [50] and [52], fuzzy job precedence relations [28] and [39] and so on. For a recent survey on fuzzy scheduling, the readers are referred to Dubois et al. [17]. In addition to some uncertainty inherent in practical production scheduling problems, there are usually precedence constraints among jobs [13], [19] and [36]. From the practical aspects in considering integrated processes as single machine systems [2] and [14], it is important to predict clearly the due date of the integrated process with precedence constraint and uncertain completion time for the manufacturers. To the best of our knowledge, there does not exist any research on due date assignment scheduling problem with uncertain processing times and precedence constraints when both jobs’ earliness and tardiness costs are incorporated into scheduling decisions. In this paper, we study a single machine due date assignment scheduling problem with fuzzy processing times and general precedence constraints. The object is to assign a due date to each job and find an optimal schedule of a set of jobs so that the crisp possibilistic mean (or expected) value of total earliness-tardiness penalties is minimized. Furthermore, the customer service level of the due date in fuzzy environment is introduced to describe the quality of the due date. We also drive an optimal polynomial time algorithm for the considered scheduling problem. Then, we show that if general precedence constraint is involved, the problem is NP-hard. In order to simplify the precedence constraints among jobs, four reduction transformations are proposed which allow us to simplify the precedence constraints without changing the optimal schedule. Based on these four reduction transformations, an optimal polynomial time algorithm for the considered scheduling problem is given when the precedence constraint is a tree or a collection of trees. Comparisons are also made with the method proposed in [43]. The rest of the paper is organized as follows. In Section 2, we give a formal description of the considered problem and some notations to be used. In Section 3, we propose an optimal polynomial time algorithm based on the concept of optimal service level for the considered problem. In Section 4, we show that if general precedence constraint among jobs is involved, the problem becomes NP-hard, and it is still polynomially solvable if the precedence constraint is a tree or collection of trees. In Section 5, comparisons are made with the method proposed in [43]. In Section 6, we present some concluding remarks.

In this paper, the due date assignment scheduling problem with general precedence constraint and optimal customer service level in a fuzzy single machine environment was studied. An optimal polynomial time algorithm for View the MathML source1|p˜|M¯∑i=1neiE˜i+tiT˜i was proposed. It was shown that View the MathML source1|prec,p˜|M¯∑i=1neiE˜i+tiT˜i is NP-hard. Furthermore, four reduction transformations under the optimal customer service level were obtained. Based on these four reduction transformations, an optimal polynomial time algorithm was put forward when the precedence constraints are trees or a collection of trees. However, when the general precedence constraints are more complex than trees, we only can simplify the precedence constraints by methods in this paper and can not find the optimal solution for View the MathML source1|prec,p˜|M¯∑i=1neiE˜i+tiT˜i in polynomial time since the problem is NP-hard. So, our future works may focus on designing heuristic algorithms for single machine due date assignment scheduling problems with general precedence constraints among jobs and fuzzy processing times.