1 Introduction

Recently, order scheduling (OS) problem has become an important issue in many service and manufacturing environments, in which a product development team develops modules independently for several products, and the product design is deemed to be completed when all the modules have been designed (seen Ahmadi et al. 2005; Wang and Cheng 2007).

For relevant OS literature studies, Wagneur and Sriskandarajah (1993) claimed that the maximum completion time minimization and the maximum tardiness minimization problems are solved in polynomial time, that the number of late jobs minimization problem is in binary NP-hard in the two-machine case, and that the total completion time minimization and the total tardiness minimization problems are unary NP-hard for \(m \geqslant 2\). Meanwhile, Leung et al. (2005a) gave a counterexample and showed that the number of late jobs minimization problem in the two-machine case is still an open issue. Leung et al. (2005b) showed that the OS model on three- or more machine settings is strongly NP-hard, and derived a heuristic based on the shortest processing time rule on the machine with the largest current load and a heuristic based on the earliest completion time for approximate solutions. For the two-machine case, Sung and Yoon (1998) provided the shortest maximum processing time (SMPT) algorithm and the shortest total processing time (STPT) algorithms to solve it. Yang (2005a, b) considered OS problems associated with the completion time of the orders and analyzed the complexity of several problems with different types of objectives, job restrictions, and machine environments. Ahmadi et al. (2005) showed that the weighted sum of customer order delivery times minimization is proved as unary NP-hard, characterized the optimal schedule, solved several special cases of the problem, derived tight lower bounds, and proposed several heuristic solutions.

Regarding the literature research for minimizing the total weighted order completion time, Wang and Cheng (2007) claimed that the problem is unary NP-hard, and proposed a heuristic and discussed its worst-case behavior. Yoon and Sung (2005) built a branch-and-bound method to solve the problem, while Leung et al. (2006a, 2007a, 2008a) derived heuristic algorithms for finding approximate solutions.

For some OS studies involving due dates, Lee (2013) considered the tardiness minimization as the objective function, derived some dominance properties and three lower bounds in a branch-and-bound algorithm for finding optimal solution, and proposed three heuristic algorithms for approximate solutions. Introducing the position-based learning idea to the Lee’s model, Xu et al. (2016a) proposed a branch-and-bound algorithm incorporating certain dominance rules and three lower bounds and simulated annealing, particle swarm optimization, and modified earliest due dates of orders to solve the problem. Lin et al. (2017) addressed a two-agent order scheduling with ready times and utilized a branch-and-bound method, a particle swarm optimization, and opposite-based particle swarm optimization for the optimal solution and approximate solution. Additional OS works in other settings, readers may refer to Blocher et al. (1998), Erel and Ghosh (2007), Framinan and Perez-Gonzalez (2017), Lin and Kononov (2007), Hsu and Liu (2009), Wu et al. (2018), Xu et al. (2016b), Yang and Posner (2005), Zhao et al. (2016), and so on.

The issue of the release dates of orders in the OS models has, however, been rarely studied. In manufacturing semi-finished lenses, the complexity of relevant customer satisfaction criteria, along with meeting customer due dates with different priorities, poses a difficult challenge. Readers may refer to Ahmadi et al. (2005) for details. In addition, the occurrence of resources in parallel is common in many real applications. Given the unequal ready times of the jobs on parallel batch machines, a good policy is to wait and combine future job arrivals to increase the completeness of a batch (Monch et al. 2005). For the importance of the due dates in real applications, readers may refer to French (1982) and Armentano and Ronconi (1999) for the scheduled landing time of an aircraft and for several production examples involving due date settings.

Motivated by these observations and the relatively limited use of metaheuristic to solve order scheduling models, in this study we consider both release dates and number of tardy jobs in the OS model. The main contributions of this study are summarized as follows: A new OS model of considering release dates for each orders and the weighted number of tardy orders criterion is addressed. A branch-and-bound algorithm along with several properties and a lower bound is developed to find the optimal solution. Eight versions of artificial bee colony (ABC) algorithm with an improvement scheme are developed for finding the high-quality near-optimal solutions. Some extensive computational experiments and statistical tools are applied to evaluate the performances for all proposed algorithms.

The remainder of this study is summarized as follows. Section 2 presents the notation and problem formulation. Section 3 introduces several properties and a lower bound, artificial bee colony algorithm, and the branch-and-bound algorithm. Section 4 reports and evaluates observations of all the proposed algorithms, and Sect. 5 provides conclusions and suggestions.

