Single machine due window assignment scheduling problem with precedence constraints and fuzzy processing times

Abstract

In recent years, due window assignment scheduling problems deriving from just-in-time supply chain management have been studied extensively. However, precedence constraints and uncertain processing times of jobs are rarely involved simultaneously in the studies. In this paper, a single machine due window assignment scheduling problem with uncertain processing times, precedence constraints and due window size constraints is investigated, in which the processing times of jobs are presented by fuzzy numbers. The objective is to minimize the mean value of the total earliness-tardiness penalties. An optimal polynomial time algorithm is proposed for the problem when there are no precedence constraints among jobs. Note that the problem with general precedence constraints is NP-hard. An efficient 2-approximation algorithm is proposed for the general constraint problem based on linear programming relaxation. The experimental results show that the proposed methods are effective and promising.

Keywords

Fuzzy set fuzzy number possibilistic mean value and variance due window assignment scheduling precedence constraints

1 Introduction

Just-In-Time (JIT) philosophy is usually adopted in the supply chain management by modern enterprises to reduce their inventor costs, helping them to provide higher quality of services and improve their competitive advantages in the global market. It is extensively accepted that the scheduling strategy plays a crucial role in the realization of JIT in a manufacturing environment [1]. One important goal of JIT scheduling model is to discourage early and tardy jobs so as to minimize the earliness-tardiness penalties [24].

In practice, when a customer signs a contract with a supplier, a due date or generally a due window is often specified according to the negotiation between them. It is usually a compromise between the customer’s expectation and the supplier’s estimation that is mainly based on its production schedule [24]. The left end, the right end and the length of the window are called the starting time, the finishing time and the due window size, respectively. If a job is finished in the due window, it is considered to be on time and will not result in any penalty. If a job is completed before the starting time of the due window, it incurs an earliness penalty which usually includes inventory carrying cost, holding cost, and insurance cost. Alternatively, if a job is finished after the finishing time of the due window, it brings about a tardiness penalty which may include loss of customer goodwill, late charges, and loss of sales. Hence, in order to avoid such penalties, it is very important for the enterprises to obtain an optimal production schedule and determine the reasonable due windows for all jobs at the negotiation stage. Such problems are well-known as the due window assignment scheduling problems, which are studied extensively by many scholars [3 , 27]. Cheng et al. [23] investigate the problem of common due window assignment and scheduling of deteriorating jobs and a maintenance activity simultaneously on a single machine. Yin et al. [27] address a single machine batch delivery scheduling problem with an assignable common due window. Liu et al. [16] study a single machine due window assignment and resource allocation scheduling problem with learning and general positional effects. Yang et al. [6] examine some multiple due windows assignment scheduling problems with controllable processing times on a single machine. Janiak et al. [3] consider a due window assignment schedule problem on parallel machines with min-max type criteria, where the time complexity is strong NP-hard. Gerstl and Mosheiov [8] study a due window assignment scheduling problem on parallel uniform machines with job-dependent earliness-tardiness costs. An improved algorithm is then given for the same problem [7]. Yeung et al. [26] investigate a two machine common due windows proportionate flow shop scheduling problem.

However, in many practical applications, the data for the processing times of jobs are usually recorded or collected under the influence of some unexpected noises. Hence, the processing times of jobs are not known exactly in advance. Additionally, the historical data are not abundant for the processing times of jobs to get the probability distributions, which makes it difficult to model the due window assignment scheduling problems by the stochastic models given in [13 , 25]. Furthermore, the intuition and the judgement of a experienced worker play an important role in determining the processing time of a job in practice. For example, a job’s processing time perhaps is approximately 3 hours according to the evaluation of a experienced worker, which can be expressed by fuzzy number $\tilde{3}$ . In general case, it is a better choice to use fuzzy sets to model uncertain processing times in order to make full use of the imprecise data or incomplete information available in due window assignment scheduling problems, just like the successful applications for using fuzzy sets to model various manufacturing parameters in many scheduling problems [4 , 21]. In [10, 11], the due date assignment models with fuzzy processing time are given, whose objectives are to determine the time point (due date) for each job and schedule all jobs to minimize the mean value of the total earliness-tardiness penalties. The polynomial time algorithms are proposed when the precedence constraints are a collection of trees.

Note that, due to the uncertainty inherent scheduling problems, the completion time of a job can not be exactly predicted in advance, but be estimated to lie in a time interval. Hence, there are usually no penalties when the job is completed within a time interval rather than a time point in real-life applications [2]. For example, a time interval usually should be promised by the supplier to deliver goods to the customer, not an exact timing due to the uncertainty. Also, there are more complex precedence constraints between jobs [9, 22]. Hence, it is necessary to study the due window assignment scheduling problems with uncertain processing times and general precedence constraints among jobs. In this direction, this paper investigates the due window assignment problem with fuzzy processing times, general precedence constraints and due window size constraints on a single machine. The objective is to find an optimal job sequence under precedence constraints and determine an optimal due window with due window size constraint for each job such that the crisp possibilistic mean (or expected) value of the total earliness-tardiness penalties is minimized. An optimal polynomial time algorithm is put forward for the considered problem with no precedence constraints among jobs. Note that the problem with general precedence constraint is NP-hard. An efficient 2-approximation algorithm is presented for the general constraint problem based on solving a linear programming relaxation of this kind of scheduling problems. Finally, the numerical experiment is given, whose results show that our methods are promising.

2 The properties and algorithms for the problem

2.1 Preliminaries

A fuzzy number $\tilde{A}$ is a fuzzy set of the real line R with a normal, fuzzy convex and continuous membership function of a bounded support, and the family of fuzzy numbers of the real line R is denoted by $F (R)$ [5]. For $\tilde{A} \in F (R)$ and γ ∈ [0, 1], the crisp set ${\tilde{A}}_{γ}$ defined by ${t \in R | \tilde{A} (t) \geq γ}$ is called the γ-cut set of $\tilde{A}$ . It follows from the definition of fuzzy number that ${\tilde{A}}_{γ}$ is an interval expressed as [a₁ (γ), a₂ (γ)], that is ${\tilde{A}}_{γ} = [a_{1} (γ), a_{2} (γ)] .$

The arithmetic operations of fuzzy numbers based on the extension principle are given in [17] as follows. For $\tilde{A}, \tilde{B} \in F (R)$ with cut sets ${\tilde{A}}_{γ} = [a_{1} (γ), a_{2} (γ)]$ and ${\tilde{B}}_{γ} = [b_{1} (γ), b_{2} (γ)]$ , respectively, then $\tilde{A} + \tilde{B} = ⋃_{γ \in [0, 1]} γ [a_{1} (γ) + b_{1} (γ), a_{2} (γ) + b_{2} (γ)];$ (1) $\tilde{A} - \tilde{B} = ⋃_{γ \in [0, 1]} γ [a_{1} (γ) - b_{2} (γ), a_{2} (γ) - b_{1} (γ)];$ (2) $c \tilde{A} = ⋃_{γ \in [0, 1]} γ [c a_{1} (γ), c a_{2} (γ)] for c > 0;$ (3) $\max {\tilde{A}, \tilde{B}} = ⋃_{γ \in [0, 1]} γ [a_{1} (γ) \lor b_{1} (γ), a_{2} (γ) \lor b_{2} (γ)] .$ (4)

The graphical representations are given for the calculations above with fuzzy numbers in Fig. 1.

Fig.1

The graphical representation for calculations with $\tilde{A}$ and $\tilde{B}$ .

Definition 1. [5] The crisp possibilistic mean value and variance of a fuzzy number $\tilde{A}$ , denoted by $\bar{M} (\tilde{A})$ and Var $(\tilde{A})$ , are defined as $\bar{M} (\tilde{A}) = \int_{0}^{1} γ (a_{1} (γ) + a_{2} (γ)) d γ,$ (5) $Var (\tilde{A}) = \frac{1}{2} \int_{0}^{1} γ (a_{1} (γ) - a_{2} (γ))^{2} d γ .$ (6)

The standard deviation of $\tilde{A}$ is defined by $σ_{\tilde{A}} = \sqrt{Var (\tilde{A})}$ .

