Solving parallel machine problems with delivery times and tardiness objectives

Abstract

This paper studies the NP-hard problem of scheduling jobs on identical parallel machines with machine-dependent delivery times to minimize the total weighted tardiness. A mixed integer linear programming formulation is presented that does not require machine-indexed variables due to a transformation of the problem. A variable neighborhood search (VNS) algorithm is proposed incorporating a local search that utilizes fast evaluation techniques (FET) to significantly improve computational efficiency of the search in four different neighborhoods. In experiments, the VNS is compared with other solution approaches on a large set of randomly generated test instances. Additionally, results for the computational benefits of our FETs are reported.

Appendix

1.1 Alternative MILP formulation for $Pm|q_h|\sum w_jT_j$

The following MILP is an alternative to the formulation presented in Sect. 3 and explicitly incorporates machine-dependent delivery times. It uses two binary decision variables $x_{ij}$ with

$$\begin{aligned} x_{ij} = \left\{ \begin{array}{ll} 1, &{} \text{ if } \text{ job }~j~\text{ is } \text{ sequenced } \text{ immediately } \text{ after } \text{ job }~i, \\ 0, &{} \text{ otherwise, } \end{array} \right. \end{aligned}$$

(31)

and $y_{jh}$ with

$$\begin{aligned} y_{jh} = \left\{ \begin{array}{ll} 1, &{} \text{ if } \text{ job }~j~\text{ is } \text{ the } \text{ first } \text{ sequenced } \text{ job } \text{ on } \text{ machine }~h, \\ 0, &{} \text{ otherwise. } \end{array} \right. \end{aligned}$$

(32)

Furthermore, a dummy job $j=n+1$ is introduced with $p_{n+1}=0$ that marks the end of the schedule on each machine. The problem can now be formulated as follows:

Notation:

$p_j$:

Processing time of job j

$w_j$:

Weight of job j

$d_j$:

Due date of job j

$q_h$:

Delivery time of machine h

$C_j$:

Completion time of job j

$T_j$:

Tardiness of jobs j

H:

Sufficient large number

n:

Number of jobs

m:

Number of machines

$$\begin{aligned} \min \sum _{i=1}^{n} w_jT_j \end{aligned}$$

(33)

subject to

$$\begin{aligned} \sum _{j=1}^{n} y_{jh} \le 1&\quad h=1,\ldots ,m; \end{aligned}$$

(34)

$$\begin{aligned} \sum _{h=1}^{m} y_{jh} \le 1&\quad j=1,\ldots ,n; \end{aligned}$$

(35)

$$\begin{aligned} y_{jh} + \sum _{i=1,i\ne j}^{n} x_{ij} = 1&\quad j = 1,\ldots ,n; \quad h=1,\ldots ,m; \end{aligned}$$

(36)

$$\begin{aligned} \sum _{i=1,i\ne j}^{n+1} x_{ji} = 1&\quad j = 1,\ldots ,n; \end{aligned}$$

(37)

$$\begin{aligned} C_j \ge (p_j + q_h)y_{jh}&\quad j = 1,\ldots ,n; \quad h=1,\ldots m; \end{aligned}$$

(38)

$$\begin{aligned} C_j \ge C_i + p_j - H(1-x_{ij})&\quad i,j=1,\ldots ,n; i\ne j; \end{aligned}$$

(39)

$$\begin{aligned} T_j \ge C_j - d_j&\quad j=1,\ldots ,n; \end{aligned}$$

(40)

$$\begin{aligned} x_{ij} \in \{0,1\}&\quad i,j = 1,\ldots ,n; \end{aligned}$$

(41)

$$\begin{aligned} y_{jh} \in \{0,1\}&\quad j = 1,\ldots ,n; \quad h=1,\ldots ,m; \end{aligned}$$

(42)

$$\begin{aligned} C_j,T_j \ge 0&\quad i = 1,\ldots ,n \end{aligned}$$

(43)

The objective (33) is to minimize the TWT. Constraints (34) and (35) ensure that at most one job is assigned to the first position on each machine. Constraints (36) and (37) determine job sequences. The completion time of the first jobs on machines is calculated by inequality (38) while (39) defines the completion time for the remaining jobs, where H is a sufficient large number. The tardiness of each job is calculated by inequality (40). Constraints (41) through (43) define the variables.

The MILP was tested on the set of small instances described in Sect. 6.3 as well. In a direct comparison, a superiority of MILP performances could not be confirmed with statistical significance.

1.2 ATC heuristic for $Pm|q_h|\sum w_jT_j$

The ATC rule was originally proposed for the single machine PMTWT problem but can be applied to other tardiness-related scheduling problems as well. The general idea of ATC is to calculate a priority value $I_j$ for each job, which increases as its slack, i.e., the remaining time until its due date, reduces:

$$\begin{aligned} I_j = \frac{w_{j}}{p_{j}} \exp \left( -\frac{\max \{d_{j} - q_{h} - p_{j} - t_{h},0\}}{k\bar{p}} \right) , \end{aligned}$$

(44)

where k represents a look-ahead parameter, $\bar{p}$ the average processing time of jobs, and $t_h$ the current workload of machine h. If jobs have no slack left, priority values equal shortest weighted processing time. Our implementation of ATC for $Pm|q_h|\sum w_jT_j$ is given in Algorithm 3.

In the first phase, an initial schedule is constructed using ATC. In each iteration, first, the fastest machine is determined under consideration of machine delivery times. For each unscheduled job, the priority value is calculated based on the current machine workload. Among all unscheduled jobs, the one with largest priority value is scheduled to the first available position on the machine and the machine workload is incremented by its processing time. This procedure is repeated until all jobs are scheduled. In the second phase, an adjacent pairwise exchange procedure is applied to each machine to improve the given schedule.