2 Notation and problem statement

The notations used in this study are given in the following:

  • n: order number,

  • m: machine number,

  • \( M_{k} \): machine code k, where k = 1, …, m,

  • \( \sigma ,\sigma^{\prime} \): schedules of n orders, where \( \sigma = (\pi ,i,j,\pi^{\prime}) \) and \( \sigma^{\prime} = (\pi ,j,i,\pi^{\prime}) \) are two full sequences, and \( \pi \) and \( \pi^{\prime} \) denote two partial sequences,

  • \( p_{vk} \): component k processing time of order v processed on machine k, for \( 1 \le k \le m \).

  • \( d_{v} \): due date for order v, for \( 1 \le v \le n \).

  • \( t_{k} \): a starting time on Mk, for \( 1 \le k \le m \).

  • \( C_{v} (\sigma ) \): finished time of order v in \( \sigma \).

  • []: determined position in a given sequence;

  • \( U_{v} (\sigma ) = 0,\,{\text{when}}\,C_{v} (\sigma ) < d_{v} \), while \( U_{v} (\sigma ) = 1,\,{\text{when}}\,C_{v} (\sigma ) > d_{i} \).

  • \( U_{i} (\sigma ) \) and \( U_{j} (\sigma ) \): tardiness of order i and order j in \( \sigma \);

  • \( U_{j} (\sigma^{\prime}) \) and \( U_{i} (\sigma^{\prime}) \): tardiness of order j and order i in \( \sigma^{\prime} \);

  • Nb: number of employee bees;

  • Non: number of onlooker bees;

  • ITRN: number of repeat cycles or the stopping criterion that the ABC algorithm terminates;

  • limit: number of improvements;

  • p_scout: the value for the employed bee abandoned;

  • \( {\text{em}}\_{\text{bee}}_{i} \): an employed bee with \( {\text{em}}\_{\text{bee}}_{i} \in R^{n} \), i = 1, 2, …, Nb;

  • \( {\text{on}}\_{\text{bee}}_{i} \): an onlooker bee with \( {\text{on}}\_{\text{bee}}_{i} \in R^{n} \), i = 1, 2, …, Non;

  • \( {\text{em}}\_{\text{bee}}_{ij} \): an employed bee with \( {\text{em}}\_{\text{bee}}_{ij} \in R^{n} \), i = 1,2, …, Nb; j = 1,2, …, ITRN;

  • \( {\text{on}}\_{\text{bee}}_{ij} \): an onlooker bee with \( {\text{on}}\_{\text{bee}}_{ij} \in R^{n} \), i = 1,2, …, Non; j = 1,2, …, ITRN;

  • \( v_{ij} \): a new candidate bee with \( v_{ij} \in R^{n} \), i = 1,2, …, Nb; j = 1,2, …, ITRN;

  • \( f_{i} = \frac{1}{{1 + \mathop \sum \nolimits_{l = 1}^{{N_{\text{b}} }} w_{l} U_{l} \left( \sigma \right)}} \): the fitness value for employed bee i, where an employed bee as a schedule \( \sigma \) of the n orders in this study;

  • \( p\_{\text{bee}}_{i} = \frac{{f_{i} }}{{\mathop \sum \nolimits_{l = 1}^{{N_{\text{b}} }} f_{l} }} \): a selection probability for an employed bee i;