By the arithmetic operations of fuzzy numbers and Definition 1, it is easy to get that $\bar{M} (c \tilde{A}) = c \bar{M} (\tilde{A})$ and $\bar{M} (\tilde{A} + \tilde{B}) = \bar{M} (\tilde{A}) + \bar{M} (\tilde{B}) .$

In [5], a triangular fuzzy number $\tilde{A}$ , denoted by (a, α, β) with center a, left-width α > 0 and right-width β > 0, is defined with the membership function

$μ_{\tilde{A}} (x) = {\begin{matrix} 0, & x < a - α; \\ 1 + (x - a) / α, & a - α \leq x < a; \\ 1 - (x - a) / β, & a \leq x \leq a + β; \\ 0, & x > a + β . \end{matrix}$ (7)

When α = β, the triangular fuzzy number is called the symmetric triangular fuzzy number denoted by (a, α).

As it is pointed out in [5], the crisp possibilistic mean value and variance for $\tilde{A} = (a, α)$ are $\bar{M} (\tilde{A}) = a$ and $Var (\tilde{A}) = α^{2} / 6$ , respectively.

2.2 Problem formulation

In this paper, a single machine due window assignment scheduling problem is investigated, in which the jobs have to be processed on a single machine and the scheduler determines a due window for each job in uncertain environment. All jobs are available at time zero; the preemption of jobs and the idle machine times are not allowed; the machine can process at most one job at a time; there are precedence constraints among jobs; the uncertain processing times are modeled by the symmetrical triangular fuzzy numbers. The problem notations used in this paper are presented as follows:

$J = {J_{1}, J_{2}, \dots, J_{n}}$ : jobs set;

$\tilde{p_{i}} = (a_{i}, α_{i}) (a_{i} > 0, α_{i} > 0)$ : fuzzy processing time of job J_i;

$\tilde{C_{i}}$ : completion time of job J_i;

<d_i, d_i+ L_i >: due window of job J_i with the beginning time d_i > 0 and the size L_i > 0;

$\vec{d} = (< d_{1}, d_{1} + L_{1} >, \dots, < d_{n}, d_{n} + L_{n} >)$ : due window vector;

${\tilde{E}}_{i} = \max {d_{i} - \tilde{C_{i}}, 0}$ : earliness of job J_i;

${\tilde{T}}_{i} = \max {\tilde{C_{i}} - (d_{i} + L_{i}), 0}$ : tardiness of job J_i;

e_i > 0: per unit earliness penalties;

t_i > 0: per unit tardiness penalties.

The precedence constraints among jobs in the field of scheduling are usually specified in the form of a directed acyclic graph G, in which each vertex represents a job. We say that J_i precedes J_j or J_j succeeds J_i, written as J_i → J_j, whenever there is a directed path from vertex J_i to vertex J_j in G [14].

Note that, there are many factors affecting the due window size of a job, such as the customer’s demand, the uncertain processing time and the machine’s speed. The most important factor is the uncertainty of the completion time, which means that the due window size is strongly influenced by the standard deviation of the completion time. Usually, a wide due window is not acceptable, since a large due window and delayed job completion reduce the enterprise’s competitiveness and customer service level. Thus, it is necessary to give a constraint for the size of a due window. In this paper, it is assumed that, for each job, there is a linear constraint between the due window size and the standard deviation of the completion time, that is $L_{i} = λ_{i} \sqrt{6} σ_{{\tilde{C}}_{i}} (0 \leq λ_{i} \leq 1, i = 1, \dots, n)$ . For simplicity, the linear constraints are expressed by the vector $\vec{λ} = (λ_{1}, λ_{2}, \dots, λ_{n}) \in [0, 1]^{n}$ , where λ_i is called the ratio of the due window size L_i with respect to ${\tilde{C}}_{i}$ . Our objective is to find a schedule of jobs under the precedence constraints and determine a due window vector $\vec{d} = (< d_{1}, d_{1} + L_{1} >, < d_{2}, d_{2} + L_{2} >, \dots, < d_{n}, d_{n} + L_{n} >)$ with the due window size constraints such that the crisp possibilistic mean (or expected) value of the total earliness-tardiness penalties $\bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ is minimized. The objective function (of both job sequence and due windows) is expressed as $f (π, \vec{d}) = \bar{M} (\sum_{i = 1}^{n} e_{i} max {d_{i} - \tilde{C_{i}}, 0} + t_{i} max {{\tilde{C}}_{i} - d_{i} - L_{i}, 0}) = \bar{M} (\sum_{i = 1}^{n} [e_{i} max {d_{i} - \tilde{C_{i}}, 0} + t_{i} max {\tilde{C_{i}} - d_{i} - λ_{i} \sqrt{6} σ_{{\tilde{C}}_{i},}, 0}]) .$

Extending the standard scheduling notations [12, 20], this problem is denoted as

$\begin{matrix} 1 | prec, \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}}) . \end{matrix}$ (8)

Especially, when there are no precedence constraints among jobs, the problem is denoted as

$1 | \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}}) .$ (9)

Definition 2. Let the completion time and the due window with a given ratio λ of a job be $\tilde{C}$ and <d, d+ L >. If the crisp possibilistic mean value of the job’s earliness-tardiness penalties

$\begin{matrix} \bar{M} (e max {d - \tilde{C}, 0} + t max {\tilde{C} - d - L, 0}) \\ = \bar{M} (e max {d - \tilde{C}, 0} \\ + t max {\tilde{C} - d - λ \sqrt{6} σ_{\tilde{C}}, 0}) \end{matrix}$ (10) reaches minimum when d = d^*, then <d^*, d^*+ L > is called the optimal due window with respect to the completion time $\tilde{C}$ and the ratio λ.

Definition 3. Given a feasible schedule π with a due window vector $\vec{d} = (< d_{1}, d_{1} + L_{1} >, < d_{2}, d_{2} + L_{2} >, \dots, < d_{n}, d_{n} + L_{n} >)$ under the due window size constraints $\vec{λ} = (λ_{1}, \dots, λ_{n})$ . If $\vec{d}$ such that $f (π, \vec{d}) = \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ is minimized, then $\vec{d}$ is called an optimal due window vector with respect to the schedule π and the constraints $\vec{λ}$ .

Definition 4. For a schedule π of {J₁, J₂, ⋯, J_n}, assign a due window <d_i, d_i+ L_i > with a due window size ratio λ_i to J_i (i = 1, ⋯, n). Let $\vec{λ} = (λ_{1}, \dots, λ_{n})$ and $\vec{d} = (< d_{1}, d_{1} + L_{1} >, < d_{2}, d_{2} + L_{2} >, \dots, < d_{n}, d_{n} + L_{n} >)$ , respectively. If $f (π, \vec{d}) = \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ is minimized, then $< π, \vec{d} >$ is called an optimal schedule of jobs. For convenience, π is also called an optimal schedule with the due window vector $\vec{d}$ , or π is optimal.

2.3 The polynomial time algorithm for the problem

1 | \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})

Lemma 1. Let the per unit earliness penalties, the per unit tardiness penalties, the completion time, and the due window size ratio of a job be e, t, $\tilde{C} = (a, α)$ and λ, then there is d^* ∈ [a − (1 + λ) α, a + α] such that <d^*, d^*+ λα > is an optimal due window with respect to the completion time $\tilde{C}$ and the ratio λ.

