Minimization of total energy consumption in an m-machine flow shop with an exponential time-dependent learning effect

Abstract

This study investigates an energy-aware flow shop scheduling problem with a time-dependent learning effect. The relationship between the traditional and the proposed scheduling problem is shown and objective is to determine a job sequence in which the total energy consumption is minimized. To provide an efficient solution framework, composite lower bounds are proposed to be used in a solution approach with the name of Bounds-based Nested Partition (BBNP). A worst-case analysis on shortest process time heuristic is conducted for theoretical measurement. Computational experiments are performed on randomly generated test instances to evaluate the proposed algorithms. Results show that BBNP has better performance than conventional heuristics and provides considerable computational advantage.

Keywords

flow shop / energy-aware scheduling / learning effect / nested partition / worst-case error bound

Introduction

Conventional scheduling problems with time-based objectives have been widely investigated in the past few decades. Conventional scheduling problems that are usually embedded in a synthetic industrial information system deal with the allocation of jobs on machines over a given time period. The objective is focused on the reduction of production time, which is related to turnover rate and appropriate economic indicators. However, in terms of sustainable development, the consumed energy in scheduling has become a public economic benefit for manufacturing companies with the continuous increase of environmental issues and large amount of energy costs. By contrast, the processing time of a job or an operation is constantly fixed through the entire production for the classical research on scheduling. However, there are many realistic manufacturing environments, the labor or production facility improves continuously over time and the learning effect continuously improve over time, which indicate that a job has a shorter processing time than that of previously scheduled jobs that is an extremely important factor to consider. This condition provides an accurate estimation on energy consumption, which causes better calculation of processing time of workers and machines. Thus, integrating the learning effect to the energy-based scheduling objective will aid in actual processing time approximation and accurate estimation of total energy consumption. For the close relationship between the energy-aware scheduling and scheduling with learning effects, an integrated research on the combined problem should be conducted regardless of its immense complexity.

Despite various studies on the traditional flow shop scheduling problem (FSS), the literature on scheduling problems that consider sustainable factors is limited, and the integrated scheduling problem with simultaneous considerations of energy reduction and learning effects has not been investigated due its high complexity. In this study, we first propose an energy-aware FSS (EAFSS) problem with a time-dependent learning effect. A new efficient framework with bound-based selection, partitioning, and sampling-based strategy is designed to solve the combined problem. This framework can be practically extended to solve other combinatorial problems where efficient bounds can be developed. A bound-based nested partition (BBNP) with a composite bound is proposed to obtain an optimal solution. We also conduct a worst-case analysis on a shortest processing time (SPT) algorithm for theoretical measurement.

The remainder of this paper is organized as follows: Section 2 presents a literature review in terms of FSS with learning effect (FSSLE) and energy-aware scheduling (EAS). Section 3 provides the notations and assumptions. Section 4 shows the relationship between the traditional and proposed problems. Section 5 develops a composite bound for sustainable FSS with the exponential sum-of-processing-time-based learning effects. Sections 6 and 7 describe the proposed composite solution and worst-case analysis on SPT heuristic. Section 8 presents the detailed experimental results and analysis. Section 9 summarizes the conclusions.

Literature review

As a conventional topic, FSS has been intensively investigated in the past few decades. ^{Johnson (1954)}, ^{Gonzalez and Sahni (1978)}, ^{Garey and Johnson (1979)}, and ^{Smutnicki (1998)} investigated typical flow shop models and their associated algorithms. Polynomial solutions can be found in several certain cases (^Johnson,1954). However, in most cases, it is not able to be solved in polynomial time (^{Gonzalez and Sahni, 1978}), which leads to the study on approximation algorithms (^{Garey and Johnson, 1979}; ^{Smutnicki, 1998}). Many real applications have supported Wright’s theory (1936) where the processing time can be remarkably reduced with the increase of production requirements (^{Webb, 1994}). ^{Biskup (1999)} and ^{Cheng and Wang (2000)} successfully introduced Wright’s theory in scheduling. Considerable studies have focused on FSSLE. ^{Lee and Wu (2004)} investigated a two-machine FSS with position-based learning effects. They proposed heuristic and branch-and-bound methods to minimize the total completion time. Recently, ^{Pei et al. (2017)} evaluated a serial-batching scheduling problem with position-based learning effect under single and parallel machine environments, which minimizes the total number of delayed jobs and maximizes the earliness. They developed an optimization algorithm for a single machine setting and proposed a hybrid ba-vns algorithm for a parallel machine setting. For a learning-based scheduling environment, ^{Wang and Xia (2005)} investigated FSS to minimize either the total flow time or makespan. They determined polynomial time solutions in several certain cases. They proposed a heuristic algorithm and confirmed the worst-case error bound of the heuristic. ^{Koulamas and Kyparisis (2007)} considered sum-of-job-processing-time-based and position-based learning effects in a two-machine FSS and showed that the SPT sequence is optimal under several certain cases. On the basis of the similar concept of ^{Wang and Xia (2005)}, ^{Xu et al. (2008)} implemented the worst-case analysis on SPT for the FSSLE. Their objectives are all related to completion time. ^{Pei et al. (2017)} assessed a serial-batch scheduling problem in an environment where coordination exists among multiple factories and resource-dependent processing time and dual constraints of resources are considered. They provided a polynomial-time scheduling rule for the optimization of each single factory and proposed an efficient BA-VNS algorithm to solve the complex coordinate problem. ^{Wu and Lee (2009)}, ^{Rudek (2011)}, ^{Kuo et al. (2012)}, ^{Sun et al. (2013)}, ^{Wang et al. (2013)}, ^{Xu et al. (2016)}, and ^{Gao et al. (2017)} conducted recent studies on FSSLE.

EAS is an area that has been rarely investigated in the scheduling domain regardless of its importance. ^{Liu et al. (2001)}, ^{Artigues et al. (2009)}, ^{Lee and Zomaya (2010)}, ^{Chan et al. (2013)}, and ^{Agrawal and Rao (2014)} conducted previous studies associated on EAS. ^{Liu et al. (2001)} considered power-aware scheduling under timing-constraints. ^{Artigues et al. (2009)} investigated a scheduling problem with energy constraints. Tree searches are applied to provide schedule solutions. ^{Lee and Zomaya (2010)} evaluated a scheduling framework that incorporates various factors related with energy-efficient operation. ^{Chan et al. (2013)} introduced a scheduling problem with weighted flow time and energy graphs. Algorithms with the basic concept of removing certain tasks and maintaining the optimality are developed. ^{Agrawal and Rao (2014)} conducted a systematic study on EAS of a distributed system. They proved that total energy consumption minimization is equivalent to makespan minimization for several special cases. In addition, several heuristics are developed for the solution. ^{Liu et al. (2017)} considered an EAS problem with processing-speed-dependent processing times and proposed a three-stage decomposition approach to minimize energy consumption.