The model can be formally stated as follows. Consider a set of n orders from n different clients and m components for each order. The m components are operated on different machines in parallel. A machine can only process a particular component. In this study, we assume that each order has its own release time. The interruption or preemption is not allowed. Let \( p_{vk} \) be the component k processing time of order v to be processed on Mk. Let \( w_{i} \), \( d_{i} \), and \( r_{i} \) denote the weighted, due date, and release date of order i, respectively. In this study, we aim to explore an optimal sequence to minimize the weighted number of tardy orders. Karp (1972) showed that the total weighted number of tardiness scheduling problem (or named as \( 1//\sum {w_{i} U_{i} } \)) is NP-hard when each order has one component only. Accordingly, our proposed problem \( 1/r_{i} ,OS/\sum {w_{i} U_{i} } \) is also NP-hard. Therefore, some dominant properties and a lower bound are derived to find an optimal solution for the branch-and-bound (B&B) method.

3 The branch-and-bound method

3.1 Dominance and lower bound

We build several properties and a lower bound to facilitate the B&B to quickly find an optimal schedule. To show that \( \sigma \) dominates \( \sigma^{\prime} \), it suffices to prove \( w_{i} U_{i} (\sigma ) + w_{j} U_{j} (\sigma ) \le w_{j} U_{j} (\sigma^{\prime}) + w_{i} U_{i} (\sigma^{\prime}) \) and \( C_{j} (\sigma ) < C_{i} (\sigma^{\prime}) \). The proofs are omitted because they can be discussed by the pairwise interchange method. For more details of the B&B, readers may refer to Wang et al. (2017a, b) and Cheng et al. (2017).

Property 1-1

If \( r_{j} > r_{i} \ge \max_{1 \le k \le m} \left\{ {t_{k} } \right\} \), \( \max_{1 \le k \le m} \{ p_{ik} \} < \max_{1 \le k \le m} \{ p_{jk} \} \), \( r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} > r_{j}^{{}} \), \( r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} < d_{i} \), \( r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} + \max_{1 \le k \le m} \{ p_{ik} \} > d_{i} \), and \( r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} + \max_{1 \le k \le m} \{ p_{jk} \} < d_{j} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 1-2

If \( r_{j} > r_{i} \ge \max_{1 \le k \le m} \left\{ {t_{k} } \right\} \), \( \max_{1 \le k \le m} \{ p_{ik} \} < \max_{1 \le k \le m} \{ p_{jk} \} \), \( r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} > r_{j}^{{}} \), \( r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} > d_{j} \), \( r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} + \max_{1 \le k \le m} \{ p_{ik} \} > d_{i} \), and \( d_{i} > r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 1-3

If \( r_{j} > r_{i} \ge \max_{1 \le k \le m} \left\{ {t_{k} } \right\} \), \( \max_{1 \le k \le m} \{ p_{ik} \} < \max_{1 \le k \le m} \{ p_{jk} \} \), \( r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} > r_{j}^{{}} \), \( r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} > d_{j} \), and \( d_{i} > r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 1-4

If \( r_{j} > r_{i} \ge \max_{1 \le k \le m} \left\{ {t_{k} } \right\} \), \( \max_{1 \le k \le m} \{ p_{ik} \} < \max_{1 \le k \le m} \{ p_{jk} \} \), \( r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} > r_{j}^{{}} \), \( d_{j} > r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} + \max_{1 \le k \le m} \{ p_{jk} \} \), and \( d_{l} > r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} + \max_{1 \le k \le m} \{ p_{ik} \} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 2-1

If \( r_{i} \ge \max_{1 \le k \le m} \left\{ {t_{k} } \right\} \), \( r_{i} + \max_{1 \le k \le m} \left\{ {t_{k} } \right\} < r_{j} \), \( r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} < d_{j} \), and \( r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} < d_{i}^{{}} < r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} + \max_{1 \le k \le m} \{ p_{ik} \} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 2-2

If \( r_{i} \ge \max_{1 \le k \le m} \left\{ {t_{k} } \right\} \), \( r_{i} + \max_{1 \le k \le m} \left\{ {t_{k} } \right\} < r_{j} \), \( r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} > d_{j} \), and \( r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} < d_{i}^{{}} < r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} + \max_{1 \le k \le m} \{ p_{ik} \} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 2-3

If \( r_{i} \ge \max_{1 \le k \le m} \left\{ {t_{k} } \right\} \), \( r_{i} + \max_{1 \le k \le m} \left\{ {t_{k} } \right\} < r_{j} \), \( w_{i} > w_{j} \), and \( r_{j} + \max_{1 \le k \le m} \{ p_{jk} \} < d_{j}^{{}} < r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} + \max_{1 \le k \le m} \{ p_{jk} \} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 2-4