$\begin{matrix} g (k) = \bar{M} (e max {a + k α - \tilde{C}, 0} + t max {\tilde{C} - a - (k + λ) α, 0}) \\ = {\begin{matrix} - α t (k + λ), & k < - 1 - λ; \\ t [\int_{0}^{1 + k + λ} γ [(1 - k - λ) α - α γ] d γ - \int_{1 + k + λ}^{1} 2 (k + λ) α γ d γ], & - 1 - λ \leq k < - 1; \\ e [\int_{0}^{1 + k} γ [(1 + k) α - α γ] d γ] + t [\int_{0}^{1 + k + λ} γ [(1 - k - λ) α - α γ] d γ - \int_{1 + k + λ}^{1} 2 (k + λ) α γ d γ], & - 1 \leq k < - λ; \\ e [\int_{0}^{1 + k} γ [(1 + k) α - α γ] d γ] + t [\int_{0}^{1 - k - λ} γ [(1 - k - λ) α - α γ] d γ], & - λ \leq k < 0; \\ t [\int_{0}^{1 - k - λ} γ [(1 - k - λ) α - α γ] d γ] + e [\int_{0}^{1 - k} γ [(1 + k) α - α γ] d γ + \int_{1 - k}^{1} 2 k α γ d γ], & 0 \leq k < 1 - λ; \\ e [\int_{0}^{1 - k} γ [(1 + k) α - α γ] d γ + \int_{1 - k}^{1} 2 k α γ d γ], & 1 - λ \leq k \leq 1; \\ e (k + λ) α, & k > 1 . \end{matrix} \end{matrix}$ (11)

By computation, g (k) = αh (e, t, λ, k), where

$h (e, t, λ, k) ≜ {\begin{matrix} - t (k + λ), & k < - 1 - λ; \\ t [\frac{(1 + k + λ)^{3}}{6} - (k + λ)], & - 1 - λ \leq k < - 1; \\ e \frac{(1 + k)^{3}}{6} + t [\frac{(1 + k + λ)^{3}}{6} - (k + λ)], & - 1 \leq k < - λ; \\ e \frac{(1 + k)^{3}}{6} + t \frac{(1 - k - λ)^{3}}{6}, & - λ \leq k < 0; \\ t \frac{(1 - k - λ)^{3}}{6} + e [\frac{(1 - k)^{3}}{6} + k], & 0 \leq k < 1 - λ; \\ e [k + \frac{(1 - k)^{3}}{6}], & 1 - λ \leq k \leq 1; \\ e (k + λ), & k > 1 . \end{matrix}$ (12)

Proof. For a due window <d, d+ L > with the ratio λ, do a linear transformation $d = \bar{M} (\tilde{C}) + k \sqrt{6} σ_{\tilde{C}} = a + k α$ , then <d, d+ L > = < d, d + λα > = < a + kα, a + (k + λ) α >. It implies that the crisp possibilistic mean value of the job’s earliness-tardiness penalties $\bar{M} (e max {d - \tilde{C}, 0} + t max {\tilde{C} - (d + L), 0})$ can be expressed by the function of k(denoted by g (k)), where $g (k) = \bar{M} (e max {a + k α - \tilde{C}, 0} + t max {\tilde{C} - a - (k + λ) α, 0}) .$ Furthermore, by computation, g (k) is given in Equations (11) and (12). It is easy to verify that the function g (k) is continuous respect to k on the set of real numbers, monotone decreasing on (− ∞, −1 − λ) and monotone increasing on (1, + ∞). Hence, there is k^* ∈ [−1 − λ, 1] such that g (k) reaches the minimal value in k^*. It implies that <a+ k^*α, a + k^*α + λα > is an optimal due window respect to the completion time $\tilde{C}$ and the ratio λ. According to k^* ∈ [−1 − λ, 1], it is easy to get d^* = a + k^*α ∈ [a − (1 + λ) α, a + α]. Hence, there exists d^* ∈ [a − (1 + λ) α, a + α] such that <d^*, d^*+ λα > is an optimal due window with respect to the completion time $\tilde{C}$ and the ratio λ. □

According to Equation (12), the function g (k) is a cubic piecewise polynomial of k in [−1 − λ, 1]. Hence we can obtain k^* that minimizes g (k) by the following algorithm:

Algorithm 1.

Step 1. Find the derivative g′ (k) of the cubic piecewise polynomial g (k) in the set R − {−1 − λ, − 1, − λ, 0, 1 − λ, 1}.

Step 2. Find the roots of the derivative g′ (k) if exist.

Step 3. Compute the value of the function g (k) in the set A = {k|g′ (k) =0} ∪ {−1 − λ, − 1, − λ, 0, 1 − λ, 1}.

Step 4. Find the minimal value g (k^*) of the set {g (k) |k ∈ A} and return k^*.

According to Lemma 1 and Algorithm 1, we can assign the optimal due window <a+ k^*α, a + (k^* + λ) α > to the job with the given the completion time $\tilde{C} = (a, α)$ and the ratio λ, where k^* is obtained by Algorithm 1.

Definition 5. Let the completion time and the due window with a given ratio λ of a job be $\tilde{C}$ and <d, d+ L >. $k = (d - \bar{M} (\tilde{C})) / \sqrt{6} σ_{\tilde{C}}$ is called the customer service level of the due window <d, d+ L > with respect to the completion time $\tilde{C}$ and the ratio λ. If $\bar{M} (e max {\bar{M} (\tilde{C}) + k \sqrt{6} σ_{\tilde{C}} - \tilde{C}, 0} + t max {\tilde{C} - \bar{M} (\tilde{C}) - (k + λ) \sqrt{6} σ_{\tilde{C}}, 0})$ reaches the minimal value when k = k^*, then k^* is called an optimal customer service level with respect to the completion time $\tilde{C}$ and the ratio λ.

According to Definition 5, <d^*, d^*+ L > is an optimal due window with respect to the completion time $\tilde{C}$ and the ratio λ if and only if $k^{*} ≜ (d^{*} - \bar{M} (\tilde{C})) / \sqrt{6} σ_{\tilde{C}}$ is an optimal customer service level with respect to $\tilde{C}$ and λ.

Let $\vec{k} = (k_{1}, k_{2}, \dots, k_{n})$ where k_i is the customer service level of the due window <d_i, d_i+ L_i > with the completion ${\tilde{C}}_{i}$ and the due window size ratio λ_i. Definition 5 implies that $d_{i} = \bar{M} (\tilde{C_{i}}) + k_{i} \sqrt{6} σ_{\tilde{C_{i}}}$ . Then the objective function can be represented by $\vec{k}$ as $f (π, \vec{d}) = \sum_{i = 1}^{n} \bar{M} (e_{i} max {\bar{M} (\tilde{C_{i}}) + k_{i} \sqrt{6} σ_{\tilde{C_{i}}} - \tilde{C_{i}}, 0} + t_{i} max {\tilde{C_{i}} - \bar{M} (\tilde{C_{i}}) - (k_{i} + λ_{i}) \sqrt{6} σ_{\tilde{C_{i}}}, 0}) ≜ g (π, \vec{k}) .$ Hence, our objective is also to find a schedule of jobs under precedence constraints and determine the customer service levels $\vec{k} = (k_{1}, k_{2}, \dots, k_{n})$ with due window size constraints to minimize the function $g (π, \vec{k})$ .

$\begin{matrix} g (π, \vec{k}) & = & \bar{M} (\sum_{i = 1}^{n} e_{i} max {\sum_{j = 1}^{i} a_{j} + k_{i} \sum_{j = 1}^{i} α_{j} - \tilde{C_{i}}, 0} + t_{i} max {\tilde{C_{i}} - \sum_{j = 1}^{i} a_{j} - (k_{i} + λ_{i}) \sum_{j = 1}^{i} α_{j}, 0}) \\ = & \sum_{i = 1}^{n} \bar{M} (e_{i} max {\sum_{j = 1}^{i} a_{j} + k_{i} \sum_{j = 1}^{i} α_{j} - \tilde{C_{i}}, 0} + t_{i} max {\tilde{C_{i}} - \sum_{j = 1}^{i} a_{j} - (k_{i} + λ_{i}) \sum_{j = 1}^{i} α_{j}, 0}) \\ = & \sum_{i = 1}^{n} h (e_{i}, t_{i}, λ_{i}, k_{i}) \sum_{j = 1}^{i} α_{j} . \end{matrix}$ (13)

Furthermore, without loss of generality, let π = (J₁, J₂, ⋯, J_n). Then the completion time of job J_i is $\tilde{C_{i}} = (\sum_{j = 1}^{i} a_{j}, \sum_{j = 1}^{i} α_{j})$ (i = 1, ⋯, n). Given a customer service level k_i and a due window size ratio λ_i, the due window of J_i under k_i and λ_i is $< d_{i}, d_{i} + L > = < \sum_{j = 1}^{i} a_{j} + k_{i} \sum_{j = 1}^{i} α_{j}, \sum_{j = 1}^{i} a_{j} + (k_{i} + λ_{i}) \sum_{j = 1}^{i} α_{j} >$ . It follows by Lemma 1 that $g (π, \vec{k})$ can be expressed as Equation (13). In order to analyze the properties of the function $g (π, \vec{k})$ , a notion called the unitary comprehensive penalty of a job is introduced as follows:

Definition 6. Let per unit earliness penalties, per unit tardiness penalties, due window size ratio and due window’s customer service level of a job be e, t, λ and k. Then, w ≜ h (e, t, λ, k) is called the unitary comprehensive penalty of the job under the given customer service level k and the due window size ratio λ.

Lemma 2. For a schedule π with the customer levels $\vec{k}$ and the due window size ratios $\vec{λ}$ , if there are two adjacent jobs J_l and J_k (J_l before J_k) in π such that (w_l/α_l) < (w_k/α_k), then g (π, k) − g (π′, k) >0, where the processing time of job J_i is (a_i, α_i) (i = 1, ⋯, n), and the schedule π′ is obtained from π by adjacent pairwise interchange of J_l and J_k and keeping other jobs remain in their original position.

Fig.2

The adjacent pairwise interchange of J_l and J_k.

Proof. The adjacent pairwise interchange of J_l and J_k is shown as Fig. 2 below. The difference in the values of the objectives under schedules π and π′ is due only to the jobs J_l and J_k. Because the crisp possibilistic mean value of the total penalties of the jobs processed before J_l and J_k is not affected by the interchange. Neither is the crisp possibilistic mean value of the total penalties of the jobs processed after J_l and J_k. Let the sum of α_j for job J_j processed before J_l and J_k be P. According to Equation (13), it is easy to get the crisp possibilistic mean value of the total penalties of J_l and J_k under π is w_l (P + α_l) + w_k (P + α_l + α_k), while under π′ it is w_k (P + α_k) + w_l (P + α_k + α_l). Thus, it is easy to get $\begin{matrix} g (π, k) - g (π^{'}, k) = α_{l} α_{k} (\frac{w_{k}}{α_{k}} - \frac{w_{l}}{α_{l}}) > 0 . □ \end{matrix}$

Lemma 3. Let π = {J_{i
₁}, J_{i
₂}, ⋯, J_{i
_n}} be an optimal schedule with the customer levels $\vec{k} = (k_{i_{1}}, k_{i_{2}}, \dots, k_{i_{n}})$ and the due window size ratios $\vec{λ} = (λ_{1}, λ_{2}, \dots, λ_{n})$ . Let $k_{i_{j}}^{*} (j = 1, 2, \dots, n)$ be obtained by Algorithm 1. Then, $w_{i_{j}} = w_{i_{j}}^{*} ≜ h (e_{i_{j}}, t_{i_{j}}, λ_{i_{j}}, k_{i_{j}}^{*})$ for j = 1, ⋯, n.

Proof. By contradiction. Suppose there is j₀ such that $w_{i_{j_{0}}} = h (e_{i_{j_{0}}}, t_{i_{j_{0}}}, λ_{i_{j_{0}}}, k_{i_{j_{0}}}) \neq h (e_{i_{j_{0}}}, t_{i_{j_{0}}}, λ_{i_{j_{0}}}, k_{i_{j_{0}}}^{*}) = w_{i_{j_{0}}}^{*}$ . Without loss of generality, let j₀ = 1. According to Lemma 1 and Algorithm 1, we have $w_{i_{j}} = h (e_{i_{j}}, t_{i_{j}}, λ_{i_{j}}, k_{i_{j}}) \geq h (e_{i_{j}}, t_{i_{j}}, λ_{i_{j}}, k_{i_{j}}^{*}) = w_{i_{j}}^{*}$ . It follows that

$\begin{matrix} g (π, \vec{k}) & = & \sum_{l = 1}^{n} h (e_{i_{l}}, t_{i_{l}}, λ_{i_{l}}, k_{i_{l}}) \sum_{j = 1}^{l} α_{i_{j}} \\ > & h (e_{i_{1}}, t_{i_{1}}, λ_{i_{1}}, k_{i_{1}}^{*}) α_{i_{1}} \\ + \sum_{l = 2}^{n} h (e_{i_{l}}, t_{i_{l}}, λ_{i_{l}}, k_{i_{l}}^{*}) \sum_{j = 1}^{l} α_{i_{j}} \\ = & g (π, {\vec{k}}^{*}), \end{matrix}$ (14) where ${\vec{k}}^{*} = (k_{i_{1}}^{*}, k_{i_{2}}^{*}, \dots, k_{i_{n}}^{*}) .$ A contradiction appears since π is optimal. □

Known from Lemma 3, it is a necessary condition for an optimal schedule that $w_{j} = h (e_{j}, t_{j}, λ_{j}, k_{j}) = h (e_{j}, t_{j}, λ_{j}, k_{j}^{*})$ , namely, the unitary comprehensive penalty of the job J_i in any optimal schedule is same. Obviously, for any optimal schedule $< π^{*}, {\vec{d}}^{*} >$ , the customer service levels $\vec{k}$ of ${\vec{d}}^{*}$ are the same as ones obtained by Algorithm 1 for all jobs. Also, it is easy to get $k_{i}^{*} (i = 1, \dots, n)$ by Algorithm 1 within O(n) time complexity.

In the rest of the paper, ${\vec{k}}^{*} = (k_{1}^{*}, k_{2}^{*}, \dots, k_{n}^{*})$ is used to denote the optimal service levels obtained by Algorithm 1 for an optimal schedule π of the jobs set $J$ .

Algorithm 2.

Step 1. Input fuzzy processing time (a_i, α_i), per unit earliness penalties e_i, per unit tardiness penalties t_i and due window size ratio λ_i for job J_i (i = 1, ⋯, n).

Step 2. Compute the optimal customer service level k_i by Algorithm 1 and the unitary comprehensive penalty w_i under k_i and λ_i by w_i = h (e_i, t_i, λ_i, k_i) (i = 1, ⋯, n).

Step 3. Schedule the jobs according to the nonincreasing order of w_i/α_i. The schedule is denoted as π.

Step 4. Compute the completion time ${\tilde{C}}_{i}$ of job J_i in the schedule π and assign the due window <d_i, d_i+ L_i > to job J_i where $< d_{i}, d_{i} + L_{i} > = < \bar{M} ({\tilde{C}}_{i}) + k_{i} \sqrt{6} σ_{{\tilde{C}}_{i}}, \bar{M} ({\tilde{C}}_{i}) + (k_{i} + λ_{i}) \sqrt{6} σ_{{\tilde{C}}_{i}} > (i = 1, 2, \dots, n) .$

Step 5. Return π, $\vec{d} = (< d_{1}, d_{1} + L_{1} >, < d_{2}, d_{2} + L_{2} >, \dots, < d_{n}, d_{n} + L_{n} >)$ and $\vec{k} = (k_{1}, k_{2}, \dots, k_{n})$ .

Theorem 1. The problem $1 | \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ can be solved by Algorithm 2 in the polynomial time.

Proof. Assume that there exists an optimal schedule π not obtained by Algorithm 2, whose unitary comprehensive penalty vector under $\vec{k^{*}}$ is denoted by $\vec{w} = (w_{1}, w_{2}, \dots, w_{n})$ . Known from Lemma 3, $w_{i} = h (e_{i}, t_{i}, λ_{i}, k_{i}^{*})$ , which is the same as one obtained by Algorithm 2 for job J_i. The logic of Algorithm 2 implies that there are at least two adjacent jobs J_j and J_k (J_j before J_k in π) such that (w_j/α_j) < (w_k/α_k). Next, let schedule π′ be obtained by interchanging J_j and J_k without changing other jobs. From Lemma 2, we have g (π, k^*) > g (π′, k^*). Thus, a contradiction appears, which implies that the schedule obtained by Algorithm 2 is optimal. Additionally, it is easy to know the time complexity of Algorithm 2 is O (n log n). □

2.4 A 2-approximation algorithm for the problem

1 | prec, \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})

Note that, with a general constraints among jobs, the problem $1 | prec, \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ is NP-hard, since the NP-hard problem in [10] is a special case of the problem considered in this section. Motivated by some polyhedral methods for the single machine scheduling problems [15, 19], a 2-approximation algorithm is designed for 1 $| prec, \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ based on solving a linear programming relaxation of the problem, whose worst case ratio is shown to be 2.

For the problem $1 | prec, \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n}$ $e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ with fuzzy processing time ${\tilde{p}}_{i} = (a_{i}, α_{i})$ , unitary earliness-tardiness penalties vector (e_i, t_i), due window size ratio λ_i and precedence constraints G among jobs, the following notations are used. The standard deviation of fuzzy processing time of job J_i is denoted as $σ_{{\tilde{p}}_{i}}$ ; for any set $S \subset J$ , $σ_{\tilde{p}} (S) ≜ \sum_{J_{i} \in S} σ_{{\tilde{p}}_{i}}, σ_{\tilde{p}}^{2} (S) ≜ \sum_{J_{i} \in S} σ_{{\tilde{p}}_{i}}^{2}, σ_{\tilde{p}} (S)^{2} ≜ [\sum_{J_{i} \in S} σ_{{\tilde{p}}_{i}}]^{2} .$

By Definition 1, it is easy to get $σ_{{\tilde{p}}_{i} + {\tilde{p}}_{j}} = σ_{{\tilde{p}}_{i}} + σ_{{\tilde{p}}_{j}}$ ; furthermore, for the completion time ${\tilde{C}}_{i}$ and ${\tilde{C}}_{j}$ , $σ_{{\tilde{C}}_{i} + {\tilde{C}}_{j}} = σ_{{\tilde{C}}_{i}} + σ_{{\tilde{C}}_{j}}$ . It follows that $σ_{{\tilde{C}}_{i}} \leq σ_{{\tilde{C}}_{j}}$ if J_i is processed before J_j in a feasible schedule π, which means that the schedule π is in accordance with the sequence of $σ_{{\tilde{C}}_{1}}, \dots, σ_{{\tilde{C}}_{n}}$ which is sorted from small to large. Also, the precedence constraints G can also be presented as ones of $σ_{{\tilde{C}}_{1}}, \dots, σ_{{\tilde{C}}_{n}}$ as follows: $σ_{{\tilde{C}}_{i}} \geq σ_{{\tilde{p}}_{i}}, i = 1, \dots, n; σ_{{\tilde{C}}_{k}} \geq σ_{{\tilde{C}}_{i}} + σ_{{\tilde{p}}_{k}}$ for each arc J_iJ_k in G, and $σ_{{\tilde{C}}_{k}} \geq σ_{{\tilde{C}}_{i}} + σ_{{\tilde{p}}_{k}}$ or $σ_{{\tilde{C}}_{i}} \geq σ_{{\tilde{C}}_{k}} + σ_{{\tilde{p}}_{i}}$ for any two jobs J_k, J_i.

According to Equation (13), for a schedule π with the customer service levels $\vec{k}$ , the objective function is $g (π, \vec{k}) = \sum_{i = 1}^{n} \sqrt{6} h (e_{i}, t_{i}, λ_{i}, k_{i}) σ_{C_{i}} .$ Hence, the problem $1 | prec, \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ can be formulated in the following way, where $σ_{{\tilde{C}}_{1}}, \dots, σ_{{\tilde{C}}_{n}}$ are used as the variables and the constraints ensure that the variables $σ_{{\tilde{C}}_{1}}, \dots, σ_{{\tilde{C}}_{n}}$ specify a feasible set of the standard deviations of the completion times: $minimize \sum_{i = 1}^{n} \sqrt{6} h (e_{i}, t_{i}, λ_{i}, k_{i}^{*}) σ_{C_{i}}$ (15) $\begin{matrix} subject to \\ σ_{{\tilde{C}}_{i}} \geq σ_{{\tilde{p}}_{i}}, i = 1 \dots n, \end{matrix}$ (16) $σ_{{\tilde{C}}_{k}} \geq σ_{{\tilde{C}}_{i}} + σ_{{\tilde{p}}_{k}} for each arc J_{i} J_{k} in G,$ (17) $σ_{{\tilde{C}}_{k}} \geq σ_{{\tilde{C}}_{i}} + σ_{{\tilde{p}}_{k}} or σ_{{\tilde{C}}_{i}} \geq σ_{{\tilde{C}}_{k}} + σ_{{\tilde{p}}_{i}} for J_{k}, J_{i},$ (18) where $σ_{{\tilde{C}}_{1}}, \dots, σ_{{\tilde{C}}_{n}}$ are the variables and h (e, t, λ, k) is given in Equation (12), J_k and J_i are any two jobs in Equation (18).

Note that Equation (18) is not linear inequalities. However, for a feasible scheduling π = {J_π(1), J_π(2),⋯, J_π(n)} of jobs set $J$ , let $S \subset J$ , then schedule the jobs of S according to the order of the jobs in π, which is denoted as J_π(s₁) − J_π(s₂) − ⋯ − J_{π(s_l)}. It follows that $σ_{{\tilde{C}}_{π (k)}} = \sum_{j = 1}^{k} σ_{{\tilde{p}}_{π (j)}}$ and $σ_{{\tilde{C}}_{π (s_{j})}} = \sum_{i = 1}^{s_{j}} σ_{{\tilde{p}}_{π (i)}}$ . Then, $\begin{matrix} \sum_{J_{i} \in S} σ_{{\tilde{p}}_{i}} σ_{{\tilde{C}}_{i}} \\ = \sum_{j = 1}^{l} σ_{{\tilde{p}}_{π (s_{j})}} σ_{{\tilde{C}}_{π (s_{j})}} = \sum_{j = 1}^{l} σ_{{\tilde{p}}_{π (s_{j})}} (\sum_{i = 1}^{s_{j}} σ_{{\tilde{p}}_{π (i)}}) \\ = σ_{{\tilde{p}}_{π (s_{1})}} [σ_{{\tilde{p}}_{π (1)}} + \dots + σ_{{\tilde{p}}_{π (s_{1})}}] \\ + σ_{{\tilde{p}}_{π (s_{2})}} [σ_{{\tilde{p}}_{π (1)}} + \dots σ_{{\tilde{p}}_{π (s_{1})}} + \dots + σ_{{\tilde{p}}_{π (s_{2})}}] + \dots \\ + σ_{{\tilde{p}}_{π (s_{l})}} [σ_{{\tilde{p}}_{π (1)}} + \dots + σ_{{\tilde{p}}_{π (s_{l - 1})}} + \dots + σ_{{\tilde{p}}_{π (s_{l})}}] \\ \geq σ_{{\tilde{p}}_{π (s_{1})}} [σ_{{\tilde{p}}_{π (s_{1})}}] + σ_{{\tilde{p}}_{π (s_{2})}} [σ_{{\tilde{p}}_{π (s_{1})}} + σ_{{\tilde{p}}_{π (s_{2})}}] + \dots \\ + σ_{{\tilde{p}}_{π (s_{l})}} [σ_{{\tilde{p}}_{π (s_{1})}} + σ_{{\tilde{p}}_{π (s_{2})}} + \dots + σ_{{\tilde{p}}_{π (s_{l})}}] \\ = \frac{1}{2} [\sum_{j = 1}^{l} σ_{{\tilde{p}}_{π (s_{j})}}^{2} + (\sum_{j = 1}^{l} σ_{{\tilde{p}}_{π (s_{j})}})^{2}] \\ = \frac{1}{2} [σ_{\tilde{p}}^{2} (S) + σ_{\tilde{p}} (S)^{2}] . \end{matrix}$

Based on the above linear inequalities, using the standard deviations of the completion times as the variable, a linear programming relaxation of the problem 1 $| prec, \tilde{p}, < d, d + L >, \vec{λ} | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ under the optimal customer service levels can be represented as follows: $minimize \sum_{j = 1}^{n} \sqrt{6} h (e_{j}, t_{j}, λ_{j}, k_{j}^{*}) σ_{{\tilde{C}}_{j}}$ (19) $\begin{matrix} subject to \\ σ_{{\tilde{C}}_{j}} \geq σ_{{\tilde{p}}_{j}}, j = 1 \dots n, \end{matrix}$ (20) $σ_{{\tilde{C}}_{k}} \geq σ_{{\tilde{C}}_{j}} + σ_{{\tilde{p}}_{k}} for each arc J_{j} J_{k} in G,$ (21) $\begin{matrix} \sum_{J_{j} \in S} σ_{{\tilde{p}}_{j}} σ_{{\tilde{C}}_{j}} \geq \frac{1}{2} (σ_{\tilde{p}}^{2} (S) + σ_{\tilde{p}} (S)^{2}) for each S \subset J . \end{matrix}$ (22)

Lemma 4. Let the variables $σ_{{\tilde{C}}_{1}}, σ_{{\tilde{C}}_{2}}, \dots, σ_{{\tilde{C}}_{n}}$ satisfy $\sum_{J_{j} \in S} σ_{{\tilde{p}}_{j}} σ_{{\tilde{C}}_{j}} \geq \frac{1}{2} (σ_{\tilde{p}}^{2} (S) + σ_{\tilde{p}} (S)^{2})$ for each $S \subset J$ and assume without loss of generality that $σ_{{\tilde{C}}_{1}} \leq σ_{{\tilde{C}}_{2}} \leq \dots \leq σ_{{\tilde{C}}_{n}}$ . Then, for each j = 1, ⋯, n,

$\sum_{k = 1}^{j} σ_{{\tilde{p}}_{k}} \leq 2 σ_{{\tilde{C}}_{j}} .$ (23)

Proof. It is similar to one of Lemma 2.1 in [15].

Based on the linear programming above, an algorithm is designed for the problem 1 $| prec, \tilde{p}, < d, d + L >, λ | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ as follows:

Algorithm 3.

Step 1. Input fuzzy processing time (a_i, α_i), unit earliness penalties e_i, unit tardiness penalties t_i, due window size ratio λ_i for job J_i (i = 1, ⋯, n). Input precedence constraints G among jobs.

Step 2. Compute the optimal customer service level k_i by Algorithm 1 and the unitary comprehensive penalty w_i under k_i and λ_i by w_i = h (e_i, t_i, λ_i, k_i) (i = 1, ⋯, n).

Step 3. Construct the linear programming induced by 1 $| prec, \tilde{p}, < d, d + L >, λ | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ according to Eqs.(19), (20), (21) and (22).

Step 4. Solve the linear programming problem of step 3 and obtain the solution ${\bar{σ}}_{{\tilde{C}}_{1}}, {\bar{σ}}_{{\tilde{C}}_{2}}, \dots, {\bar{σ}}_{{\tilde{C}}_{n}}$ .

Step 5. Schedule the jobs according to the nondecreasing order of ${\bar{σ}}_{{\tilde{C}}_{j}}$ , where ties are broken by choosing an order that is consistent with the precedence constraints G. This schedule is denoted as π.

Step 6. Compute the completion time ${\tilde{C}}_{j}$ of job J_j in the schedule π obtained in step 5. Then assign the due window <d_i, d_i+ L_i > to job J_i where $< d_{i}, d_{i} + L_{i} > = < \bar{M} ({\tilde{C}}_{i}) + k_{i} \sqrt{6} σ_{{\tilde{C}}_{i}}, \bar{M} ({\tilde{C}}_{i}) + (k_{i} + λ_{i}) \sqrt{6} σ_{{\tilde{C}}_{i}} > (i = 1, 2, \dots, n) .$

Step 7. Return π, $\vec{d} = (< d_{1}, d_{1} + L_{1} >, < d_{2}, d_{2} + L_{2} >, \dots, < d_{n}, d_{n} + L_{n} >)$ and $\vec{k} = (k_{1}, k_{2}, \dots, k_{n})$ .

Theorem 2. The worst case ratio of Algorithm 3 for 1 $| prec, \tilde{p}, < d, d + L >, λ | \bar{M} (\sum_{i = 1}^{n} e_{i} \tilde{E_{i}} + t_{i} \tilde{T_{i}})$ is 2.

Proof. Let a schedule π = {J_π(1), J_π(2), ⋯, J_π(n)} with the due window vector $\vec{d}$ be obtained by Algorithm 3, and ${\bar{σ}}_{{\tilde{C}}_{1}}, {\bar{σ}}_{{\tilde{C}}_{2}}, \dots, {\bar{σ}}_{{\tilde{C}}_{n}}$ be the solution of the linear programming in step 4 of Algorithm 3. Known from Step 5, it follows that ${\bar{σ}}_{{\tilde{C}}_{π (1)}} \leq {\bar{σ}}_{{\tilde{C}}_{π (2)}} \leq \dots \leq {\bar{σ}}_{{\tilde{C}}_{π (n)}} .$ Also, for π, the value of objective function is $f (π, \vec{d}) = \sum_{j = 1}^{n} \sqrt{6} h (e_{π (j)}, t_{π (j)}, λ_{π (j)}, k_{π (j)}^{*}) σ_{{\tilde{C}}_{π (j)}} = \sum_{j = 1}^{n} \sqrt{6} h (e_{π (j)}, t_{π (j)}, λ_{π (j)}, k_{π (j)}^{*}) \sum_{k = 1}^{j} σ_{{\tilde{p}}_{π (k)}} .$ Further, $f (π, \vec{d}) \leq \sum_{j = 1}^{n} \sqrt{6} h (e_{π (j)}, t_{π (j)}, λ_{π (j)}, k_{π (j)}^{*}) 2 {\bar{σ}}_{{\tilde{C}}_{π (j)}}$ according to $\sum_{k = 1}^{j} σ_{{\tilde{p}}_{π (k)}} \leq 2 {\bar{σ}}_{{\tilde{C}}_{π} (j)}$ for j = 1, ⋯, n in Lemma 4.

On the other hand, for an optimal schedule π^* = {J_π^*(1), J_π^*(2), ⋯, J_π^*(n)} with ${\vec{d}}^{*}$ , we have $f (π^{*}, {\vec{d}}^{*}) = \sum_{j = 1}^{n} \sqrt{6} h (e_{π^{*} (j)}, t_{π^{*} (j)}, λ_{π^{*} (j)}, k_{π^{*} (j)}^{*}) \sum_{k = 1}^{j} σ_{{\tilde{p}}_{π^{*} (k)}} = \sum_{j = 1}^{n} \sqrt{6} h (e_{π^{*} (j)}, t_{π^{*} (j)}, λ_{π^{*} (j)}, k_{π^{*} (j)}^{*}) σ_{{\tilde{C}}_{π^{*} (j)}} = \sum_{j = 1}^{n} \sqrt{6} h (e_{j}, t_{j}, λ_{j}, k_{j}^{*}) σ_{{\tilde{C}}_{j}^{*}} .$ It is easy to verify that $σ_{{\tilde{C}}_{1}^{*}}, \dots, σ_{{\tilde{C}}_{n}^{*}}$ satisfy $\sum_{J_{j} \in S} σ_{{\tilde{p}}_{j}} σ_{{\tilde{C}}_{j}^{*}} \geq \frac{1}{2} (σ_{\tilde{p}}^{2} (S) + σ_{\tilde{p}} (S)^{2})$ for each $S \subset J .$ Hence $(σ_{{\tilde{C}}_{1}^{*}}, \dots, σ_{{\tilde{C}}_{n}^{*}})$ is in the feasible domain of the linear programming of step 3. It follows that

$\begin{matrix} f (π, \vec{d}) = \sum_{j = 1}^{n} \sqrt{6} h (e_{π (j)}, t_{π (j)}, λ_{π (j)}, k_{π (j)}^{*}) \sum_{k = 1}^{j} σ_{{\tilde{p}}_{π (k)}} \\ \leq \sum_{j = 1}^{n} \sqrt{6} h (e_{π (j)}, t_{π (j)}, λ_{π (j)}, k_{π (j)}^{*}) 2 {\bar{σ}}_{{\tilde{C}}_{π (j)}} \\ = 2 \sum_{j = 1}^{n} \sqrt{6} h (e_{j}, t_{j}, λ_{j}, k_{j}^{*}) {\bar{σ}}_{{\tilde{C}}_{j}} \\ \leq 2 \sum_{j = 1}^{n} \sqrt{6} h (e_{j}, t_{j}, λ_{j}, k_{j}^{*}) σ_{{\tilde{C}}_{j}^{*}} = 2 f (π^{*}, {\vec{d}}^{*}) . □ \end{matrix}$

Example 1. Let $J = {J_{1}, \dots, J_{13}}$ with ${\tilde{p}}_{1} = (2, 1), {\tilde{p}}_{2} = (5, 4), {\tilde{p}}_{3} = (4, 3), {\tilde{p}}_{4} = (5, 4), {\tilde{p}}_{5} = (3, 2), {\tilde{p}}_{6} = (4, 3), {\tilde{p}}_{7} = (6, 5), {\tilde{p}}_{8} = (5, 4), {\tilde{p}}_{9} = (3, 2), {\tilde{p}}_{10} = (4, 3), {\tilde{p}}_{11} = (5, 4), {\tilde{p}}_{12} = (6, 5)$ and ${\tilde{p}}_{13} = (7, 6)$ ; (e₁, ⋯, e₁₃) = (6, 7, 3, 8, 4, 11, 9, 6, 3, 5, 3, 8, 7), (t₁, ⋯, t₁₃) = (11, 9, 5, 7, 8, 14, 4, 5, 8, 6, 9, 3, 10) and (λ₁, ⋯, λ₁₃) = (0.2, 0.3, 0.2, 0.1, 0.1, 0.4, 0.2, 0.1, 0.4, 0.3, 0.2, 0.2, 0.3). The precedence constraints are described as Fig. 3.

Fig.3

The precedence constraint for Example 1.

First, compute the unitary comprehensive penalty under optimal customer service level for each job, that is $\vec{w} = (1.9294, 1.6184, 0.9259, 2.1363, 1.5670, 2.1102, 1.3990, 1.5621, 0.7878, 1.1189, 1.1690, 1.1200, 1.6992) .$ Then, construct the linear programming according to step 3 of Algorithm 3 and solve the linear programming; the solution is $({\bar{σ}}_{{\tilde{C}}_{1}}, \dots, {\bar{σ}}_{{\tilde{C}}_{13}}) = (1.225, 4.899, 15.408, 17.041, 0.817, 2.450, 13.775, 7.757, 3.266, 6.124, 15.408, 11.325, 13.775) .$

Next, schedule the jobs according to the nondecreasing order of ${\bar{σ}}_{{\tilde{C}}_{j}},$ and get the schedule π = (J₅, J₁, J₆, J₉, J₂, J₁₀, J₈, J₁₂, J₇, J₁₃, J₃, J₁₁, J₄). The Gantt chart of the schedule for the fuzzy completion times is given in Fig. 4.

Fig.4

The Gantt chart of the schedule obtained by Algorithm 3 for the fuzzy completion times in Example 1.

The due windows of all jobs are <5.1076, 5.7076>, <15.8400, 19.4400 >, <49.5474, 57.1474 >, <55.2417, 59.8417 >, <3.2364, 3.4364 >, <8.0890, 10.4890 >, <29.8068, 35.6068 >, <24.2278, 26.1278 >, #x003C;11.9386, 15.1386 >, <19.3307, 23.8307 >, <60.2251, 68.6251 >, <24.2867, 29.0867 > and <42.3958, 52.8958>, respectively.

Remark. Note that the constraints of the linear programming of step 3 in Algorithm 3 is the exponentially large class of constraints. However, as it is pointed in [19], an effective ellipsoid algorithm is given based on a polynomial time separation algorithm for the exponentially large class of constraints. Hence, the solution for the example above can be quickly obtained even the size of the constraints matrix is 8225 × 13.

3 Experiment

For the scheduling problems with uncertain processing times, stochastic methods are use to model the problems, where the processing times are usually assumed as random variables with normal distributions [25]. According to the results of [25], a due date d can be assigned to a job such that the expected value of the earliness-tardiness penalties E (e max {d − C, 0} + t max {C − d, 0}) is minimized, whose completion time is a random variable C with a normal distribution N (μ, σ²). Similarly, a due window <d, d+ L > can be obtained such that the expected value of the earliness-tardiness penalties E (e max {d − C, 0} + t max {C − d − L, 0}) is minimized, and it is detailedly given out how to determine the due window <d, d+ L > in Appendix, which is an extension of the results in [25]. Without special statement, the above method extending from [25] and the method of our paper are briefly written as the stochastic method and the fuzzy method in the following.

Next, the stochastic method and the fuzzy method will be tested on the same data come from Example 1 [25] to examine their effectivity by comparing the total penalties, which can be denoted by the flow diagram in Fig. 5.

Fig.5

The flow diagram for examining the effectivity of the due window assignment method.

Fig.6

The earliness-tardiness penalty of each job in samples 1–6.

In Example 1 [25], the processing time of the job is a random variable with the normal distribution N (10, 3²); the per unit earliness penalties and tardiness penalties are $e = 3 \sqrt{2 π}$ and $t = 27 \sqrt{2 π}$ . Next, 6 samples are produced from the normal distribution N (10, 3²) which are the same as ones in [10], and their sample sizes are 46, 81, 180, 344, 666 and 1332, respectively. The sampling method for each sample is as follows. First, according to the 3σ principe, determine the interval which the processing time of the job is almost in. It is easy to get that the interval is [1,19, 1,19]. Second, divide the interval [1,19, 1,19] into 6 subintervals as [1, 4], [4, 7], [7, 10], [10, 13], [13, 16] and [16, 19]. At last, choose the processing times from 6 subintervals in accordance with the probability of the random variable N (10, 3²) lying in each interval.

Then, model the uncertain processing time of the job by the uncertain variables based on the sampled data and determine the job’s due windows with the size L = 3 by the use of two methods. For the stochastic method, the uncertain processing time of the job is modeled by a random variable with the normal distribution N (10, 3²) for each sample, and the optimal due window is <11.3280, 14.3280>, where the solving process is given in Appendix; for the fuzzy method of our paper, the uncertain processing time of this job for each sample is modeled by a symmetrical triangle number (10, 8.5), since the processing time of the job is almost in the interval [1, 19] according to the 3σ principe; and the optimal due window is <12.1068, 15.1068> according to the fuzzy method of this paper.

Table 1

The total penalties of sample 1–sample 6

Samples	Stochastic Method	Fuzzy Method	Decreasing Rate(%)
Sample 1 (46jobs)	1141.7	1112.0	2.6
Sample 2 (81 jobs)	2215.0	2214.2	0.04
Sample 3 (180 jobs)	4475.4	4349.8	2.8
Sample 4 (344 jobs)	8872.1	8590.4	3.18
Sample 5 (666 jobs)	16747.4	16555.4	1.15
Sample 6 (1332 jobs)	33208.1	32853.4	1.07

Then, compute the earliness-tardiness penalties of all jobs in each sample based on the collected data, which are are shown in Fig. 6. Also, compute the total penalties of all jobs in each sample for these two methods, and compute the decreasing rates of the total penalties for the fuzzy method compared to the ones for the stochastic method, which are given in Table 1 for 6 samples; Known from the decreasing rates of all samples in Table 1, for the same data above, the total penalties induced by the due window obtained by our method are less than the ones induced by the due window obtained by stochastic method.

Further, our model can deal with the due window assignment scheduling problems with general precedence constraints among jobs under uncertain environment, whereas there are no results for this case by stochastic method as far as we know. Moreover, we use Example 1 in section 2 to test Algorithm 3. All algorithms are implemented using MATLAB language (no explicit use of parallel toolbox), tested in MATLAB 2017b, 16 GB memory and Intel core i7-7700 CPU. Then, the schedule with the objective function value 403.2450 is obtained by Algorithm 3 in 3 seconds. On the other side, the optimal schedule π^* is (J₅, J₁, J₆, J₉, J₂, J₁₀, J₈, J₁₂, J₇, J₃, J₁₃, J₁₁, J₄) with the objective function value 402.7872 can be obtained by the enumeration, but the time is about 1890 seconds due to examining 39916800 permutations. Moreover, the ratio of two objective function values is $\frac{403.2450}{402.7872} = 1.0011$ , which shows that Algorithm 3 is effective.

4 Conclusions

In this paper, a single machine due window assignment scheduling problem with precedence constraints in fuzzy environment was studied. The optimal polynomial time algorithm for $1 | \tilde{p}, < d, d + L >, λ | \bar{M} (e_{i} {\tilde{E}}_{i} + t_{i} {\tilde{T}}_{i})$ was proposed. Moreover, for general precedence constraints, a 2-approximation algorithm was designed based on solving a particular relaxation of this kind of due window assignment scheduling problems.

However, Algorithm 3 is required to solve a kind of linear programming with exponentially large class of constraints. Our work may accordingly focus on designing more effective algorithm for the due window assignment scheduling with general precedence constraints and fuzzy processing times.

Appendix

In the following, it is illustrated how to obtain <d, d + L > 0 such that the expected value of the earliness-tardiness penalties E (t max {ξ − d − L, 0} + e max {d − ξ, 0}) reaches the minimal value, where e, t, L > 0 and ξ ∼ N (μ, σ²) with the probability density function $f (x) = \frac{1}{\sqrt{2 π} σ} exp {- \frac{(x - μ)^{2}}{2 σ^{2}}}$ .

Let Y = max {ξ − d − L, 0} and Z = max {d − ξ, 0}. Then, it follows that $\begin{matrix} F_{Y} (y) & = & P (\max {ξ - d - L, 0} \leq y) \\ = & {\begin{matrix} 0, & y < 0; \\ \int_{- \infty}^{y + d + L} f (x) dx, & y \geq 0, \end{matrix} \end{matrix}$ (24) $F_{Z} (z) = {\begin{matrix} 0, & z < 0; \\ 1 - \int_{- \infty}^{d - z} f (x) dx, & z \geq 0 . \end{matrix}$ (25)

Hence, the probability density functions of Y and Z are

$f_{Y} (y) = {\begin{matrix} 0, & y < 0; \\ f (y + d + L), & y \geq 0 . \end{matrix}$ (26) and

$f_{Z} (z) = {\begin{matrix} 0, & z < 0; \\ f (d - z), & z \geq 0 . \end{matrix}$ (27)

Then, it is not difficult to get

$\begin{matrix} G (d) & = & E (t max {ξ - d - L, 0} + e max {d - ξ, 0}) \\ = & t \int_{d + L}^{+ \infty} xf (x) dx - t (d + L) \int_{d + L}^{+ \infty} f (x) dx \\ - e \int_{- \infty}^{d} xf (x) dx + ed \int_{- \infty}^{d} f (x) dx . \end{matrix}$ (28)

It follows that

$\begin{array}{l} G' (d) = t \int_{+ \infty}^{d + L} f (x) d x + e \int_{- \infty}^{d} f (x) d x; \\ G ″ (d) = t f (d + L) + e f (d) . \end{array}$ (29)

It is easy to verify that and G (d) is a convex function on (− ∞, + ∞) with $lim_{d \to + \infty} G (d) = lim_{d \to - \infty} G (d) = + \infty$ . Also, G^′ (d) is a increasing function with $\lim_{d \to + \infty} G' (d) = e > 0$ and $\lim_{d \to - \infty} G' (d) = - t < 0$ . Therefore, has and only has one root d^* such that G (d^*) is the minimal value of G (d) on (− ∞, + ∞).

In fact, for t ≠ e, it is not easy to get the analytical solution of the equation:

$G^{'} (d) = e \int_{- \infty}^{d} f (x) dx - t \int_{d + L}^{+ \infty} f (x) dx = 0 .$ (30)

The numerical solution of can be obtained by numerical method. In this paper, Newton iteration method is used to solve the with the iteration equation for Example 1.

Footnotes

Acknowledgments

This paper was supported by National Natural Science Foundation of China (11401030), the Training Program of Outstanding Young Teacher for Guangdong’s Colleges and Universities (2014) and Teacher Research Capacity Promotion Programm of Beijing Normal University Zhuhai.

References

Baykasǒsglu

Gkǒen and

Z.D.

Unutmaz , New approaches todue date assignment in job shops, European Journal of Operational Research 187(1) (2008), 31–45.

Janiak

, Kwiatkowski

and Lichtenstein

, Scheduling problemswith a common due window assignment: A survey, International Journal of Applied Mathematics and Computer Science 23(1) (2013), 231–241.

Janiak

, Kovalyov

and Marek

, Soft due window assignment andscheduling on parallel machines, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans 37(5) (2007), 614–620.

Wong

and Lai

, A survey of the application of fuzzy set theoryin production and operations management: 1998-2009, International Journal of Production Economics 129(1) (2011), 157–168.

Carlsson

and Fullér

, On possibilistic mean value and variance of fuzzy numbers, Fuzzy Sets and Systems 122(2) (2001), 315–326.

Yang

, Lai

and Yang

, Scheduling problems with multiple duewindows assignment and controllable processing times on a single machine,, International Journal of Production Economics 150 (2014), 96–103.

Gerstl

and Mosheiov

, An improved algorithm algorithm fordue-window assignment on parallel identical machines with unit-timejobs, Information Processing Letters 113(19-21) (2013), 754–759.

Gerstl

and Mosheiov

, Due-window assignment with identical jobs on parallel uniform machines, European Journal of Operational Research 229(1) (2013), 41–47.

Lushchakova

I.N.

, Two machine preemptive scheduling problem with release dates, equal processing times and precce constraints, European Journal of Operational Research 171(1) (2006), 107–122 eden.

10.

, Sun

and Li

D.H.

, Single machine due date assignment scheduling problem with customer service level in fuzzy environment, Applied Soft Computing 10(3) (2010), 849–858.

11.

, Yuan

, Lee

E.S.

and Xu

, Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness? tardiness costs on a single machine, Computers and Mathematics with Applications 62(11) (2011), 4126–4139.

12.

Leung

J.Y.-T.

, Introduction and notation in:

J.Y.-T.

Leung (Ed.), Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman & Hall, CRC, Boca Raton, 2004 (Chapter 1).

13.

Baker

K.R.

, Minimizing earliness and tardiness costs in stochasticscheduling, European Journal of Operational Research 236(2) (2014), 445–452.

14.

Adolphson

, Sinle machine job sequencing with precceconstraints, SIAM Journal on Computing 6(1) (1977), 40–54.

15.

Hall

, Schulz

, Shmoys

and Wein

, Scheduling to minimize average completion time: Off-line and On-line approximation algorithms, Mathematics of Operations Research 22(3) (1997), 513–544.

16.

Liu

, Wang

, Liu

and Liu

, Single machine due window assignment and resource allocation scheduling problems with learning and general positional effects, Journal of Manufacturing Systems 43(1) (2017), 1–14.

17.

Hanss

, Applied Fuzzy Arithmetic: An Introduction with Engineering Applications, Springer, Berlin, 2005.

18.

Iranpoor

, FatemiGhomi

S.M.T.

and Zandieh

, Due-date assignment and machine scheduling in a low machine-rate situation with stochastic processing times, Computers & Operations Research 40(4) (2013), 1100–1108.

19.

Queyranne

, Structure of a simple scheduling polyhedron, Mathematical Programming 58(1-3) (1993), 263–285.

20.

Graham

R.L.

, Lawler

E.L.

, Lenstra

J.K.

and Rinnooy

A.H.G.

, Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5 (1979), 287–326.

21.

Slowiński

, Hapke

, Scheduling Under Fuzziness, Physica-Verlag, Heidelberg, 2000.

22.

Cheng

T.C.E.

, Yuan

J.J.

and Yang

A.F.

, Scheduling a batch processing machine subject to precce constraints, release dates and identical processing times, Operations & Research 32(4) (2005), 849–859.

23.

Cheng

T.C.E.

, Yang

and Yang

, Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and adeteriorating maintenance activity, International Journal of Production Economics 135(1) (2012), 154–161.

24.

Gordon

, Proth

and Chu

, A survey of the state-of-the-art ofcommon due date assignment and scheduling research, European Journal of Operational Research 139(1) (2002), 1–25.

25.

Portougal

and Trietsch

, Setting due dates in a stochastic single machine environment, Computers & Operations Research 33(6) (2006), 1681–1694.

26.

Yeung

, Choi

and Cheng

T.C.E.

, Optimal scheduling of asingle-supplier single-manufacturer supply chain with common duewindows, IEEE Transactions on Automatic Control 55(12) (2010), 2767–2777.

27.

Yin

, Cheng

T.C.E.

, Hsu

and Wu

, Single-machine batch delivery scheduling with an assignable common due window, Omega 41(2) (2013), 216–225.