Notations and assumptions

The investigated problem here includes n jobs J=\{J_{\mathrm{1}},J_{\mathrm{2}},\dots ,J_n\}, where each job in the system should be sequentially processed on each of m machines M=\{M_{\mathrm{1}},M_{\mathrm{2}},\dots ,M_m\} and without preemption. The sequence of the job remains the same for each machine, which indicates that each job joins the queue of the next machine after its completion on its own machine and all the queues are assumed to follow a first in first out principle. Similar to the study of ^{Agrawal and Rao (2014)}, the energy consumption in the working and idle states for each machine M_i are denoted as \mu (M_i) and k\mu (M_i), respectively, where \mathrm{0}\le k\le \mathrm{1}. Each job J_j consists m operations O_{\mathrm{1}j},O_{\mathrm{2}j},\dots ,O_{mj}, and these operations should be sequentially processed on each machine. p_{ij} denotes the (original) processing time of operation O_{ij}.

A previous study on the learning effect assumed that the learning curve is position-based, which is a log-linear learning curve p_{jr}=p_j{r}^a where a is a constant index and is positionin a schedule. The processing time exponentially decreases with the increase of position r when . An exponential model of learning effect p_{jr}=p_j{\alpha }^{r-\mathrm{1}}, where \mathrm{0}\le \alpha \le \mathrm{1}, is proposed by ^{Wang and Xia (2005)}. The effect is constant for a given job because p_{j,r+\mathrm{1}}{p}_{j,r}=\alpha. With this approach, the processing time decreases at a reasonably slow rate when \alpha is close to 1. This condition is suitable for several manufacturing environments where the learning effect is slow.

Motivated by this condition, we consider an exponential time-dependent learning effect in this study, and actual processing time p_{ijr} is defined as follows:

(1)p_{ijr}=p_{ij}(\alpha a^{{\sum }_{l=\mathrm{1}}^{r-\mathrm{1}}{p}_{i[l]}}+\beta ),i=\mathrm{1},\mathrm{2},\dots ,m;r,j=\mathrm{1},\mathrm{2},\dots ,n,

Where is the learning rate, \alpha \ge \mathrm{0},\beta \ge \mathrm{0}, and \alpha +\beta =\mathrm{1}.

For a given schedule \mathrm{\pi }, the completion time of operation O_{ij} is denoted by C_{ij}(\mathrm{\pi })=C_{ij},i=\mathrm{1},\mathrm{2},\dots ,m;j=\mathrm{1},\mathrm{2},\dots ,n, and C_j(\mathrm{\pi })=C_j=C_{mj} represents the completion time of job J_j. {\tau }_c(M_i) denotes the total working time on machine M_i, and {\tau }_d(M_i) represents the total idle time on machine M_i. Thus, {\tau }_d(M_i)=C_{\max }-{\tau }_c(M_i). This condition aims to determine a schedule to minimize the total energy consumption, which is expressed as E={\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)]. The problem can be written as Fm|p_{ijr}=p_{ij}(\alpha a^{{\sum }_{l=\mathrm{1}}^{r-\mathrm{1}}{p}_{i[l]}}+\beta )|{\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)](m\ge \mathrm{3}) and it is well known that this problem is NP-complete.

Analysis on minimum energy consumption scheduling with learning effects

Considering that {\tau }_d(M_i)=C_{\max }-{\tau }_c(M_i), total energy consumption E can also be expressed as

E={\displaystyle \sum _{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)]=(\mathrm{1}-k){\displaystyle \sum _{i=\mathrm{1}}^m}\mu (M_i){\tau }_c(M_i)+k{\displaystyle \sum _{i=\mathrm{1}}^m}\mu (M_i)C_{max},

where k and \mu (M_i) are fixed constants. The traditional assumption on the objective of the scheduling problem focuses on the time reduction of tasks and usually includes the minimization of makespan, maximum delay, total completion time, and total tardiness. This assumption is further related to overall turnover rate or customer satisfaction, which are important economic and management factors. The objective considered in this study provides such a sustainable way of scheduling where the total energy consumption is kept low.

On the basis of the above equation, when the learning effect is ignored (processing time is assumed to be constant) and power consumption rates \mu (M_i) are equal for all the machines, that is, \mu (M_{\mathrm{1}})=\mu (M_{\mathrm{2}})=\dots =\mu (M_m)=\mu (M), we can have

\begin{array}{l}E=(\mathrm{1}-k){\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i){\tau }_c(M_i)+k{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i)C_{max}=(\mathrm{1}-k)\mu (M){\displaystyle {\sum }_{i=\mathrm{1}}^m}{\tau }_c(M_i)+\\ k{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i)C_{max}.\end{array}

Considering that k, \mu (M_i), and {\displaystyle {\sum }_{i=\mathrm{1}}^m}{\tau }_c(M_i) are all fixed constants, the problem will be reduced to the minimization of makespan. For the general case, the objective is the addition of two factors, namely, minimum working energy consumption and minimum makespan. The setting of different energy consumption rates for different machines lead to the tradeoffs between economic and sustainable factors because makespan is used as an important corporate economic indicator. In addition, the entire consumed time can be controlled within a reasonable limit by reducing the energy consumption although the minimum energy consumption cannot guarantee the minimum makespan.

Hence, the sustainable perspective does not conflict with the corporate economic profits or management level in terms of EAS for the operation management of manufacturers. On the contrary, a good control of consumed energy can have a remarkable impact on the reduction of production time and costs. The benefit of energy-aware objective is that it is a generalization of minimizing production time, which can lead to a better balance. The different settings of energy consumption rates provide opportunities in configuring the problem based on various preferences.

Composite lower bounds (LBs)

In this section, we propose a composite bound on partial solutions under three different perspectives, namely, LB(\mathrm{1}), LB(\mathrm{2}), and LB(\mathrm{3}), which is applied to reduce the total nodes searched in a branch-and-bound framework. Let \mathrm{\pi }=(PS,US) be a schedule of jobs where PS and US represent the scheduled and unscheduled parts, respectively.