If \( r_{i} \ge \max_{1 \le k \le m} \left\{ {t_{k} } \right\} \), \( r_{i} + \max_{1 \le k \le m} \left\{ {t_{k} } \right\} < r_{j} \), \( r_{j} + \max_{1 \le k \le m} \left\{ {p_{jk} } \right\} > d_{j} \), and \( r_{i} + \max_{1 \le k \le m} \{ p_{ik} \} < d_{i}^{{}} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 2-5

If \( r_{i} \ge \max_{1 \le k \le m} \left\{ {t_{k} } \right\} \), \( r_{i} + \max_{1 \le k \le m} \left\{ {t_{k} } \right\} < r_{j} \), \( d_{j} > r_{i} + \max_{1 \le k \le m} \left\{ {p_{ik} } \right\} + \max_{1 \le k \le m} \left\{ {p_{jk} } \right\} \), and \( d_{j} > r_{j} + \max_{1 \le k \le m} \left\{ {p_{jk} } \right\} + \max_{1 \le k \le m} \left\{ {p_{ik} } \right\} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 3-1

If \( \hbox{max} \left\{ {t_{k} ,r_{j} } \right\} > \hbox{max} \left\{ {t_{k} ,r_{i} } \right\} \) and \( p_{ik} \le p_{jk} \) for k = 1, 2,…, m, and \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{i} \} + p_{ik} + p_{jk} \} < d_{j} \), and \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{j} \} + p_{jk} + p_{ik} \} > d_{i} > \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{i} \} + p_{ik} \} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 3-2

If \( \hbox{max} \left\{ {t_{k} ,r_{j} } \right\} > \hbox{max} \left\{ {t_{k} ,r_{i} } \right\} \) and \( p_{ik} \le p_{jk} \) for k = 1, 2,…, m, and \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{j} \} + p_{jk} \} > d_{j} \), \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{i} \} + p_{ik} \} < d_{i} \), and \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{j} \} + p_{jk} + p_{ik} \} > d_{i} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 3-3

If \( \hbox{max} \left\{ {t_{k} ,r_{j} } \right\} > \hbox{max} \left\{ {t_{k} ,r_{i} } \right\} \) and \( p_{ik} \le p_{jk} \) for k = 1, 2,…, m, \( w_{i} > w_{j} \), and \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{i} \} + p_{ik} + p_{jk} \} > d_{j} > \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{j} \} + p_{jk} \} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 3-4

If \( \hbox{max} \left\{ {t_{k} ,r_{j} } \right\} > \hbox{max} \left\{ {t_{k} ,r_{i} } \right\} \) and \( p_{ik} \le p_{jk} \) for k = 1, 2,…, m, \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{j} \} + p_{jk} \} > d_{j} \), and \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{i} \} + p_{ik} \} < d_{i} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Property 3-5

If \( \hbox{max} \left\{ {t_{k} ,r_{j} } \right\} > \hbox{max} \left\{ {t_{k} ,r_{i} } \right\} \) and \( p_{ik} \le p_{jk} \) for k = 1, 2,…, m, \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{i} \} + p_{ik} + p_{jk} \} < d_{j} \), and \( \max_{1 \le k \le m} \{ \hbox{max} \{ t_{k} ,r_{j} \} + p_{jk} + p_{ik} \} < d_{i} \), then \( \sigma \) dominates \( \sigma^{\prime} \).

Next, we present one more property to justify a feasible sequence of the unscheduled orders. Assume that \( (\pi ,\pi^{c} ) \) is a schedule of orders in which \( \pi \) is a partial determined schedule with q orders and \( \pi^{c} \) is another undetermined part with (n–q) orders. Furthermore, let \( \pi^{\text{edd}} \) be the sequence according to the earliest due date first rule (EDD) of undetermined (n–q) order and \( t_{k} \) denote the finished time of the last order on Mk in \( \pi \) for \( 1 \le k \le m \).

Property 4

If \( \max_{1 \le k \le m} \left\{ {\hbox{max} \{ t_{k} ,r_{j} \} + p_{jk} } \right\}_{{j \in \pi^{c} }} > \max_{{j \in \pi^{c} }} \{ d_{j} \} \) holds, then \( (\pi ,\pi^{edd} ) \) dominates \( (\pi ,\pi^{c} ) \).

In the following, a lower bound is also proposed for the B&B method. Consider \( \pi \) as a partial schedule in which the sequence of the first q orders is scheduled, and \( \pi^{\text{us}} \) as the unscheduled orders with (n–q)\( = n_{1} \) orders. Assume that \( {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{p}_{(q + 1)},} \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{p}_{(q + 2)} , \ldots ,\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{p}_{{(q + n_{1} )}} \) denote the increasing sequence of \( {\sum\nolimits_{k = 1}^{m} {p_{q + 1\;k} } ,}\sum\nolimits_{k = 1}^{m} {p_{q + 2\;k} } , \ldots ,\sum\nolimits_{k = 1}^{m} {p_{{q + n_{1} \;k}} } \). Then, the lower bound (LB) can be easily computed and given by

