Order Acceptance and Scheduling Problem: A Proposed Formulation and the Comparison with the Literature

Abstract

In classical scheduling problem, it is assumed that all orders must be processed. In the order acceptance and scheduling (OAS) problem, some orders are rejected due to limited capacity. In make-to-order production environment, in which the OAS problem occurs, accepting all orders may cause overloads, delay in deliveries and unsatisfied customers. Oğuz et al. (2010) introduced the OAS problem with sequence-dependent setup times and release dates. In this paper, we propose a new mixed integer programming formulation with O(n²) decision variables and O(n²) constraints for the same problem. We conduct a computational analysis comparing the performance of our formulation with Oğuz et al. (2010) formulation. We use the benchmark instances, which are available in the literature. We observe that our formulation can solve all the instances up to 50 orders in a reasonable time, while Oğuz et al. (2010) formulation can solve only the instances with 10 orders in the same time limit.

1 Introduction

In scheduling problem, it is mostly assumed that all orders must be processed. However, in real-life applications this may not be the case. In make-to-order production environment, accepting all orders may cause overloads, delay in deliveries and unsatisfied customers. Therefore, firms tend to reject some orders. Order acceptance and scheduling (OAS) problem consists of deciding which orders to be accepted and determining the schedule of the accepted orders [1].

The OAS problem considered in this study was introduced by Oğuz et al. [2] in 2010 and a mathematical formulation was proposed. The problem is defined as follows. In a single machine environment, there is a set of orders shown as N = {1, 2, …, n}. For each order iϵN, let r_i be the release date, p_i be the processing time, d_i be the due date, $\overline{{d_{i} }}$ be the deadline, e_i be the revenue, w_i be the unit penalty weight for the tardiness of the orders and s_ji be the sequence-dependent setup time occurring if the order i is processed immediately after order j. The setup operation of order iϵN can only be performed after its release date. The objective is to select and schedule a subset of orders that maximizes the total profit.

To the best of our knowledge, there are 27 studies related to single machine OAS problem in the literature. Only 9 of them include a mathematical formulation. These studies are summarized in Table 1. In [4]’s study, a job is rejected if it is not finished before its due date. This study is considered as the first example of OAS problem in the literature [1]. [5] considered varying prices and customer chosen due dates, while [6] considered inventory costs. They proposed two different formulations. [2] introduced the OAS problem with sequence-dependent setup times and release dates. They proposed a formulation and their study has taken remarkable attention by researches. In [7]’s study, there are obligatory jobs and they proposed two mathematical formulations. [8] addressed the OAS problem considering resource limits and due windows and proposed a formulation. In his study, a job is rejected if it cannot be finished within its due window. [9] studied the OAS problem with sequence-dependent setup times depending on lot sizes. They considered total available time constraint and proposed a formulation. [10] defined an upper limit for the number of accepted jobs and considered sequence-dependent setup times. They proposed a nonlinear formulation. [3] dealt with the problem as in [2]. They proposed a time-indexed formulation with different revenue calculation method. [3]’s time indexed formulation has some structural difficulties, so we did not consider this formulation in detail.

Table 1. Single machine OAS studies with mathematical formulation

In recent years, the developments on computer technology and softwares enable us to solve the combinatorial problems to optimality by well-designed mathematical formulations. Mathematical formulations can be useful in real-life applications and allow post-optimality analysis. In most of the studies on OAS problem, solving methods generally focus on heuristic algorithms. However, as [12] express that mathematical formulations are still useful for the scheduling problems.

In this study, we propose a new formulation for single machine OAS problem with sequence-dependent setup times and release dates. We conduct a detailed computational analysis to compare Oğuz et al. [2] formulation and our proposed formulation.

The remainder of this paper is organized as follows. Section 2 introduces the new integer linear programming formulation for single machine OAS problem with sequence-dependent setup times and release dates. Section 3 presents the results of the computational experiments comparing the performance of our proposed and Oğuz et al. [2] formulation. Finally, Sect. 4 provides the concluding remarks of this work.

2 A New Formulation