Lemma 1. (^{Wang et al. (2009)}) For problem \mathrm{1}|p_{jr}=p_j(\alpha a^{{\sum }_{l=\mathrm{1}}^{r-\mathrm{1}}{p}_{i[l]}}+\beta )|C_{max}, an optimal schedule can be obtained by sequencing the jobs in non-decreasing order of p_j (i.e., the SPT rule).

LB 1

First, we consider an LB for the term C_{max}. For a partial schedule with k scheduled jobs, the completion time of the (k+\mathrm{1}) th job on machine M_i can be written as

\begin{array}{l}{C}_{i[k+\mathrm{1}]}(\mathrm{\pi })=\max \{C_{i-\mathrm{1},[k+\mathrm{1}]}(\mathrm{\pi }),C_{i[k]}(\mathrm{\pi })\}+p_{i[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}}+\beta )\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\ge \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{C}_{i[k]}(\mathrm{\pi })+p_{i[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}}+\beta ).\end{array}

Similarly,

C_{m[k+\mathrm{1}]}(\mathrm{\pi })\ge C_{i[k]}(\mathrm{\pi })+{\displaystyle \sum _{u=i}^m}{p}_{u[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}}+\beta ),

C_{m[k+j]}(\mathrm{\pi })\ge C_{i[k]}(\mathrm{\pi })+{\displaystyle \sum _{u=i}^{m-\mathrm{1}}}{p}_{u[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}}+\beta )

+{\displaystyle \sum _{h=\mathrm{1}}^j}{p}_{m[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{m[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}{p}_{m[k+l]}}}+\beta ),

where \mathrm{1}\le j\le n-k.

Hence, the makespan is

\begin{array}{l}{C}_{\max }=C_{[n]}(\mathrm{\pi })\ge C_{i[k]}(\mathrm{\pi })+{\displaystyle \sum _{u=i}^{m-\mathrm{1}}}{p}_{u[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}}+\beta )\\ \end{array}

(2)+{\displaystyle \sum _{h=\mathrm{1}}^{n-k}}{p}_{m[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{m[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}{p}_{m[k+l]}}}+\beta ).

The first term is a constant, and an LB can be obtained by minimizing the last two terms. From Lemma 1, the term {\displaystyle {\sum }_{h=\mathrm{1}}^{n-k}}{p}_{m[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{m[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}{p}_{m[k+l]}}}+\beta ) can be minimized by sequencing the jobs in non-decreasing order of p_{m[j]}. Thus, the LB for C_{max} concerning machine M_i is

L{B}_i(C_{\max })=C_{i[k]}(\mathrm{\pi })+{\displaystyle \sum _{u=i}^{m-\mathrm{1}}}{p}_{u{[k+\mathrm{1}]}^{*}}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}}+\beta )

(3)+{\displaystyle \sum _{h=\mathrm{1}}^{n-k}}{p}_{m[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{m[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}{p}_{m[k+l]}}}+\beta ),

where {[k+\mathrm{1}]}^{*}=\arg \hspace{0.17em}\underset{[k+\mathrm{1}]}{\min }{\displaystyle {\sum }_{u=i}^{m-\mathrm{1}}}{p}_{u[k+\mathrm{1}]}.

For the term {\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i){\tau }_c(M_i), we can easily show that

\begin{array}{l}{\displaystyle \sum _{i=\mathrm{1}}^m}\mu (M_i){\tau }_c(M_i)\ge {\mu }_{min}{\displaystyle \sum _{i=\mathrm{1}}^m}{\displaystyle \sum _{j=\mathrm{1}}^k}{p}_{i[j]}(\alpha a^{{\sum }_{l=\mathrm{1}}^{j-\mathrm{1}}{p}_{i[l]}}+\beta )\\ +{\mu }_{min}{\displaystyle \sum _{h=\mathrm{1}}^{n-k}}{L}_{(k+h)}(\alpha a^{\underset{i=\mathrm{1}}{\overset{m}{\min }}{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}{L}_{(k+l)}}}+\beta ).\end{array}

where {\mu }_{min} is the minimum value among {\mu }_i(\mathrm{1}\le i\le m), and L_{(k+\mathrm{1})}\le L_{(k+\mathrm{2})}\le \cdots \le L_{(n)} is a nondecreasing order of total normal processing times of unscheduled jobs.

In addition,

\begin{array}{l}{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i){\tau }_c(M_i)\ge {\mu }_{min}{\displaystyle {\sum }_{i=\mathrm{1}}^m}{\displaystyle {\sum }_{j=\mathrm{1}}^k}{p}_{i[j]}(\alpha a^{{\sum }_{l=\mathrm{1}}^{j-\mathrm{1}}{p}_{i[l]}}+\beta )+\\ {\displaystyle {\sum }_{i=\mathrm{1}}^m}{\displaystyle {\sum }_{h=\mathrm{1}}^{n-k}}{p}_{i(k+h)}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}{p}_{i(k+l)}}}+\beta ).\\ \end{array}

Thus, the LB for the term {\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i){\tau }_c(M_i) is

L{B}^{\mathrm{1}}=\min ({\mu }_{min}{\displaystyle \sum _{i=\mathrm{1}}^m{\displaystyle \sum _{j=\mathrm{1}}^k}}{p}_{i[j]}(\alpha a^{{\sum }_{l=\mathrm{1}}^{j-\mathrm{1}}{p}_{i[l]}}+\beta )+{\mu }_{min}{\displaystyle \sum _{h=\mathrm{1}}^{n-k}}{L}_{(k+h)}(\alpha a^{\underset{i=\mathrm{1}}{\overset{m}{\min }}{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}{L}_{(k+l)}}}+\beta ),

{\mu }_{min}{\displaystyle {\sum }_{i=\mathrm{1}}^m}{\displaystyle {\sum }_{j=\mathrm{1}}^k}{p}_{i[j]}(\alpha a^{{\sum }_{l=\mathrm{1}}^{j-\mathrm{1}}{p}_{i[l]}}+\beta )+{\displaystyle {\sum }_{i=\mathrm{1}}^m}{\displaystyle {\sum }_{h=\mathrm{1}}^{n-k}}{p}_{i(k+h)}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}{p}_{i(k+l)}}}+\beta )).

Accordingly, LB{(\mathrm{1})}_i=(\mathrm{1}-k)L{B}^{\mathrm{1}}+k{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i)LB{(\mathrm{1})}_i(C_{max}). We select the maximum value of LB{(\mathrm{2})}_i to obtain a tight LB, and LB(\mathrm{1}) is denoted as follows:

(4)LB(\mathrm{1})=\max \{LB{(\mathrm{1})}_{\mathrm{1}},LB{(\mathrm{1})}_{\mathrm{2}},\dots ,LB{(\mathrm{1})}_m\}.

LB 2

Following the similar perspective that each certain machine generates an LB is taken, we consider all the remaining operations of a job in the calculation of C_{i[k+\mathrm{1}]}(\mathrm{\pi }) compared with LB 1. Thus, we have

C_{i[k+\mathrm{1}]}(\mathrm{\pi })\ge C_{i[k]}(\mathrm{\pi })+p_{i[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}}+\beta ).

Similarly,

C_{m[k+\mathrm{1}]}(\mathrm{\pi })\ge C_{i[k]}(\mathrm{\pi })+{\displaystyle \sum _{u=i}^m}{p}_{u[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}}+\beta ),

C_{m[k+j]}(\mathrm{\pi })\ge C_{i[k]}(\mathrm{\pi })+{\displaystyle \sum _{h=\mathrm{1}}^j}{p}_{i[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{i[k+l]}}+\beta )

+{\displaystyle \sum _{u=i+\mathrm{1}}^m}{p}_{u[k+j]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{j-\mathrm{1}}}{p}_{u[k+l]}}+\beta ),

where \mathrm{1}\le j\le n-k.

Hence, the makespan is

C_{max}=C_{[n]}(\mathrm{\pi })\ge C_{i[k]}(\mathrm{\pi })+{\displaystyle \sum _{h=\mathrm{1}}^{n-k}}{p}_{i[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{i[k+l]}}+\beta )

(5)+{\displaystyle \sum _{u=i+\mathrm{1}}^m}{p}_{u[n]}(\alpha a^{{\sum }_{l=\mathrm{1}}^{n-\mathrm{1}}{p}_{u[l]}}+\beta ).

The first term is a constant, and the minimization of the last two terms will lead to a low bound. From Lemma 1, the term {\displaystyle {\sum }_{h=\mathrm{1}}^{n-k}}{p}_{i[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}{p}_{i[k+l]}}}+\beta ) can be minimized by sequencing the jobs in non-decreasing order of p_{i[j]}. Thus, the LB for machine M_i is

L{B}_i(C_{\max })=C_{i[k]}(\mathrm{\pi })+{\displaystyle \sum _{h=\mathrm{1}}^{n-k}}{p}_{i[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{i[k+l]}}+\beta )

(6)+{\displaystyle \sum _{u=i+\mathrm{1}}^m}{p}_{u{[n]}^{*}}(\alpha a^{{\sum }_{l=\mathrm{1}}^{n-\mathrm{1}}{p}_{u[l]}}+\beta ).

where {[n]}^{*}=\arg \hspace{0.17em}\underset{[n]}{\min }{\displaystyle {\sum }_{u=i+\mathrm{1}}^m}{p}_{u{[n]}^{*}}.

Accordingly, LB{(\mathrm{2})}_i=(\mathrm{1}-k)L{B}^{\mathrm{1}}+k{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i)LB{(\mathrm{2})}_i(C_{max}). We select the maximum value of LB{(\mathrm{2})}_i to obtain a tight LB, and LB(\mathrm{2}) is denoted as follows:

(7)LB(\mathrm{2})=\max \{LB{(\mathrm{2})}_{\mathrm{1}},LB{(\mathrm{2})}_{\mathrm{2}},\dots ,LB{(\mathrm{2})}_m\}.

LB 3

We take a new perspective for each job in the calculation of LB 3. C_{i[k+\mathrm{1}]}(\mathrm{\pi }) is calculated based on the arbitrary position of a certain job.

\begin{array}{l}{C}_{i[k+\mathrm{1}]}(\mathrm{\pi })=\max \{C_{i-\mathrm{1},[k+\mathrm{1}]}(\mathrm{\pi }),C_{i[k]}(\mathrm{\pi })\}+p_{i[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}}+\beta )\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\ge \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{C}_{\mathrm{1}[k]}(\mathrm{\pi })+{\displaystyle \sum _{u=\mathrm{1}}^i}{p}_{u[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}}+\beta ).\end{array}

Similarly,

C_{m[k+\mathrm{1}]}(\mathrm{\pi })\ge C_{\mathrm{1}[k]}(\mathrm{\pi })+{\displaystyle \sum _{u=\mathrm{1}}^m}{p}_{u[k+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}}+\beta ),

