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.
With the current emphasis on the just in time (JIT) production philosophy, it is crucial to meet the target due dates in order to reduce the inventory costs of modern enterprises and satisfy the demands of the customers [1] and [2]. 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 [3]. Hence, meeting due dates has always been one of the most important objectives in scheduling and supply chain management [4], [5], [6], [7], [8], [9], [10], [11], [12] and [13] and due date assignment scheduling problems have attracted many scholars. Pioneering research in this area was done by Seidmann et al. [14] and Panwalkar et al. [15] in the 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. [16].
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 [17], [18], [19], [9], [20], [21], [10], [22] and [23]. For example, Cheng [19] 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 minimizes 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 [22] 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–tardiness cost. Two efficient heuristics with time complexity View the MathML sourceO(nlogn) were proposed. Xia et al. [23] investigated job sequencing and distinct due date assignment for a single machine shop with random processing times. The customer service level is taken into consideration in [20] and [21] for the due date assignment problem in a stochastic environment. An asymptotically optimal due date setting procedure with optimal customer service level and View the MathML sourceO(nlogn) time complexity to minimize expected total earliness–tardiness costs was given in [21].
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 fuzzy sets to treat different sources of uncertainty, particularly when intuition and judgement play an important role [24] and [25]. There have been some successful applications of using fuzzy sets to model various manufacturing parameters, such as fuzzy customer demand [26], fuzzy due dates and fuzzy processing times [27], [28], [29], [30], [31], [32], [33], [34], [35] and [36], fuzzy job precedence relations [37] and [38] and so on. For a recent survey on fuzzy scheduling, the readers are referred to Dubois et al. [39].
In addition to some uncertainty inherent in practical production scheduling problems, there are usually precedence constraints among jobs [40], [41] and [42]. From the practical aspects in considering integrated processes as single machine systems [43] and [44], it is important to predict clearly the due date of the integrated processes with precedence constraints among processes and uncertain completion times for the manufacturers. For this case, a scheduling model with uncertain processing times and precedence constraints was proposed in [45], in which both jobs’ earliness and tardiness costs are incorporated into scheduling decisions.
Note that, in a fuzzy scheduling model such as [45], they did not take the significance of γγ-cut sets of fuzzy parameters into consideration. Indeed, the information expressed by different cut sets of a fuzzy variable may be different [46]. Hence, it is worth investigating how to make better decisions by making full use of the information expressed by fuzzy variables in the fuzzy scheduling model. In this direction, this paper investigates due date assignment problems with fuzzy processing times and precedence constraints among jobs on a single machine. First, we construct scheduling model in which we use the weighting functions to describe the importance of different γγ-cut sets of fuzzy variables. The object is to determine an optimal schedule and respective due dates to minimize the total weighted possibilistic mean value of the weighted earliness–tardiness costs. Then, we drive an optimal polynomial time algorithm for the considered problem when there are no precedence constraints among jobs. Also, we show that if general precedence constraints are involved, the problem is NP-hard. Then, four reduction rules are put forward to simplify the constraints without changing the optimal schedule. Moreover, an optimal polynomial time algorithm is proposed when the precedence constraint is a tree or a collection of trees. Finally, a numerical experiment shows that our method is effective.
n this paper, the problem View the MathML source1|p̃,prec|∑i=1nM̄fi(wi(eiẼi+tiT̃i)) was investigated. An optimal polynomial time algorithm for View the MathML source1|p̃|∑i=1nM̄fi(wi(eiẼi+tiT̃i)) was given. Four reduction rules under optimal customer service levels for the NP-hard problem View the MathML source1|p̃,prec|∑i=1nM̄fi(wi(eiẼi+tiT̃i)) were proposed to simplify the constraints without changing the optimal schedule. Based on these, it was shown that View the MathML source1|p̃,trees|∑i=1nM̄fi(wi(eiẼi+tiT̃i)) can be solved in polynomial time.