In this section we introduce a new mixed integer linear programming formulation for OAS problem with sequence-dependent setup times and release dates. Let “0” and “n+1” be the dummy orders, which indicate the first order of the schedule and the last order of the schedule respectively. Decision variables are given as follows. Let T_i be the tardiness of order i, for iϵN. Let Z_ij be the completion time of order j, if order j is processed immediately after order i. Let Y_i be 1, if order i is accepted, 0 otherwise. Let X_ij be 1, if order j is processed immediately after order i, 0 otherwise. Our proposed formulation is given below:

$$ { \hbox{max} }\sum\nolimits_{i = 1}^{n} {R_{i} } $$

(1)

s.t.

$$ \sum\nolimits_{i = 1}^{n} {X_{0i} } = 1 $$

(2)

$$ \sum\nolimits_{i = 1}^{n} {X_{i,n + 1} } = 1 $$

(3)

$$ \sum\nolimits_{j = 1,i \ne j}^{n + 1} {X_{ij} = Y_{i} } \quad \forall_{i} = 1,\, \ldots \,,n $$

(4)

$$ \sum\nolimits_{j = 0,i \ne j}^{n} {X_{ji} } = Y_{i} \quad \forall_{i} = 1,\, \ldots ,\,n $$

(5)

$$ \begin{aligned} \sum\nolimits_{j = 1}^{n + 1} {Z_{ij} } - \sum\nolimits_{k = 0}^{n} {Z_{ki} } = \sum\nolimits_{j = 1}^{n + 1} {(r_{j} + s_{ij} + p_{j} )X_{ij} } \quad i \ne j,\quad & \forall_{i} = 1,\, \ldots ,\,n,\quad \\ \forall_{j} = 1,\, \ldots ,\,n + 1 \\ \end{aligned} $$

(6)

$$ Z_{0i} = \left( {r_{i} + s_{0i} + p_{i} } \right)X_{0i} \quad \forall_{i} = 1,\, \ldots ,\,n $$

(7)

$$ \sum\nolimits_{k = 0}^{n} {Z_{ki} } \le \overline{{d_{i} }} Y_{i} \quad \forall_{i} = 1,\, \ldots ,\,n $$

(8)

$$ Z_{ij} \le \overline{{d_{max} }} X_{ij} \quad i \ne j,\quad \forall_{i} = 0,\, \ldots ,\,n,\quad \forall_{j} = 1,\, \ldots ,\,n + 1 $$

(9)

$$ T_{i} \ge \sum\nolimits_{k = 0}^{n} {Z_{ki} } - d_{i} Y_{i} \quad \forall_{i} = 1,\, \ldots ,\,n $$

(10)

$$ T_{i} \le (\overline{{d_{i} }} - d_{i} )Y_{i} \quad \forall_{i} = 1,\, \ldots ,\,n $$

(11)

$$ T_{i} \ge 0\quad \forall_{i} = 1,\, \ldots ,\,n $$

(12)

$$ R_{i} = e_{i} Y_{i} - T_{i} w_{i} \quad \forall_{i} = 1,\, \ldots ,\,n $$

(13)

$$ R_{i} \ge 0\quad \forall_{i} = 1,\, \ldots ,\,n $$

(14)

$$ Y_{i} \in \left\{ {0,1} \right\}\quad \forall_{i} = 1, \ldots ,n $$

(15)

$$ X_{ij} \in \left\{ {0,1} \right\}\quad i \ne j,\quad \forall_{i} = 0, \ldots ,n,\quad \forall_{j} = 1, \ldots ,n + 1 $$

(16)

$$ Z_{ij} \ge 0\quad i \ne j,\quad \forall_{i} = 0,\, \ldots ,\,n,\quad \forall_{j} = 1,\, \ldots ,\,n + 1 $$

(17)