C_{i[k+j]}(\mathrm{\pi })\ge C_{\mathrm{1}[k]}(\mathrm{\pi })+{\displaystyle \sum _{h=\mathrm{1}}^{j-(w+\mathrm{1})}}{p}_{i[k+w+h+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{i[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{w+\mathrm{1}}}{p}_{i[k+l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{i[k+w+l+\mathrm{1}]}}+\beta )

+{\displaystyle \sum _{h=\mathrm{1}}^w}{p}_{\mathrm{1}[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{\mathrm{1}[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{\mathrm{1}[k+l]}}+\beta )+{\displaystyle \sum _{u=\mathrm{1}}^i}{p}_{u[k+w+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^w}{p}_{u[k+l]}}+\beta )

where \mathrm{1}\le j\le n-k, \mathrm{1}\le w\le j-k.

C_{m[k+j]}(\mathrm{\pi })\ge C_{\mathrm{1}[k]}(\mathrm{\pi })+{\displaystyle \sum _{h=\mathrm{1}}^{j-(w+\mathrm{1})}}{p}_{m[k+w+h+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{m[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{w+\mathrm{1}}}{p}_{m[k+l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{m[k+w+l+\mathrm{1}]}}+\beta )

+{\displaystyle \sum _{h=\mathrm{1}}^w}{p}_{\mathrm{1}[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{\mathrm{1}[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{\mathrm{1}[k+l]}}+\beta )+{\displaystyle \sum _{u=\mathrm{1}}^m}{p}_{u[k+w+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^w}{p}_{u[k+l]}}+\beta ),

where \mathrm{1}\le j\le n-k, \mathrm{1}\le w\le j-k.

Hence, the makespan is

C_{\max }=C_{[n]}(\mathrm{\pi })\ge C_{\mathrm{1}[k]}(\mathrm{\pi })+{\displaystyle \sum _{h=\mathrm{1}}^{n-(k+w+\mathrm{1})}}{p}_{m[k+w+h+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{m[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{w+\mathrm{1}}}{p}_{m[k+l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{m[k+w+l+\mathrm{1}]}}+\beta )

(8)+{\displaystyle \sum _{h=\mathrm{1}}^w}{p}_{\mathrm{1}[k+h]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{\mathrm{1}[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{\mathrm{1}[k+l]}}+\beta )+{\displaystyle \sum _{u=\mathrm{1}}^m}{p}_{u[k+w+\mathrm{1}]}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^w}{p}_{u[k+l]}}+\beta ),

where \mathrm{1}\le w\le n-k The first term is a constant, and the minimization of the last three terms will lead to an LB. Moreover, the second term is minimized by sequencing all jobs in a non-decreasing order of p_{\min (j)}=\min \{p_{\mathrm{1}[j]},p_{m[j]}\}based on Lemma 1, except for the {(k+w+\mathrm{1})}_{th} job. By contrast, the actual processing time can be minimized by increasing the accumulated learning effect. Hence, we take p_{\max (j)}=\min \{p_{\mathrm{1}[j]},p_{m[j]}\} as the processing time of the past position. Consequently, the LB for job J_j is

L{B}_j(C_{max})=C_{\mathrm{1}[k]}(\mathrm{\pi })+{\displaystyle \sum _{u=\mathrm{1}}^m}{p}_{uj}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{u[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{n-k-\mathrm{1}}}{p}_{u[k+l]}}+\beta )

(9)+{\displaystyle \sum _{h=\mathrm{1}}^{n-k-\mathrm{1}}}{p}_{\min (k+h)}(\alpha a^{{\sum }_{l=\mathrm{1}}^k{p}_{\mathrm{1}[l]}+{\displaystyle {\sum }_{l=\mathrm{1}}^{h-\mathrm{1}}}{p}_{\max (k+h)}}+\beta ),

where k\le j\le n-k, k\le h\le n-k.

Accordingly, LB{(\mathrm{3})}_j=(\mathrm{1}-k)L{B}^{\mathrm{1}}+k{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i)LB{(\mathrm{3})}_j(C_{max}). We use the maximum value of LB{(\mathrm{2})}_i to obtain a tight LB, and LB(\mathrm{1}) is denoted as follows:

(10)LB(\mathrm{3})=\max \{LB{(\mathrm{3})}_{\mathrm{1}},LB{(\mathrm{3})}_{\mathrm{2}},\dots ,LB{(\mathrm{3})}_{n-k}\}.

Three LBs are derived from different perspectives, and these LBs form the composite bound by using their maximum value. Thus, the composite bound is denoted as

(11)LB=\max \{LB(\mathrm{1}),LB(\mathrm{2}),LB(\mathrm{3})\}.

Algorithms

Two heuristic algorithms

Considering that the proposed problem on m-machine (m\ge \mathrm{3}) flow shop is NP-complete, heuristic algorithms can be constructed to solve it within a limited amount of time. In this study, we use two heuristics, namely, O(m{n}^{\mathrm{2}}) NEH heuristic of Nawaz et al. (1983) and O(m{n}^{\mathrm{4}}) FL heuristic of Framinan and Leisten (2003) to solve Fm|p_{ijr}=p_{ij}(\alpha a^{{\sum }_{l=\mathrm{1}}^{r-\mathrm{1}}{p}_{i[l]}}+\beta )|{\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)](m\ge \mathrm{3}). They are widely applied and shown to be efficient in solving FSS. Now, we provide the modified NEH and FL algorithms with time complexity of O(m{n}^{\mathrm{3}}) and O(m{n}^{\mathrm{4}}), respectively.

NEH algorithm

Step 1. Calculate total normal processing time L_j of each job J_j.

Step 2. Denote the SPT sequence \mathrm{\pi }, where all jobs are sorted in non-decreasing order of L_j, and let {\mathrm{\pi }}_k be job in the kth position of \mathrm{\pi }.

Step 3. Select {\mathrm{\pi }}_{\mathrm{1}}, {\mathrm{\pi }}_{\mathrm{2}} from \mathrm{\pi }, switch their positions, calculate the energy consumption of the two possible sequences, and select the better one. The relative positions of the two jobs will not change in the remaining steps. Set j=\mathrm{3}.

Step 4. Use {\mathrm{\pi }}_j, insert it in j possible positions of the partial sequence in the previous steps and result in j sequences, and calculate the energy of these sequences to find the best sequence. Keep the relative positions of jobs in the current best sequence unchanged.

Step 5. If j=n, STOP; otherwise set j=j+\mathrm{1} and go to Step 4.

FL algorithm

Step 1. Calculate total normal processing time L_j of each job J_j.

Step 2. Denote the SPT sequence \mathrm{\pi }, where all jobs are sorted in non-decreasing order of L_j, and denote {\mathrm{\pi }}_k the job in the kth position of \mathrm{\pi }.

Step 3. Set k=\mathrm{2}. Pick {\mathrm{\pi }}_{\mathrm{1}}, {\mathrm{\pi }}_{\mathrm{2}} from \mathrm{\pi }, switch their positions, calculate the energy consumption of the two possible sequences, and select the better one. The relative positions of the two jobs will not change in the remaining steps.

Step 4. Set k=k+\mathrm{1}. Pick {\mathrm{\pi }}_j, insert it in k possible positions of the partial sequence found in the previous steps and result in k sequences, calculate the energy of these sequences to find the best sequence, and go to Step 5.

Step 5. Interchange jobs in all possible positions i and j of the above best sequence, where , . This process will result in k(k-\mathrm{1})/\mathrm{2} sequences, and select the one with minimum energy consumption as the best partial sequence.

Step 6. If k=n, STOP; otherwise, go to Step 4.

BBNP algorithm

On the basis of the abovementioned studies, we propose the BBNP algorithm in this subsection. We combine the above composite LB with Nested Partition algorithm. ^{Shi and Ólafsson (2000)} proposed the NP algorithm, where they optimized the allocation of computational effort during searching and sustained the global view, in which considerable computational efforts are allocated to the most promising region. The NP algorithm has been successfully applied in a wide range of combinatorial and large-scale optimization problems (^{Shi et al. 2001}; ^{Wu et al. 2010})

For each iteration of a general NP framework, the most promising region is divided into small subregions (partitioning) and the remaining parts are aggravated as surrounding regions. Then, samples are randomly selected from subregions and surrounding regions (random sampling). Subsequently, the promising index is calculated for each region, and this promising index will serve as the guidance direction for the next iteration. Finally, the movement is performed based on the promising index.

However, good implementation of the partition and sampling procedure is difficult for the NP method. For the mitigation and improvement of the performance of the algorithm, we introduce the LB and upper bound (UB) in the solution, which can provide a mathematical-based strategy of partitioning and sampling and a good guide for the implementation.

Bounds-based-partitioning (BBP)

Partitioning is a key step used in BBNP. For partitioning, the promising region is divided into several small subregions. Given a huge feasible solution space, the underlying problem is that the computational effort should not be wasted in the subregions that are not able to contribute to optimum searching. By contrast, BBNP trims the subregion that cannot generate the optimal solution and reduces the searching region to a small scale. To achieve this condition, a good UB should be determined, calculate the LB for {\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)] of the unfathomed partial schedules, and trim the useless regions with the UB smaller than LB. The sampling procedure is only implemented in the remaining subregion. Figure 1 illustrates the BBP procedure.

BBP procedure

Step 1. Obtain the UB of BBNP by implementing the heuristic algorithms and select the best solution generated.

Step 2. In the kth level, divide promising region \theta into n-k subregions by partitioning.

Step 3. Calculate the LB for unfathomed partial schedules or C_{\max } of the completed schedules for each obtained subregion.

Step 4. Trim the useless subregions with UB smaller than LB and obtain M_{\sigma (k)} subregions. Denote {\sigma }_{\mathrm{1}}(k),{\sigma }_{\mathrm{2}}(k),\dots ,{\sigma }_{M_{\sigma (k)}}(k) as the final subregions to be investigated.

Bound-based-sampling (BBS)

Sampling should be implemented for each subregion acquired in the above procedure. An efficient sampling strategy provides an actual reflection of the subregion and has a direct impact on the performance of BBNP. The solution obtained from the sampling can be used as the evaluation factor and the new UB when it is smaller than the current UB. Similar to the previous procedure, we introduce bounds to trim the nodes that are unlikely to lead to optimum. The BBS procedure is shown in Fig. 2.

BBS procedure

Step 1. For subregion {\sigma }_j(k) to be sampled, the (k+\mathrm{1})th level node is fixed by BBP procedure. Calculate the LB for each of the rest n-k-\mathrm{1} levels.

Step 2. In the (k+\mathrm{2})th level, trim its subregion with UB smaller than LB, and implement a random selection in the remaining subregions to allocate job on the (k+\mathrm{2})th level node.

Step 3. Repeat Step 2 in (k+\mathrm{3})th, (k+\mathrm{4})th,\dots ,(n-\mathrm{1})th level.

To avoid duplicate sampling, construct a new archive to store history sample nodes in each BBS procedure, and this archive is used to compare with new samples.

Estimating the promising index and backtracking

This procedure is the same with conventional NP framework and the promising index is calculated by the best objective value determined in a particular region.

The full BBNP algorithm is described as follows:

BBNP algorithm

Step 1. Denote d as the algorithm level, t as the run time, and set d=\mathrm{1} and t=\mathrm{0}.

Step 2. If d>n or t>TIMELIMIT, then STOP.

Step 3. Implement BBP procedure to divide root region \theta into n initial subregions without generating any surrounding region.

Step 4. Use the BBS procedure in every current region.

Step 5. Calculate the promising index. If the best promising index exists in a subregion {\sigma }^{*}, go to Step 6; otherwise, go to Step 7.

Step 6. Select {\sigma }^{*} as the next promising region. Generate the surrounding region with other solution space. Set d=d+\mathrm{1} and t=CURRENTTIME.

Step 7. Backtrack to the parent region of the current promising region. Set d=d-\mathrm{1} and t=CURRENTTIME.

Worst-case bounds

On the basis of Lemma 1, we can build an approximate solution by using the SPT rule to solve Fm|p_{ijr}=p_{ij}(\alpha a^{{\sum }_{l=\mathrm{1}}^{r-\mathrm{1}}{p}_{i[l]}}+\beta )|{\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)].

Theorem 1. Let {\mathrm{\pi }}^{*} be an optimal schedule and \mathrm{\pi } be an SPT schedule for Fm|p_{ijr}=p_{ij}(\alpha a^{{\sum }_{l=\mathrm{1}}^{r-\mathrm{1}}{p}_{i[l]}}+\beta )|{\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)] problem. Then,

(12){\displaystyle \frac{{\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)](\mathrm{\pi })}{{\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)]({\mathrm{\pi }}^{*})}}\le {\displaystyle \frac{m}{(\alpha a^{P_{max}}+\beta )}}{\displaystyle \frac{{\mu }_{max}(\mathrm{1}-k)+k{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i)}{{\mu }_{min}(\mathrm{1}-k)+k{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i)}},

Where P_{max}=\max \{{\displaystyle {\sum }_{l=\mathrm{1}}^n}{p}_{il}-p_{imin}|i=\mathrm{1},\mathrm{2},\dots ,m\}, P_{imin}=\min \{p_{ij}|j=\mathrm{1},\mathrm{2},\dots ,n\}, {\mu }_{max}=ma{x}_{i=\mathrm{1}}^m\mu (M_i), and {\mu }_{min}=mi{n}_{i=\mathrm{1}}^m\mu (M_i).

Proof. Similar to the proof in ^{Wang J B and Wang J J (2014)} for an SPT schedule \mathrm{\pi }, where L_{\mathrm{1}}\le L_{\mathrm{2}}\le \dots \le L_n, we have

(13)\begin{array}{l}{C}_j(\mathrm{\pi })\le L_{\mathrm{1}}+L_{\mathrm{2}}(\alpha a^{p_{\min ,\mathrm{1}}}+\beta )+L_{\mathrm{3}}(\alpha a^{p_{\min ,\mathrm{1}}+p_{\min ,\mathrm{2}}}+\beta )+\dots +L_j(\alpha a^{p_{\min ,\mathrm{1}}+p_{\min ,\mathrm{2}}+\dots +p_{\min ,j-\mathrm{1}}}+\beta )\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\le {\displaystyle \sum _{l=\mathrm{1}}^j{L}_l},\end{array}

where P_{\min ,j}=\min \{p_{ij}|i=\mathrm{1},\mathrm{2},\dots ,m\}. Thus,

(14)C_{\max }(S)\le {\displaystyle \sum _{j=\mathrm{1}}^n{L}_j.}

Denote {\mathrm{\pi }}^{*}=(J_{[\mathrm{1}]},J_{[\mathrm{2}]},\dots ,J_{[n]}) as the optimal schedule, where [j] is job that is sequenced at the jth position of {\mathrm{\pi }}^{*}, we have

C_{\mathrm{1}[j]}=p_{\mathrm{1}[\mathrm{1}]}+p_{\mathrm{1}[\mathrm{2}]}(\alpha a^{p_{\mathrm{1}[\mathrm{1}]}}+\beta )+\cdots +p_{\mathrm{1}[j]}(\alpha a^{p_{\mathrm{1}[\mathrm{1}]}+p_{\mathrm{1}[\mathrm{2}]}+\cdots +p_{\mathrm{1}[j-\mathrm{1}]}}+\beta ),

C_{\mathrm{2}[j]}\ge p_{\mathrm{2}[\mathrm{1}]}+p_{\mathrm{2}[\mathrm{2}]}(\alpha a^{p_{\mathrm{2}[\mathrm{1}]}}+\beta )+\cdots +p_{\mathrm{2}[j]}(\alpha a^{p_{\mathrm{2}[\mathrm{1}]}+p_{\mathrm{2}[\mathrm{2}]}+\cdots +p_{\mathrm{2}[j-\mathrm{1}]}}+\beta ),

\cdots

C_{m[j]}\ge p_{m[\mathrm{1}]}+p_{m[\mathrm{2}]}(\alpha a^{p_{m[\mathrm{1}]}}+\beta )+\cdots +p_{m[j]}(\alpha a^{p_{m[\mathrm{1}]}+p_{m[\mathrm{2}]}+\cdots +p_{m[j-\mathrm{1}]}}+\beta ).

Hence,

(15)C_{[j]}(S^{*})\le {\displaystyle \frac{\mathrm{1}}{m}}{\displaystyle \sum _{l=\mathrm{1}}^j{L}_l}(\alpha a^{p_{max}}+\beta ),

where P_{\max }=\max \{{\displaystyle {\sum }_{l=\mathrm{1}}^n}{p}_{il}-p_{imin}|i=\mathrm{1},\mathrm{2},\dots ,m\} and P_{i\min }=\min \{p_{ij}|i=\mathrm{1},\mathrm{2},\dots ,n\}. Thus,

(16)C_{\max }(S^{*})\le {\displaystyle \frac{\mathrm{1}}{m}}{\displaystyle \sum _{l=\mathrm{1}}^n{L}_l}(\alpha a^{p_{max}}+\beta )={\displaystyle \frac{\mathrm{1}}{m}}{\displaystyle \sum _{l=\mathrm{1}}^n{L}_l}(\alpha a^{p_{max}}+\beta ).

Consequently, from (14) and (16), we have

\begin{array}{l}{\displaystyle \frac{{\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)](\mathrm{\pi })}{{\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)]({\mathrm{\pi }}^{*})}}\\ \le {\displaystyle \frac{{\mu }_{max}(\mathrm{1}-k){\displaystyle {\sum }_{j=\mathrm{1}}^n{L}_j}+k{\displaystyle {\sum }_{i=\mathrm{1}}^m\mu (M_i)}{\displaystyle {\sum }_{j=\mathrm{1}}^n{L}_j}}{{\mu }_{max}(\mathrm{1}-k){\displaystyle {\sum }_{j=\mathrm{1}}^n{L}_j}{\displaystyle \frac{m}{(\alpha a^{P_{max}}+\beta )}}+k{\displaystyle {\sum }_{i=\mathrm{1}}^m\mu (M_i)}{\displaystyle {\sum }_{j=\mathrm{1}}^n{L}_j{\displaystyle \frac{m}{(\alpha a^{P_{max}}+\beta )}}}}}\\ \le {\displaystyle \frac{m}{(\alpha a^{P_{max}}+\beta )}}{\displaystyle \frac{{\mu }_{max}(\mathrm{1}-k)+k{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i)}{{\mu }_{min}(\mathrm{1}-k)+k{\displaystyle {\sum }_{i=\mathrm{1}}^m}\mu (M_i)}}.\end{array}