$$ LB = \sum\nolimits_{i = 1}^{q} {w_{i} U_{i} } + w_{\text{min} } \sum\nolimits_{i = 1}^{{n_{1} }} {I_{{\{ C_{[q]} + \tilde{p}_{(q + i)} > d_{\text{max} } \} }} } , $$

where \( I_{{\{ t > a\} }} = 1 \), \( I_{{\{ t \le a\} }} = 0 \), \( d_{\text{max} } = \max_{{j \in \pi^{US} }} \{ d_{j} \} \), and \( w_{\text{min} } = \min_{{j \in \pi^{US} }} \{ w_{j} \} \).

3.2 Artificial bee colony algorithm

The artificial bee colony (ABC) algorithm has been widely applied to solve a lot of combinatorial problems (Abba Ari et al. (2016), Basturk and Karaboga (2006), Kang et al. (2015, 2016a, b), Tereshko (2000), Tereshko and Lee (2002), Tereshko and Loengarov (2005), Kang and Li (2016), Teodorovic (2003), Lucic and Teodorovic (2002), Teodorovic and Dell’orco (2005), Benatchba et al. (2005), Wedde et al. (2004), Yang (2005a, b), Karaboga (2005), Aydoğdu et al. (2016), Singh and Mann (2017), Xin et al. (2017), and Xue et al. (2018)). Inspired by these observations, we use intelligent behaviors of honeybee swarms to solve problem under study.

Following the design of Karaboga (2005), the three elements of the ABC cover employed bees, onlookers, and scouts. In ABC, two ways, including the multi-point insert method by Chaurasia et al. (2016), Singh (2009), Sundar and Singh (2012), and three-point exchange method by Liang et al. (2002) and Chaurasia et al. (2016), are commonly adopted to generate a new neighborhood solution. The main advantages of two methods are to avoid trapping in a local searching and to explore the search space. The pseudo-code of ABC and the neighborhood local search method are provided in the following.

The main codes of the ABC are given below.

figure a

The details of the neighborhood local search method are given below.

figure b

Let \( {\text{em\_bee}}_{i} = (x_{1} ,x_{2} , \ldots ,x_{n} ) \) denote an employed bee with \( x_{i} \in R \), i = 1, 2, …, n. Consider an employed bee as a schedule of the n orders in this study. During the execution of ABC, a random number encoding method is used to define a set of continuous real numbers to represent the codes of the orders. For example, given em_beei = (0.83, 0.72, 0.34, 0.23, 0.51) as an employed bee, it is decoded as a sequence \( \sigma \) = (5, 4, 2, 1, 3) by the ranking method. To show the impact of parameter settings on the ABC algorithm, four types of ABC algorithms were constructed, each of which was assigned a different parameter setting. Specifically, the parameter settings of the four ABC algorithms are given in Table 1. In addition, we also compare four proposed hybrid ABCs with their corresponding four basic ABC algorithms where the number of limit is set to 0. They are referred as B-ABC1, B-ABC2, B-ABC3, and B-ABC4. Due to the setting of Table 1, B-ABC1 and B-ABC3, and B-ABC2 and B-ABC4 are with the same number of employed bees and the same number of onlookers, but they adopt different levels of limit.

Table 1 Parameter settings of the four types of ABC algorithms
Full size table

3.3 A branch-and-bound algorithm

The depth-first rule is utilized in the branching procedure. The advantage of this policy is that the computer only keeps no more than \( \left( {n - 1} \right) \) nodes for the lower bounds throughout the procedure. In the branch-and-bound method (B&B), the orders are first scheduled in a forward way and select a systematically search and branch down each tree. The steps are summarized in the following:

Step 1: Initialization

Perform eight ABCs and choose the best schedule as the current best solution

Step 2: Branching

Apply the depth-first rule

Step 3: Eliminating

Utilize all dominances to determine if the node is active or non-active. For the non-active nodes

Compute their lower bound by the proposed lower-bound formulas

Compute the weighted number of tardy orders for the full node

Step 4: Bounding