In the objective function (1), the difference between total revenue of accepted orders and total tardiness penalty of accepted orders is maximized. With constraint (2) and (3), it is guaranteed that “0” is assigned to the first position and “n+1” is assigned to the last position of the schedule. Constraint set (4) ensures that if an order is accepted, another order is processed immediately after this order; and constraint set (5) ensures that if an order is accepted another order is processed immediately before this order. Constraint set (6) calculates the completion time of the orders. Constraint set (7) calculates the completion time of the first processed order in the sequence. Constraint set (8) guarantees that if an order is not completed before its deadline, then the order is not accepted. Constraint set (9), where $\overline{{d_{max} }} = max_{i = 1,\, \ldots ,\,n} \{ \overline{{d_{i} }} \}$, provides X_ij be zero, when Z_ij be zero, and gives an upper bound to Z_ij’s. Constraint set (10) calculates the tardiness of the orders. Constraint set (11) gives an upper bound to T_i’s, while constraint set (12) provides a lower bound to T_i’s. Constraint set (13) calculates the revenue of the orders, while constraint set (14) bounds it. Constraint sets (15) and (16) define the binary variables. Constraint set (17) gives a lower bound to Z_ij’s. Our proposed formulation has 2n²+10n+2 constraints and n²+2n binary decision variables.

Constraints (2), (3), (4) and (5) are traditional assignment constraints, therefore they are same as in Oğuz et al. [2] formulation. Constraints (11), (12), (13) are due to the relations between tardiness, targets and revenue, so they are same as in Oğuz et al. [2] formulation. Constraints (14), (15), (16) and (17) are non-negativity and binary constraints. These constraints also are not related with the structure of the formulation directly.

Main difference between our formulation and Oğuz et al. [2] formulation depends upon the decision variables corresponding to completion times of the orders. Oğuz et al. [2] defines completion times by indexing with C_i for i^th order and develops main constraints of their formulation as a function of C_i’s and other decision variables. We define completely different decision variables for completion time in relation with preceding order i and j as Z_ij, thus our main decision variables are arc-based whereas Oğuz et al. [2] formulation’s main decision variables are node-based.

In accordance with these above explanations, main body of our formulation which includes constraints (6), (7), (8), (9) and (10) is completely different from Oğuz et al. [2] formulation.

3 Computational Experiments

In this section we summarize the results of computational experiments comparing the performance of Oğuz et al. [2] formulation (OSB) and our proposed formulation (OPF). Mathematical formulations were coded in C++ and benchmark instances were solved by CPLEX 12.4 in an Intel Xeon Phi 7290 with 1.5 GHz and 384 GB of RAM.

Benchmark instances were generated by [11] and they are available on the web address http://home.ku.edu.tr/~coguz~/Research/Dataset_OAS.zip. There are six instance groups which consist of n = 10,15,20,25,50 and 100. Each instance group has 250 instances, and there are totally 1500 benchmark instances. For the instances with 10,15,20,25 and 50 orders the time limit is set 7200 seconds; for the instances with 100 orders the time limit is set 14400 seconds. Run times and LP relaxations of OPF and OSB for n = 10 are showed in Table 2.

Table 2. The results of OSB and OPF for n = 10

From Table 2, we observe that OPF is extremely faster than OSB with the average run times 0,48 and 94,67 respectively. LPR values are not different and the average percentage deviation is 0,05 which indicates the LPR values are very close to the optimal values.

We solved all the instances with n = 10 with each formulation. The average run time and the average percentage deviation are given in Table 3.

Table 3. The results of OPF for n = 10, 15, 20, 25, 50

OSB cannot solve the instances greater than 10 orders in given time limit. Therefore, we continue computational analysis with OPF. Average run times and average percentage deviations for n = 15, 20, 25 and 50 are given in Table 3. OPF can solve all the instances up to 50 orders in a reasonable time.

There are no benchmark instances between 50 and 100 orders. OPF cannot solve the instances with 100 orders in 14400 seconds time limit.

4 Concluding Remarks

In this study we proposed a new arc-based mathematical formulation for solving a variant of OAS problem that includes sequence-dependent setup times and release dates. Our proposed formulation and Oğuz et al. [2] formulation were tested on instances ranging from 10 to 50 orders. Oğuz et al. [2] formulation can solve only the instances with 10 orders in given time limit. Our proposed formulation can solve the instances up to 50 orders to optimality in the same time limit. Future studies may consider proposing new mathematical formulations capable of solving larger instances in a reasonable time.