Computational experiments

For the evaluation of the heuristics and BBNP, computational experiments are conducted in this section. The algorithms are coded in C+ + and run on a Pentium 4 with 2 GB RAM personal computer. The test problems are generated based on ^{Li et al. (2013)} and ^{Wang and Wang (2014)}, and their specifications are shown as follows:

• learning rate: a=\{\mathrm{0.7},\mathrm{0.8},\mathrm{0.9}\};

• processing time: p_{ij}\in U[\mathrm{1},\mathrm{100}];

• energy consumption in the working state: \mu (M_i)\in (\mathrm{1},\mathrm{2});

• factors: \alpha =\beta =\mathrm{0.5}, k\in (\mathrm{0},\mathrm{1}).

Medium size instances:

• machine number: m=\mathrm{3},\mathrm{5};

• job number: n = 9,10,11,12,13,14;

• time limit of BBNP approach: 900 s.

Large size instances:

• machine number: m=\mathrm{5};

• job number: n = 20,50,100,150,200;

• time limit of BBNP approach: 1800s.

For each combination of n-a-m, 20 random instances are generated.

Tables 1 and 2 show the computation results of medium-size problems. The average and maximum error gap are used to reflect the performance of heuristic algorithms. The error gap of the solution is calculated as follows:

(V_{\mathrm{Heur}}-V_{\mathrm{opt}})/V_{\mathrm{opt}}\times \mathrm{100}\%,