If the lower bound is larger than the initial solution, cut that node and all nodes beyond it in the branch, or if the weighted number of tardy orders for the completed node less than the initial solution, update it as a new current best solution

Step 5: Stopping rule

Repeat to do step 2, step 3, and step 4 until all nodes are visited

4 Computational experiment

In this section, we evaluate the performances of the eight ABCs and the B&B through some computational tests. All the algorithms were coded in a FORTRAN and run on a personal computer with an Intel(R) Core(TM)7 Quad CPU 2.66 GHz with 4 GB RAM. Following the design of Lee (2013) and Leung et al. (2006b, 2007b, 2008a, b), we generated the normal component processing times from Uniform(1, 100) for the order instances. In addition, we generated the order due dates from another Uniform(Pbar(1 − τ − R/2), P(1 − τ + R/2)), where \( Pbar = \sum\nolimits_{k = 1}^{m} {\sum\nolimits_{i = 1}^{n} {p_{ik} } } /m \), and \( \tau \) and R describe the tardiness factor and the range of the due dates, respectively. Six cases of \( \tau \) and R were examined at (\( \tau \), R) = (0.5, 0.75), (0.5, 0.5), (0.5, 0.25) (0.25, 0.25), (0.25, 0.5), and (0.25, 0.75). Following the design of Reeves (1995), we generated the release times from Uniform(0, 100n\( \lambda \)) where \( \lambda \) and n denote the control variable and order size. The values of \( \lambda \) were set at 0.2, 0.5, 0.8. In this paper, we design two parts of the computational experiment comprising the small-size order and the big-size order. (Note that a job is equivalent to an order.)

4.1 Results of small number of orders

For the small-size orders, we set the number of order sizes at n = 14, 16, and the number of three machine sizes at m = 2, 3, 4. We examined one hundred problem instances for each category. Therefore, there were a total of 10,800 instances tested in this experiment. The B&B algorithm would stop and turn to run next instance once node number was over 108.

To evaluate the performance of the B&B, we recorded the average and maximum number of nodes and the average and maximum execution times (in seconds). To evaluate the performance of eight versions of ABCs, we recorded the average error percentage (AEP) and maximum error percentage. The AEP is defined as

$$ {\text{AEP}} = \left[ {(H_{i} - O^{*} )/O^{*} } \right] \times 100\% , $$

where \( H_{i} \) is the objective obtained by using eight ABCs and \( O^{ * } \) is the objective obtained using the B&B.

The performance of the B&B is given in Table 2, where the last column FS is the number of instances the B&B succeeded in achieving the optimal solution. The performances of the eight versions of ABCs are given in Table 3.

Table 2 Performances of B&B as the value of each parameter changes
Full size table
Table 3 Performances of AEP of ABCs as the value of each parameter changes
Full size table

As given in Table 2, the number of machines had little impact on the performance of the B&B. Regarding the impact of parameter λ on the performance of the B&B, it appears in Table 2 that the AEPs of CPU time and nodes tend to decrease for both n = 14 and n = 16 as the value of parameter λ increases, when the other parameters are fixed. For parameter τ, Table 2 shows that the AEPs of nodes and CPU time decrease for n = 14, while they increase for n = 16. There is no apparent pattern of impact of parameters τ and R on the performance of the B&B.

For the impact of the above parameters on the performance of the eight types of ABCs, Table 3 shows no apparent impact of the parameter m. The average AEP first decreases but then increases as m increases for instances of n = 14; however, an opposite trajectory is observed for instances of n = 16. As clearly given in Table 3, the average AEP of the four types of ABC algorithms tends to decrease as the value of λ or τ increases. On the contrary, the average AEP of the eight types of ABCs increases as the value of parameter R increases. Table 3 also confirms that the ABC3, on average, slightly outperformed the other algorithms.

As for the performance of eight ABCs, the box plots in Fig. 1 show the AEP distributions of all the proposed methods. To compare the solution quality among the four basic ABCs (B-ABC1, B-ABC2, B-ABC3, and B-ABC4) and the four hybrid ABCs (ABC1, ABC2, ABC3, and ABC4), analysis of variance (ANOVA) was conducted. The results are given in Table 4. With a p value of less than 0.0001, follow-up Fisher’s least significant difference tests were subsequently conducted to find out the differences of solution quality among the eight algorithms. The reports are presented in Table 5. At the 0.05 level of significance, the AEPs were divided into two groups: the AEPs of ABC1, ABC2, ABC3, and ABC4 were in one group; the AEPs of the B-ABC1, B-ABC2, B-ABC3, and B-ABC4 were in the other group. The ABC3 algorithm with the smallest value of AEP is recommended for small number of orders.