where V_{\mathrm{Heur}} is the value {\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)] of the solution generated by the heuristic algorithms, and V_{\mathrm{opt}} is the value {\displaystyle {\sum }_{i=\mathrm{1}}^m}[\mu (M_i){\tau }_c(M_i)+k\mu (M_i){\tau }_d(M_i)] of the optimal schedule. From the results, FL is more efficient than SPT and NEH. The performance is enhanced when the new framework BBNP is applied.

The frequency of maximum value, which indicates the dominating frequency of one LB for the partial schedule, is recorded in Table 3 when the composite bound method is applied. The maximum value is defined as M{N}_i/TN where M{N}_i is the number in which LB i dominates the others and TN is total number of iterations for one run. For the composite bounds, the frequency of domination of each LB on the evaluation of the partial schedule is almost equal through the results of frequency of maximum value. Hence, no superiority is observed among the domination of each LB in the composite strategy.

Table 4 shows the computation results of large-sized problems. In this experiment, the average and maximum ratio {\displaystyle \frac{E(Heur)}{E(ARB)}} are used as the indicator on the performance of heuristic algorithms, where E is the total energy, Heur\in \{SPT,NEH,FL,BBNP\} and ARB is any busy schedule (^{Smutnicki 1998}). The ARB algorithm is selected as the reference value because it is a simple and arbitrary algorithm. From the results, the BBNP algorithm is more efficient than FL and FL is the most efficient among all the heuristics for large-scale instances.