Fig. 1
figure 1

Box plot of AEP for eight algorithms at n = 14,16

Full size image
Table 4 ANOVA table for the small number of jobs
Full size table
Table 5 Results of Fisher’s LSD for the four ABCs and four B-ABCs at n = 14,16
Full size table

4.2 Results of big number of orders

For the big number of jobs, we set the number of order sizes at n = 40 and 80, and number of three machine sizes at m = 2, 5, 10. One hundred instance problems were randomly examined for each case. Consequently, there were also a total of 10,800 problem instances examined in this experiment. To evaluate the performance of the eight versions of ABCs, we reported the mean and maximum RPD. The RPD is defined as

$$ {\text{RPD}} = \left[ {(H_{i} - H^{*} )/H^{*} } \right] \times 100\% , $$

where \( H_{i} \) is the objective obtained by using four ABCs and H*= min{eight versions of ABC algorithms}. The computational results are summarized in Table 4.

As given in Table 6, the RPDs of the four types of ABC algorithms strictly decrease as the values of parameters λ and τ increase for both n = 40 and n = 80. It appears in Table 6 that for both instances of n = 40 and n = 80, there are few changes for the RPDs of the four types of ABC algorithms as the values of parameters R and m increase.

Table 6 Performances of RPD of ABCs as the value of each parameter changes
Full size table

As demonstrated in Fig. 2, the box plots of RPDs show that the four hybrid ABCs (ABC1, ABC2, ABC3, and ABC4) outperformed the four basic ABCs (B-ABC1, B-ABC2, B-ABC3, and B-ABC4) for large numbers of orders. Meanwhile, as shown in Fig. 3, four hybrid ABCs did consume much CPU time than the four basic ABCs for large numbers of orders. An ANOVA was conducted to compare the solution quality among the four basic ABCs and the four hybrid ABCs. Table 7 shows the ANOVA test results. With a p value of less than 0.0001, follow-up Fisher’s least significant difference tests were subsequently conducted to find out the differences of solution quality among the eight algorithms for large number of orders. The results are listed in Table 8. At the 0.05 significance level, the RPDs were divided into several groups: ABC3 in one group, ABC1 in the second group, ABC2 and ABC4 in the third group, B-ABC2 and B-ABC4 in the fourth group. Moreover, the box plots in Fig. 2 also show that the RPDs of the four ABC3 have less dispersion; thus, the ABC3 with both accuracy and stability is recommended for big number of orders.

Fig. 2
figure 2

Box plot of RPD for eight algorithms at n = 40, 80

Full size image
Fig. 3
figure 3

Box plot of CPU time for eight algorithms at n = 40 and 80

Full size image
Table 7 ANOVA table for the big number of jobs
Full size table
Table 8 Results of Fisher’s LSD for the four ABCs and four B-ABCs at n = 40, 80
Full size table

Based on the above test results, we conclude that the ABC3, on average, outperformed the other seven ABCs.

5 Conclusions and suggestions

Recently, the OS models have become important and challenging topics in a lot of practical services and manufacturing environments. Different from previous research assumption that the orders are available at time zero, this paper investigates the condition that orders come in different release times. In this study, we made several main contributions. First, a lower bound and several dominance properties were derived to be used in a B&B for the small-size orders. Second, eight versions of ABCs were also presented to obtain approximate solutions for the big number of orders. Computational experiments were conducted to evaluate the performances of the B&B and eight versions of ABCs, as well as the impacts of parameters on their performances. The experimental results show that, incorporating with the proposed lower bound and dominance properties, the B&B can solve a problem instance up to n = 16 within a reasonable CPU time. In addition, the experimental tests further illustrate that the eight types of ABC algorithms performed satisfactorily in terms of efficacy and efficiency for problem instances of both small and big number of orders. Based on the results of the four versions of ABC algorithms, ABC-3 is recommended for the problem under study because of its superior performance and its quickness in achieving good-quality solutions in term of the AEPs and RPDs. For some interesting issues, one may extend our model to the bi-criterion case or in different machine environments for the future study.