Summary

In this study, an EAFSS problem with an exponential time-dependent learning effect is investigated. As shown in Section 4, the conveyed message is scheduling of minimizing energy consumption is a generalization of minimizing makespan for the proposed problem, and the perspective of economics and environment are highly related in this scope. For the solution, the newly proposed solution framework BBNP is found to be effective and shows a better performance in the numerical experiment. SPT is shown to have a tight bound with the worst-case analysis. Composite bounds are developed and shown to provide considerable computational advantages. However, no superiority is observed among the different LBs.

For future research, many complicated manufacturing environments, such as job shop and flexible job shop can be introduced and investigated. Multi-objective optimization can be conducted to investigate the relationship between different factors.

References

[1] Agrawal P, Rao S (2014). Energy-aware scheduling of distributed systems. IEEE Transactions on Automation Science and Engineering, 11(4): 1163–1175

[2] Artigues C, Lopez P, Haït A (2009). Scheduling under energy constraints. In: International Conference on Industrial Engineering and Systems Management (IESM 2009)

[3] Biskup D (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1): 173–178

[4] Chan S H, Lam T W, Lee L K (2013). Scheduling for weighted flow time and energy with rejection penalty. Theoretical Computer Science, 470: 93–104

[5] Cheng T E, Wang G (2000). Single machine scheduling with learning effect considerations. Annals of Operations Research, 98(1–4): 273–290

[6] Gao F, Liu M, Wang J J, Lu Y Y (2017). No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times. International Journal of Production Research, (2): 1–9

[7] Garey M R, Johnson D S (1979). Computers and Intractability (Vol. 29).New York: WH Freeman

[8] Gonzalez T, Sahni S (1978). Preemptive scheduling of uniform processor systems. Journal of the Association for Computing Machinery, 25(1): 92–101

[9] Johnson S M (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics, 1(1): 61–68 (NRL)

[10] Koulamas C, Kyparisis G J (2007). Single-machine and two-machine flowshop scheduling with general learning functions. European Journal of Operational Research, 178(2): 402–407

[11] Kuo W H, Hsu C J, Yang D L (2012). Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect. Information Sciences, 184(1): 282–297

[12] Lee W C, Wu C C (2004). Minimizing total completion time in a two-machine flowshop with a learning effect. International Journal of Production Economics, 88(1): 85–93

[13] Lee Y C, Zomaya A Y (2010). Energy efficient resource allocation in large scale distributed systems. In: Proceedings of Distributed Computing and Applications to Business Engineering and Science (DCABES), 2010 Ninth International Symposium on IEEE. 580–583

[14] Li G, Wang X Y, Wang J B, Sun L Y (2013). Worst case analysis of flow shop scheduling problems with a time-dependent learning effect. International Journal of Production Economics, 142(1): 98–104

[15] Liu G S, Yang H D, Cheng M B (2017). A three-stage decomposition approach for energy-aware scheduling with processing-time- dependent product quality. International Journal of Production Research, 55(11): 3073–3091

[16] Liu J, Chou P H, Bagherzadeh N, Kurdahi F (2001). Power-aware scheduling under timing constraints for mission-critical embedded systems. In: Proceedings of the 38th Annual Design Automation Conference. 840–845

[17] Pei J, Cheng B, Liu X, Pardalos P M, Kong M (2017). Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time. Annals of Operations Research, (3): 1–25

[18] Pei J, Liu X, Fan W, Pardalos P M, Lu S (2017). A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega, 82: 55–69

[19] Rudek R (2011). Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect. Computers & Industrial Engineering, 61(1): 20–31

[20] Shi L, Ólafsson S (2000). Nested partitions method for global optimization. Operations Research, 48(3): 390–407

[21] Shi L, Ólafsson S, Chen Q (2001). An optimization framework for product design. Management Science, 47(12): 1681–1692

[22] Smutnicki C (1998). Some results of the worst-case analysis for flow shop scheduling. European Journal of Operational Research, 109(1): 66–87

[23] Sun L H, Cui K, Chen J H, Wang J, He X C (2013). Research on permutation flow shop scheduling problems with general position-dependent learning effects. Annals of Operations Research, 211(1): 473–480

[24] Wang J B, Wang D, Wang L Y, Lin L, Yin N, Wang W W (2009). Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times. Computers & Mathematics with Applications, 57(1): 9–16

[25] Wang J B, Wang J J (2014). Flowshop scheduling with a general exponential learning effect. Computers & Operations Research, 43: 292–308

[26] Wang J B, Xia Z Q (2005). Flow-shop scheduling with a learning effect. Journal of the Operational Research Society, 56(11): 1325–1330

[27] Wang X Y, Zhou Z, Zhang X, Ji P, Wang J B (2013). Several flow shop scheduling problems with truncated position-based learning effect. Computers & Operations Research, 40(12): 2906–2929

[28] Webb G K (1994). Integrated circuit (IC) pricing. Journal of High Technology Management Research, 5(2): 247–260

[29] Wright T P (1936). Factors affecting the cost of airplanes. Journal of the Aeronautical Sciences, 3(4): 122–128

[30] Wu C C, Lee W C (2009). A note on the total completion time problem in a permutation flowshop with a learning effect. European Journal of Operational Research, 192(1): 343–347

[31] Wu T, Shi L, Duffie N A (2010). An HNP-MP approach for the capacitated multi-item lot sizing problem with setup times. IEEE Transactions on Automation Science and Engineering, 7(3): 500–511

[32] Xu J, Lin W C, Wu J, Cheng S R, Wang Z L, Wu C C (2016). Heuristic based genetic algorithms for the re-entrant total completion time flowshop scheduling with learning consideration. International Journal of Computational Intelligence Systems, 9(6): 1082–1100

[33] Xu Z, Sun L, Gong J (2008). Worst-case analysis for flow shop scheduling with a learning effect. International Journal of Production Economics, 113(2): 748–753

RIGHTS & PERMISSIONS

The Author(s) 2018. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)