Flow shop scheduling with peak power consumption constraints

Abstract

We study scheduling as a means to address the increasing energy concerns in manufacturing enterprises. In particular, we consider a flow shop scheduling problem with a restriction on peak power consumption, in addition to the traditional time-based objectives. We investigate both mathematical programming and combinatorial approaches to this scheduling problem, and test our approaches with instances arising from the manufacturing of cast iron plates.

1 Introduction

Under the pressures of climate change, increasing energy costs, and growing energy security concerns, manufacturing enterprises have become more and more interested in reducing their energy and power consumption. Until recently, most efforts aimed at minimizing energy and power consumption in manufacturing have been focused on developing machines and equipment that are more energy and power efficient. However, several researchers have observed that in various manufacturing enterprises, energy and power consumption can also be reduced through alternate operational strategies, such as the smarter management and scheduling of machine start-up and machine idling (e.g. Dahmus and Gutowski 2004; Gutowski et al. 2005; Drake et al. 2006). In this work, we explore the use of scheduling as a means to reduce the energy and power consumption of manufacturing enterprises.

Research on using scheduling to reduce energy and power consumption in manufacturing is rather sparse. One exception is the work by Mouzon et al. (2007), who proposed several dispatching rules and a multi-objective mathematical programming formulation for scheduling jobs on a single CNC machine in a way that minimizes energy consumption and total completion time. In addition, Mouzon and Yildirim (2008) proposed a metaheuristic algorithm to minimize the total energy consumption and total tardiness on a single machine. Fang et al. (2011) provided some preliminary insights into the modeling and algorithmic challenges of shop scheduling problems with energy and power criteria.

On the other hand, there is a considerable body of literature on scheduling computer processors in a way that minimizes energy consumption. In these settings, the processors can be run at varying speeds: reducing the speed of a processor lowers power consumption, but results in longer processing time. This energy saving technique is called dynamic voltage scaling, or speed scaling, and was originally studied by Yao et al. (1995). In most of the research on speed scaling, it is assumed that the processor speed can be chosen arbitrarily from a continuous range and the associated power consumption is an exponential function of the speed. One example of work done under this assumption is that of Bansal et al. (2007), who studied the design and performance of speed scaling algorithms for scheduling jobs with deadlines to address concerns with energy and temperature. Other researchers have also considered the case where only a number of discrete speeds are available. For example, Kwon and Kim (2005) proposed a voltage allocation technique for discrete supply voltages to produce a preemptive task schedule that minimizes total energy consumption. Other power functions have also been considered in the literature (e.g. Bansal et al. 2009). For more pointers on the ever-growing literature on speed scaling, we refer the reader to the surveys by Irani and Pruhs (2005) and Albers (2010).

In the speed scaling literature, it is typically assumed that each job needs to be processed on a single processor or one of multiple parallel processors. This is to be expected, as this matches typical computing environments. However, in a typical manufacturing environment, jobs often need to be processed on multiple machines in some order; in other words, in some kind of job shop environment. As a result, much of the work on speed scaling is not directly applicable to the problems faced by manufacturing enterprises. In this work, we aim to begin to fill this gap. In particular, we consider a permutation flow shop scheduling problem with objectives based on time and power. To the best of our knowledge, our paper is one of the first in-depth studies of shop scheduling with both time and power related criteria.

Most recent research assumes that reducing the average power consumption proportionately decreases energy costs. However, peak power consumption—that is, the maximum power consumption over all time instants—also plays a key role in the energy costs of electricity-intensive manufacturing enterprises; for example, many energy providers use time-of-use (TOU) tariffs (e.g. Babu and Ashok 2008). Peak power consumption has also received some attention in the speed scaling literature, since it affects the power supply and cooling technologies in the design of computer processors. Several researchers have studied different approaches to reduce peak power consumption on a single processor or parallel processors (e.g. Felter et al. 2005; Kontorinis et al. 2009; Cochran et al. 2011).

Due to the nature of energy costs in manufacturing environments, we consider the multi-objective problem of minimizing the makespan and the peak power consumption in a permutation flow shop. In particular, we search for Pareto optimal schedules, or schedules for which no other schedule has both lower makespan and lower peak power consumption. In order to handle the bicriteria nature of this problem, we fix an upper bound on the peak power consumption, and minimize the makespan of the schedule. We consider the problem when speeds are discrete and when they are continuous. In addition, we consider flow shops with both zero and unlimited intermediate storage between machines. (In a flow shop with zero intermediate storage, a completed job cannot leave the current machine until the next machine is available.) For simplicity, in this paper, we refer to this problem as the permutation flow shop scheduling problem with peak power consumption constraints, or the PFSPP problem for short.

We consider both mathematical programming and combinatorial approaches to the PFSPP problem. Unlike most classical scheduling problems, we need to be able to keep track of which jobs are running concurrently at any time in order to take the peak power consumption into account. This presents some interesting modeling and algorithmic challenges, and some of our results may be of interest in other scheduling applications (e.g. Thörnblad et al. 2010). For the case of discrete speeds and unlimited intermediate storage, we propose two mixed integer programming formulations, inspired by existing formulations for shop scheduling problems (Manne 1960; Lasserre and Queyranne 1992). In order to strengthen these formulations, we give valid inequalities that exploit the structure of optimal schedules and the properties of concurrently running jobs. We also test the computational performance of these two formulations and the effectiveness of these valid inequalities on a set of instances based on the manufacture of cast iron plates with slots.

We also examine the PFSPP problem with two machines and zero intermediate storage. When speeds are discrete, we show that this problem is equivalent to a special case of the asymmetric traveling salesperson problem. We also consider the case when speeds are continuous and the power consumption is an exponential function of speed. In this case, we show that there exists an optimal schedule in which the total peak power consumption at any time instant is equal to exactly the fixed upper bound, and that this problem can be transformed to an equivalent asymmetric traveling salesperson problem. Moreover, if the jobs have some special features, we obtain combinatorial polynomial time algorithms for finding optimal schedules.

2 Mathematical description of the problem

As we mentioned in the introduction, we refer to the flow shop scheduling problem that we study in this paper as the permutation flow shop problem with power consumption constraints (or the PFSPP problem for short). An instance of the PFSPP problem consists of a set $\mathcal{J}=\{1,2,\dots,n\}$ of jobs and a set $\mathcal{M}=\{ 1,2,\dots ,m\}$ of machines. Each job j on machine i has a work requirement p _ij , and must be processed nonpreemptively first on machine 1, then on machine 2, and so on. There is a set of speeds $\mathcal{S}$: a job $j\in\mathcal{J}$ processed on machine $i\in\mathcal{M}$ at speed $s\in\mathcal{S}$ has an associated processing time p _ijs and power consumption q _ijs . In addition, we are given a threshold Q _max on the total power consumption at any time instant of the schedule.

Assumption 2.1

We assume that when we process a job at a higher speed, its processing time decreases, while its power consumption increases. That is, as s increases, p _ijs decreases and q _ijs increases. In addition, we assume that the power consumption associated with processing a job on a machine at a particular speed is constant from the job’s start time until but not including the job’s completion time. Finally, we assume that $\min_{s\in\mathcal{S}}\{q_{\mathit{ijs}}\}\leq Q_{\max}$ for all $i\in\mathcal{M}$ and $j\in\mathcal{J}$.

In this paper, we focus on minimizing the makespan C _max, the completion time of the last job on the last machine m. We define a feasible schedule as a schedule in which the total power consumption at any time is no more than the given threshold Q _max. Then, depending on the type of the speed set and flow shop environment, we define the following variants of the PFSPP problem.

Problem 2.2

The set of speeds set $\mathcal{S}=\{s_{1}, s_{2},\dots,s_{d}\}$ is discrete. The flow shop has unlimited intermediate storage. Each job $j\in\mathcal{J}$ on machine $i\in\mathcal{M}$ has processing time p _ijs and power consumption q _ijs when processed at speed $s\in \mathcal{S}$. Find a feasible schedule that minimizes the makespan C _max.

Instead of giving an explicit equation for power as a function of speed, we assume that the relationship between processing time, power consumption and speed can be arbitrary in Problem 2.2, as long as it satisfies Assumption 2.1. Without loss of generality, we assume that s ₁<s ₂<⋯<s _d .

We also consider a variant of Problem 2.2, in which the flow shop has two machines and zero intermediate storage.

Problem 2.3

The set of speeds $\mathcal{S}=\{s_{1}, s_{2},\dots,s_{d}\}$ is discrete. The flow shop has two machines, that is, $\mathcal{M}=\{1,2\}$, and zero intermediate storage. Each job $j\in\mathcal{J}$ on machine $i\in\mathcal{M}$ has processing time p _ijs and power consumption q _ijs when processed at speed $s\in\mathcal{S}$. Find a feasible solution that minimizes the makespan C _max.

Unlike in Problems 2.2 and 2.3, it might be the case that each job can run at an arbitrary speed within a given continuous range. It is typical to have power as an exponential function of speed (e.g. Bouzid 2005; Mudge 2001). We consider the following two machine variant of the PFSPP problem with zero intermediate storage.

Problem 2.4

The set of speeds $\mathcal{S} = [s_{\min},s_{\max}]$ is continuous. The flow shop has two machines, that is, $\mathcal{M}=\{1,2\}$, and zero intermediate storage. Each job j processed on machine i at speed $s \in\mathcal{S}$ has processing time p _ijs =p _ij /s and power consumption q _ijs =s ^α for some constant α>1. Find a feasible schedule that minimizes the makespan C _max.

3 Discrete speeds and unlimited intermediate storage: mixed integer programming formulations

A great deal of research has focused on solving the ordinary permutation flow shop scheduling problem (without power consumption considerations) with integer programming approaches. These efforts have primarily looked at two families of mixed integer programs. One is based on Manne’s (1960) formulation that uses linear ordering variables and pairs of dichotomous constraints (called the disjunctive constraints) to ensure one job is processed before another or vice versa. The other is based on Wagner’s (1959) use of the classical assignment problem to assign jobs to positions on machines. Researchers have investigated the computational performance of different mixed integer programs for the ordinary permutation flow shop scheduling problem from these two families with respect to various objectives (e.g. Stafford et al. 2005; Keha et al. 2009; Unlu and Mason 2010).

In this work, we propose two mixed integer programming formulations, inspired by the work of Manne (1960) and Wagner (1959). In particular, we follow a variant of Wagner’s formulation proposed by Lasserre and Queyranne (1992), which models the relationship between jobs and their position in a permutation. We will compare the performance of these two mixed integer programming formulations to discover some promising formulation paradigms that can subsequently be applied to solve larger scheduling problems with peak power consumption constraints.

Unlike most ordinary flow shop scheduling problems, in the PFSPP problem, we need to keep track of jobs that are running concurrently on machines at any time. For this reason, we cannot directly apply the existing mixed integer programming formulations mentioned above. In order to build upon these formulations, we use the following observation. Note that in the PFSPP problem, each job must be processed nonpreemptively with exactly one speed $s\in\mathcal{S}$ on each machine. As a result, when a job is started on a given machine, the power consumption of that machine will stay the same until this job is finished. For any time instance t, let J _t be the set of jobs being processed at t. Let $C^{L}_{t}$ $(S^{L}_{t})$ be the completion (start) time of the last job that is completed (started) before time t. Let $C^{R}_{t}$ $(S^{R}_{t})$ be the completion (start) time of the first job that is completed (started) after time t. Denote $t_{1} = \max\{C^{L}_{t}, S^{L}_{t}\}$ and $t_{2}=\min\{C^{R}_{t},S^{R}_{t}\}$. Then for any time t′ within [t ₁,t ₂), we have J _t′=J _t , which implies that the total power consumption in the flow shop is a constant between t ₁ and t ₂.

Example 3.1

Consider the following example that illustrates the above observation. At time t, there are three jobs J _t ={j,k,l} that are processed concurrently (see Fig. 1). $S^{L}_{t}$ is the start time of job k on machine g, $C^{L}_{t}$ is the completion time of job r on machine i. In this example, $S^{L}_{t}<C^{L}_{t}$, so we have $t_{1}=C^{L}_{t}$. Similarly, we have $t_{2}=C^{R}_{t}$, which is the completion time of job j on machine f. Then within [t ₁,t ₂), the total power consumption in the flow shop is constant.

Fig. 1

Gantt chart for Example 3.1

Inspired by this observation, we propose mixed integer programs with binary variables that keep track of jobs that are running concurrently on any two different machines only at job start and completion times. First, we propose a mixed integer program in Sect. 3.1 inspired by Manne (1960), which we will call the disjunctive formulation. In Sect. 3.2, we propose another mixed integer program inspired by Lasserre and Queyranne (1992), which we will call the assignment and positional formulation (or AP formulation for short). For the remainder of this section, we assume that all data are integer.

3.1 Disjunctive formulation

In this section, we propose a mixed integer program inspired by Manne’s (1960) formulation. We define the following decision variables:

• C _max is the makespan of the schedule;

• C _ij is the completion time of job j on machine i;

• S _ij is the start time of job j on machine i;

• δ _jk is equal to 1 if job j precedes job k, and 0 otherwise;

• x _ijs is equal to 1 if job j is processed on machine i with speed s, and 0 otherwise;

• u _hkij is equal to 1 if the start time of job k on machine h is less than or equal to the start time of job j on machine i (in other words, S _hk ≤S _ij ), and 0 otherwise;

• v _hkij is equal to 1 if the completion time of job k on machine h is greater than the start time of job j on machine i (in other words, C _hk >S _ij ), and 0 otherwise;

• y _hkij is equal to 1 if the start time of job j on machine i occurs during the processing of job k on machine h (in other words, S _hk ≤S _ij <C _hk ), and 0 otherwise;

• z _hksij is equal to 1 if job k is processed on machine h with speed s, and is processed while job j starts on machine i (in other words, if x _hks =1 and y _hkij =1), and 0 otherwise.

We call the binary decision variables u,v,y and z the concurrent job variables. Let M be an upper bound on the makespan of an optimal schedule. For simplicity, we let $M=\sum_{i\in\mathcal {M}}\sum_{j\in\mathcal{J}}p_{ij1}$. Problem 2.2 can be modeled as follows:

(3.1a)

(3.1b)

(3.1c)

(3.1d)

(3.1e)

(3.1f)

(3.1g)

(3.1h)

(3.1i)

(3.1j)

(3.1k)

(3.1l)

(3.1m)

(3.1n)

(3.1o)

(3.1p)

(3.1q)

(3.1r)

The objective (3.1a) and the constraints (3.1b) ensure that the makespan is equal to the completion time of the last job processed on machine m. Constraints (3.1c)–(3.1f) ensure that the completion times are consistent with a flow shop. In particular, constraints (3.1e)–(3.1f) are the disjunctive constraints between any two jobs j and k: they ensure that job j is processed before job k or vice versa. Constraints (3.1g) ensure that jobs are processed nonpreemptively. Constraints (3.1h)–(3.1m) ensure that the concurrent job variables u, v, y and z take their intended values. Constraints (3.1n) indicate that each job can be processed on any given machine with exactly one speed. Constraints (3.1o)–(3.1p) ensure that the jobs are processed in the same order on every machine. Finally, constraints (3.1q) ensure that at any time, the total power consumption across machines does not exceed the threshold Q _max.

3.2 Assignment and positional formulation

Next, we give another formulation of our problem, inspired by the formulation proposed by Lasserre and Queyranne (1992), which uses binary variables to directly assign jobs to positions in a permutation. A variant of this formulation was proposed in Fang et al. (2011). We define the following decision variables:

• C _max is the makespan of the schedule;

• C _ij is the completion time of the jth job processed on machine i (note that “jth job” refers to the jth position, not job j);

• S _ij is the start time of the jth job processed on machine i;

• x _ijks is equal to 1 if job j is the kth job processed on machine i with speed s, and 0 otherwise;

• u _hkij is equal to 1 if the start time of the kth job processed on machine h is less than or equal to the start time of the jth job processed on machine i (in other words, S _hk ≤S _ij ), and 0 otherwise;

• v _hkij is equal to 1 if the completion time of the kth job processed on machine h is greater than the start time of the jth job processed on machine i (in other words, C _hk >S _ij ), and 0 otherwise;

• y _hkij is equal to 1 if the start time of the jth job processed on machine i occurs during the processing of the kth job on machine h (in other words, S _hk ≤S _ij <C _hk ), and 0 otherwise;

• z _hlksij is equal to 1 if job l is the kth job processed on machine h with speed s, and is processed while the jth job starts on machine i (in other words, if x _hlks =1 and y _hkij =1), and 0 otherwise.

As with the disjunctive formulation, we call the decision variables u,v,y and z the concurrent job variables.

3.2.1 Lower and upper bounds for start and completion time decision variables

For the decision variables representing start and completion times, we can obtain simple lower bounds and upper bounds as follows. Let Ω _ij be the set of jobs with the smallest j values of $\{p_{ikd}: k\in\mathcal{J}\}$, and let Δ _j be the set that contains the jobs with the largest j values of $\{\sum_{i\in\mathcal {M}}p_{ik1}:k\in\mathcal{J}\}$. Then, we have the following:

(3.2)

(3.3)

Clearly, the upper bound $\overline{C}_{mn}$ for C _mn is also an upper bound for the makespan. For simplicity’s sake, we define $\overline{S}_{ij} = \overline{C}_{ij}$ and $\underline{C}_{ij} = \underline{S}_{ij}$ for all $i\in\mathcal{M}$ and j=1,…,n.

3.2.2 Basic AP formulation

Using the above lower and upper bounds, we can formulate Problem 2.2 as follows:

(3.4a)

(3.4b)

(3.4c)

(3.4d)

(3.4e)

(3.4f)

(3.4g)

(3.4h)

(3.4i)

(3.4j)

(3.4k)

(3.4l)

(3.4m)

(3.4n)

(3.4o)

(3.4p)

(3.4q)

(3.4r)

(3.4s)

The objective (3.4a) and the constraint (3.4b) ensures that the makespan of the schedule is equal to the completion time of the last job on the last machine. Constraints (3.4c)–(3.4e) ensure that the completion times are consistent with a flow shop. Constraints (3.4f) ensure that jobs are processed nonpreemptively. Constraints (3.4g)–(3.4n) ensure that the concurrent job variables u,v,y and z take their intended values. Constraints (3.4o) ensure that on each machine each job is processed with exactly one speed and one position. Constraints (3.4p) ensure that each position is assigned with exactly one job and one speed. Constraints (3.4q) ensure that the jobs are processed in the same order on each machine. Finally, constraints (3.4r) ensure that at any time, the total power consumption across machines is at most Q _max. We call the above formulation (3.4a)–(3.4s) the basic AP formulation.

3.2.3 Strengthening the basic AP formulation: concurrent job valid inequalities

Recall that the variables u, v, y, z are related to the jobs running concurrently at job start and completion times. In this subsection, we show how to strengthen the basic AP formulation by giving valid inequalities based on the definitions of these variables. We call these inequalities the concurrent job valid inequalities.

Theorem 3.2

The following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.5a)

Proof

Fix h,k,i,j. If u _hkij =0, i.e. S _hk >S _ij , then for each r=k+1,…,n, we must also have S _hr >S _ij in any feasible schedule, and so by the definition of the variables u, we have u _hrij =0. On the other hand, if u _hkij =1, the left hand side of inequality (3.5a) is at most n−k, since u _hrij for r=k+1,…,n are binary variables. Therefore, the above inequality is valid. □

Theorem 3.3

The following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.5b)

Proof

Fix h,k,i,j. If v _hkij =0, i.e. C _hk ≤S _ij , then for each r=1,2,…,k−1, we must also have C _hr ≤S _ij in any feasible schedule, and so by the definition of variables v, we have v _hrij =0. On the other hand, if v _hkij =1, the left hand side of inequality (3.5b) is at most k−1, since v _hrij for r=1,2,…,k−1 are binary variables. Therefore, the above inequality is valid. □

Theorem 3.4

The following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.5c)

Proof

Fix h,k,i,j. If y _hkij =0, then by the definition of variables z, we have z _hlksij =0 for all l and s. Now suppose y _hkij =1. From constraints (3.4p) we have $\sum_{l\in \mathcal {J}}\sum_{s\in\mathcal{S}}x_{hlks}=1$. Without loss of generality, suppose job r is assigned to position k on machine h with speed s; i.e., x _hrks =1. Then by the definition of variables z, we have z _hrksij =1 and z _hlksij =0 for any other job l≠r, and so $\sum_{l\in\mathcal{J}}\sum_{s\in\mathcal{S}}z_{hlksij} = 1$. □

Theorem 3.5

The following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.5d)

Proof

For each position j on machine i, there exists at most one position k on machine h that satisfies S _hk ≤S _ij <C _hk , since at most one job is processed in each position. □

Theorem 3.6

The following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.5e)

Proof

Fix h,k,i,j. Suppose y _hkij +y _ijhk =0, i.e., y _hkij =y _ijhk =0, or S _hk ≥C _ij or S _ij ≥C _hk . Without loss of generality, assume S _hk ≥C _ij , which implies C _hk ≥S _hk ≥C _ij ≥S _ij . Then, by definition we have u _hkij =0, u _ijhk =1, v _hkij =1, and v _ijhk =0, and so the inequality (3.5e) holds. Now suppose y _hkij +y _ijhk =1. Without loss of generality, assume y _hkij =1 and y _ijhk =0. Then we have S _hk ≤S _ij <C _hk . By definition we have u _hkij =1, u _ijhk =0, and v _hkij =v _ijhk =1, and so the inequality (3.5e) also holds. Finally, if y _hkij +y _ijhk =2, i.e., y _hkij =y _ijhk =1, or S _hk =S _ij , then by definition we have u _hkij =u _ijhk =1 and v _hkij =v _ijhk =1, and so inequality (3.5e) still holds. □

Theorem 3.7

For each $i,h\in\mathcal{M}$ and j∈{1,2,…,n}, the following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.5f)

Proof

Fix h, k, i, j. If y _hkij =1, i.e., S _hk ≤S _ij <C _hk , then we have S _h,k+1>S _ij and C _h,k−1≤S _ij , or in other words, u _h,k+1,ij =v _h,k−1,ij =0. So in this case, inequality (3.5f) holds. Otherwise, because C _h,k−1<S _h,k+1, we have that S _h,k+1≤S _ij and C _h,k−1>S _ij cannot be satisfied simultaneously, or in other words, u _h,k+1,ij +v _h,k−1,ij ≤1. So in this case as well, inequality (3.5f) holds. □

Theorem 3.8

For each $i,h\in\mathcal{M}$ and j∈{2,…,n−1}, the following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.5g)

Proof

Fix h, k, i, j. If y _hkij =1, i.e., S _hk ≤S _ij <C _hk , then we have S _hk <S _i,j+1 and C _hk >S _i,j−1. In other words, u _hki,j+1=v _hki,j−1=1, and so in this case, inequality (3.5g) holds. Otherwise, we have that either C _i,j−1≤S _hk or C _hk ≤S _i,j+1, which implies u _hki,j+1+v _hki,j−1≥1. So in this case as well, inequality (3.5g) holds. □

3.2.4 Strengthening the basic AP formulation: nondelay valid inequalities

A feasible schedule is called nondelay if no machine is idle when there exists a job that can be processed without violating the threshold Q _max on the total power consumption across all machines.

Theorem 3.9

For Problem 2.2, there always exists an optimal schedule that is nondelay.

Proof

Suppose schedule σ ₁ is an optimal schedule that is not nondelay for Problem 2.2. Let $C_{\sigma_{1}}$ be the makespan of σ ₁. Suppose machine i is idle when job j is available to be processed in schedule σ ₁. Then we process all the other jobs the same way, and process job j with the same speed as in schedule σ ₁, starting at the earliest time after C _i−1,j at which scheduling job j on machine i does not violate the peak power consumption constraints. Denote this new schedule as σ ₂ with makespan $C_{\sigma_{2}}$. If the completion time of job j on machine i in σ ₁ is not the unique value that determines the makespan, then we still have $C_{\sigma_{2}} = C_{\sigma _{1}}$. Now suppose j is the only job that attains the makespan $C_{\sigma_{1}}$ in schedule σ ₁. Then by processing job j earlier on machine i, we obtain $C_{\sigma_{2}} <C_{\sigma _{1}}$, which contradicts the optimality of schedule σ ₁. □

Based on Theorem 3.9, we can add constraints to the basic AP formulation (3.4a)–(3.4s) that require schedules to be nondelay. It is difficult to obtain such inequalities for the general PFSPP problem. However, when the flow shop has two machines, i.e., $\mathcal{M}=\{ 1,2\}$, then we have the following nondelay valid inequalities (3.6a)–(3.6e).

Theorem 3.10

Suppose $\mathcal{M} = \{1,2\}$. For each j∈{2,3,…,n}, the following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.6a)

(3.6b)

Proof

Fix j, k. If y _2k1j =1, i.e., S _2k ≤S _1j <C _2k , and v _1,j−1,2k =0, i.e., C _1,j−1≤S _2k , then because there always exists an optimal nondelay schedule, we can start the job in the jth position on machine 1 simultaneously with the job in the kth position on machine 2, i.e., S _2k =S _1j .

In other words, u _2k1j =u _1j2k =1. So in this case the inequality (3.6a) holds. Otherwise, if y _2k1j =0, because u _2k1j +u _1j2k ≥1 and v _1,j−1,2k ≥0, the inequality (3.6a) also holds.

Reversing the roles of machines 1 and 2, we similarly obtain valid inequalities (3.6b). □

Theorem 3.11

Suppose $\mathcal{M} = \{1,2\}$. The following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.6c)

Proof

Fix k. If y _1k21=1, i.e. S _1k ≤S ₂₁<C _1k , then we can start the job in the first position on machine 2 simultaneously with the job in the kth position on machine 1, that is S _1k =S ₂₁.

In other words, u _211k =1, and so inequality (3.6c) holds. □

Theorem 3.12

Suppose $\mathcal{M} = \{1,2\}$. For each j∈{2,3,…,n}, the following inequalities are valid for the mixed integer program (3.4a)–(3.4s):

(3.6d)

(3.6e)

Proof

Fix j, k. Suppose y _2k1j =1 and v _1,j−1,2k =1, i.e., S _2k ≤S _1j <C _2k and C _1,j−1>S _2k .

Then because there always exists an optimal nondelay schedule, we can process the job in the jth position immediately after the completion time of the job in the (j−1)th position on machine 1; that is, S _1j =C _1,j−1. So the inequality (3.6d) holds. Now suppose y _2k1j and v _1,j−1,2k are not both equal to 1. Then the right side is at least $\overline{S}_{1j}-\underline{C}_{1,j-1}$, and so the inequality (3.6d) still holds.

Reversing the roles of machines 1 and 2, we similarly obtain valid inequalities (3.6e). □

We call the formulation that combines the basic AP formulation with the concurrent job valid inequalities (3.5a)–(3.5g) (and the nondelay valid inequalities (3.6) when $\mathcal{M} = \{ 1,2\}$) the enhanced AP formulation.

3.3 Experimental study

3.3.1 Computational environment

In this section, we compare the performance of the different formulations presented in Sect. 3.1 and Sect. 3.2, with respect to both computation time and solution quality. We used Gurobi Optimizer 4.5 to solve the mixed integer programs on a computer with two 2.5 GHz Quad-Core AMD 2380 processors and 32 GB of RAM running the Linux operating system.

To conduct our experiments, we considered a hypothetical flow shop scheduling problem arising from the manufacture cast iron plates with slots (Fig. 2). The plates manufactured in this flow shop can have three different lengths, two different depths of milling on the surface, three different numbers of slots, and two different depths of slots. In other words, there are 3×2×3×2=36 different types of plates. There are two types of machines with different operations: face milling and profile milling. We consider two different cases: in the first case, each plate must have the two operations on one side; in the second case, each plate must have the two operations on two sides. We can view these two different cases as two different flow shop problems with 2 and 4 machines, respectively; that is, $\mathcal{M}=\{1,2\}$ or $\mathcal{M}=\{ 1,2,3,4\}$. There are five available cutting speeds on each machine; that is, d=5 and $\mathcal{S}=\{ s_{1},s_{2},s_{3},s_{4},s_{5}\}$. We also consider a special case in which we can only use each machine’s minimum and maximum speeds; that is, d=2 and $\mathcal{S}=\{s_{1},s_{2}\}$. The processing times p _ijs and power consumption values q _ijs are generated in accordance with the Machinery’s Handbook (Oberg et al. 2008). In the instances we study, the processing times p _ijs are in the interval [4,22] (in minutes), and the power consumption values q _ijs are in the interval [4,9] (in kW). For this study, we consider instances in which the number of jobs n is 8, 12, 16, or 20.

Fig. 2

Cast iron plates with slots

We generate 10 different settings for each combination of (m,n,d), by randomly sampling n jobs with replacement from the 36 job types. Let (m,n,d,k) denote the kth setting that has m machines, n jobs and d speeds. In summary, the family of settings we use in our experiment is

$$\bigl\{(2,n,2,k), (2,n,5,k), (4,n,2,k): n\in\{8,12,16,20\},\ k\in\{ 1,2,\dots ,10 \}\bigr\}. $$

For each setting (m,n,d,k), we define $\underline{Q} = \max_{i \in \mathcal{M},j \in\mathcal{J}}\{q_{ij1}\}$ and $\overline{Q} = \sum_{i \in\mathcal{M}}\max_{j \in\mathcal{J}}\{q_{ijd}\}$. Note that when $Q_{\max}<\underline{Q}$, there is no feasible schedule, and when $Q_{\max}>\overline{Q}$, all jobs can be processed concurrently at their maximum speed. We call $[\underline{Q}, \overline{Q}]$ the power consumption range for each instance, which we divide into 9 subintervals with same length. For each setting (m,n,d,k), we solve the corresponding mixed integer program using the 10 endpoints of these subintervals as the threshold Q _max on the total power consumption at any time instant. This way, for each combination of m, n and d, we will test 10 settings with 10 different peak power consumption thresholds, or 100 instances of the problem. We set a 30 minute time limit on each instance. For each instance, we provide Gurobi Optimizer with an upper bound on the optimal makespan, using the best solution obtained from the two heuristic algorithms described next.

3.3.2 Two heuristic algorithms for finding feasible schedules

For an instance (m,n,d,k) with threshold Q _max on the peak power consumption, let $s^{*}_{ij}$ be the maximum possible speed at which job j can be processed on machine i individually without violating the power consumption threshold; i.e., $s^{*}_{ij} = \max\{s\in \mathcal {S}:q_{\mathit{ijs}}\leq Q_{\max}\}$. Suppose we fix a permutation of the job set. Then one straightforward algorithm (Algorithm 3.1) for finding a feasible schedule is to process each job j on machine i at speed $s^{*}_{ij}$ without overlap—that is, with no other concurrently running jobs.

Algorithm 3.1

Maximum possible speed, fix permutation, no overlap

For example, when Algorithm 3.1 is applied to a two-machine flow shop, in which each job is processed with its maximum possible speed without overlap, the Gantt chart of the resulting schedule looks like this:

Another simple method to generate feasible solutions is to process jobs as early as possible at their minimum possible speeds, while respecting the power consumption constraints (Algorithm 3.2). As mentioned above (e.g., Example 3.1), we only need to keep track of the jobs that are running concurrently at start or completion times. Let $\widetilde{T}$ be the sorted list of all the start and completion times of jobs, and let $\widetilde{T}[i]$ be the ith component in $\widetilde{T}$.

Algorithm 3.2

Minimum possible speed, fix permutation, as early as possible

For example, suppose that the following is a Gantt chart for the schedule we obtain using Algorithm 3.2 for the first 3 jobs of a two-machine instance:

Here, $\widetilde{T}=\{t_{1},\dots, t_{7}\}$. Next, Algorithm 3.2 attempts to schedule job 4 on machine 1 at its earliest possible time t ₄. If the power consumption threshold is violated when job 4 is processed on machine 1 at time t ₄, then the algorithm tries to schedule job 4 on machine 1 at the next possible time t ₅. If the power consumption threshold is satisfied, then the algorithm schedules job 4 on machine 1 at t ₅ and updates the list of times $\widetilde{T}$.

The primary role of the two heuristic algorithms described above in our study is to quickly obtain an upper bound on the optimal makespan for use in Gurobi’s branch-and-cut procedure. Unfortunately, in our computational results, we found that these upper bounds often are quite loose, since they only consider processing the jobs at the minimum and maximum speeds available. When jobs can be processed at a variety of speeds, the schedules found by the heuristic algorithms usually do not compare well to optimal schedules.

3.3.3 Experiment 1: makespan (C _max) vs. power consumption (Q _max)

From Assumption 2.1, we know that when a job is processed at a higher speed, its processing time decreases, while its power consumption increases. Based on this assumption, one expects a significant trade-off between makespan and peak power consumption. To achieve the shortest possible makespan, jobs should be processed at their highest possible speeds simultaneously without idle time, which leads to high peak power consumption. On the other hand, if the objective is to minimize peak power consumption, jobs should be processed at their lowest speeds and the machines should be operated without overlap. Figure 3 shows an example of the relationship between makespan and power consumption for a setting with m=2,n=8, and d=2.

Fig. 3

Trade-off between makespan and peak power consumption

We also observe that the running times of all the formulations are considerably higher for instances with intermediate values of Q _max. Figure 4 shows an example of the relationship between Q _max and running time for the same setting with m=2, n=8 and d=2, using the enhanced AP formulation. This seems correct, intuitively: for extreme values of Q _max, the optimal schedule is relatively straightforward to compute, whereas for intermediate values of Q _max, the scheduling (in particular, deciding the processing speeds) is trickier.

Fig. 4

Relationship between running time and peak power consumption

As we will see in the subsequent subsections, this pattern is prevalent. Since the running times of the formulations appear to be related to the value of Q _max, we divide the power consumption range into 3 classes. For an instance with power consumption range $[\underline{Q}, \overline{Q}]$, if Q _max is less than the first quartile of $[\underline{Q}, \overline{Q}]$, then we call Q _max “low”; when Q _max is greater than the third quartile of $[\underline{Q}, \overline{Q}]$, then we call Q _max “high”; otherwise, we call Q _max “intermediate.” In the following experiments, we will analyze the performance of the mixed integer programs with respect to different classes of Q _max.

3.3.4 Experiment 2: disjunctive vs. basic AP formulation

In order to compare the performance of the different formulations, we use the following measures to assess their performance:

• The number of instances solved to optimality within the 30 minute time limit.

• The average and maximum solution time for these instances solved to optimality.

• The average and maximum speedup factor of the running time for these instances solved to optimality. For any two formulations a and b, we define the speedup factor (SF) between a and b for a given instance as the ratio between the times taken for a and b to solve the instance. We only compute a speedup factor when both formulations can solve the instances to optimality within the predetermined time limit.

• The average optimality gap at various time points within the 30 minute time limit. We define the optimality gap as the ratio of the value of the best known feasible solution to the best known lower bound. This measure lets us compare the performance of the different formulations for the instances that do not solve to optimality within the time limit.

These performance measures were also used by Keha et al. (2009) and Unlu and Mason (2010) in their study of mixed integer programming formulations for various scheduling problems.

In this experiment, we compare the performance of the disjunctive and basic AP formulations. We look at a family of instances similarly constructed to the one described in Sect. 3.3.1, except that we look at settings with m=2, n∈{4,5,6,7,8}, and d=2. We focus on these smaller instances in this experiment because as we see in Table 1, the disjunctive formulation for even moderately sized instances (e.g., n=8) fails to solve within the 30 minute time limit. Table 1 shows the average running time for the disjunctive and basic AP formulations, and Table 2 shows the average speedup factor between the disjunctive and basic AP formulations.

Table 1 Comparison of average running time between disjunctive and basic AP formulations

Table 2 Speedup factor between disjunctive and basic AP formulations

From Tables 1 and 2, we can see that the basic AP formulation runs much faster than the disjunctive formulation, especially for instances with larger numbers of jobs. Figure 5 graphically shows the average speedup factor between the disjunctive and basic AP formulations. Given these observations, we decided to devote more attention to strengthened versions of the basic AP formulation.

Fig. 5

Average speedup factors between the disjunctive and basic AP formulations

3.3.5 Experiment 3: basic AP formulation vs. enhanced AP formulation

We proposed the concurrent valid inequalities for basic AP formulation in Sect. 3.2.3, and the nondelay valid inequalities when m=2 in Sect. 3.2.4. We expect that the addition of these inequalities in the enhanced AP formulation will result in better computational results than the basic AP formulation. As mentioned in Sect. 3.3.1, we consider instances with 2 machines and 4 machines.

Table 3 displays the size of the basic and the enhanced AP formulations for an instance with m=2 and d=2. The enhanced AP formulation has the same number of variables as the basic AP formulation, but the enhanced AP formulation has more constraints and nonzeros than the basic AP formulation, since the concurrent job valid inequalities (and nondelay valid inequalities when m=2) are also included.

Table 3 Initial sizes of the basic and the enhanced AP formulations

Table 5 shows the computational results for the instances solved to optimality with low or high values of Q _max. From this table, we see that the number of instances solved in the basic AP formulation is about the same as the enhanced AP formulation, except for instances with m=4, n=12, and d=2, for which only one of the instances was solved to optimality using the basic AP formulation while 3 instances were solved using the enhanced AP formulation. We also see that the average speedup factor in many cases is less than 1, meaning that the basic AP formulation solved faster on average than the enhanced AP formulation. This observation might be explained by the low and high Q _max: in Sect. 3.3.3 we observed that the instances with low or high values of Q _max are “easy.” Given this, one might expect that the running times of these formulations for these instances are mainly based on the size of the formulations, not the scheduling decisions.

Table 4 shows the computational results for the instances with intermediate values of Q _max. From this table, we see that in most cases, the average speedup factor is larger than 1. In other words, for these instances with intermediate values of Q _max, the additional valid inequalities in the enhanced AP formulation help in reducing running times.

Table 4 Results for solved instances with intermediate Q _max

When analyzing the data in more detail, we found more evidence that the additional valid inequalities are effective in reducing running times for instances with intermediate Q _max. Table 6 shows the computational results for instances with intermediate values of Q _max in which m=2, n=8, and d=2. From Table 6, we see that for most instances, the enhanced AP formulation runs faster than the basic AP formulation (i.e. 53 out of 60). On the other hand, for instances in which the basic AP formulation is faster, we see that the average running times for both formulations are much smaller (less than 2 seconds).

These observations suggest something similar to what we observed with the data in Table 5. When the problem is easy to solve, the size of formulation is the main factor in the running time, implying that the basic AP formulation should be faster. Otherwise, when the problem is more difficult, the valid inequalities added in the enhanced AP formulation significantly reduce the running time.

Table 5 Results for solved instances with low or high Q _max

Table 6 Results for instances with intermediate values of Q _max and m=2, n=8, d=2

We also observed that the majority of instances, especially those with larger m,n, and d, did not solve within 30 minutes, even using the enhanced AP formulation. Tables 7, 8 and 9 show the optimality gap at various times for those instances with both AP formulations within the 30 minute time limit. From Tables 7, 8 and 9, we see that the valid inequalities help in reducing the optimality gap of the mixed integer program at various time points in the solution process (especially at the later times). In addition, we see that as the number of jobs increases, the solution quality decreases at any given time, since the increased number of jobs adds to the difficulty of scheduling jobs.

Table 7 Average optimality gap for instances with m=2, d=2

Table 8 Average optimality gap for instances with m=2, d=5

Table 9 Average optimality gap for instances with m=4, d=2

4 Two machines, discrete speeds, and zero intermediate storage

Recall that in Problem 2.3, we are given a discrete speed set $\mathcal{S}=\{s_{1},\dots,s_{d}\}$ and a set of two machines $\mathcal{M}=\{1,2\}$, and there is zero intermediate storage in the flow shop. We will show that this variant of the PFSPP problem can be transformed into an instance of the asymmetric traveling salesperson problem (TSP). Recall that in the asymmetric TSP, we are given a complete directed graph and arc distances, and the task is to find a shortest tour in the graph. This transformation is inspired by a similar transformation of the classic permutation flow shop problem with zero intermediate storage by Reddi and Ramamoorthy (1972).

Before we describe this transformation, we need to establish the notion of a “block” in a schedule for a flow shop with no intermediate storage. Consider the following example.

Example 4.1

In a two machine flow shop with zero intermediate storage, suppose job r, j, k, l are processed successively in a schedule. For example, consider the following Gantt chart.

Note that in this example, because there is zero intermediate storage, job k cannot leave machine 1 until job j is completed on machine 2, and so job l cannot be started on machine 1 until the completion time of job j. We can view any feasible schedule for Problem 2.3 as the combination of n+1 blocks: a block (j,k) is a subsequence such that job j is processed on machine 2, and job k is processed on machine 1. We can process each block with overlap (e.g. block (j,k) in the Gantt chart above), or without overlap (e.g. block (r,j)). Moreover, when the permutation of the jobs is fixed, we only need to minimize the total processing time of each block in order to find an optimal schedule.

For any feasible schedule, we define the following quantities. Let p(j,k) denote the minimum total processing time of block (j,k). Let p ₁(j,k) be the minimum total processing time of block (j,k) when it is processed without overlap while respecting the power consumption threshold, and let p ₂(j,k) be the minimum total processing time of block (j,k) when jobs j and k are processed with overlap while respecting the power consumption threshold. Recall that $s^{*}_{ij}$ is the maximum speed at which job j can be processed on machine i individually without violating the power consumption threshold. Then, it is straightforward to see that the following holds.

Lemma 4.2

• (a) There exists an optimal schedule for Problem 2.3 such that for each block (j,k) of jobs, we have that $p_{1}(j,k) = p_{2js^{*}_{2j}}+p_{1ks^{*}_{1k}}$ and $p_{2}(j,k) = \min\{\max\{ p_{2js_{2j}}, p_{1ks_{1k}}\}: q_{2js_{2j}}+q_{1ks_{1k}}\leq Q_{\max}, s_{2j}\in\mathcal{S}, s_{1k}\in\mathcal{S}\}$.

• (b) There exists an optimal schedule for Problem 2.3 such that for each block (j,k) of jobs, the total processing time p(j,k)=min{p ₁(j,k),p ₂(j,k)}.

Note that p(j,k) is not necessarily equal to p(k,j). Using the above lemma, we obtain the following result.

Theorem 4.3

Problem 2.3 can be viewed as an instance of the asymmetric traveling salesperson problem.

Proof

For convenience, we introduce a new job 0 with p ₁₀=p ₂₀=0, and define $p(0,j) = p_{1js^{*}_{1j}}$ and $p(j,0) = p_{2js^{*}_{2j}}$ for j=1,…,n. Denote j ₀=j _n+1=0. Then the makespan of schedule (j ₁,j ₂,…,j _n ) is equal to $\sum_{i=0}^{n}p(j_{i},j_{i+1})$. We construct a complete graph G=(V,E) in which V={0,1,…,n}. We define the distance from node j to k as D _jk =p(j,k) for j,k∈{0,…,n} such that j≠k, and D _jj =+∞ for j=0,…,n. Then Problem 2.3 is equivalent to finding the shortest tour in G with arc distances D. □

5 Two machines, continuous speeds, and zero intermediate storage

In this section we will consider Problem 2.4, in which the flow shop has two machines with zero intermediate storage, each machine can process jobs at any speed within a continuous interval, and the power consumption of a machine processing a job at speed s is s ^α for some constant α>1. Given Q _max as the threshold for peak power consumption, we define $s_{\max}=(Q_{\max })^{\frac{1}{\alpha}}$, and let the speed set $\mathcal{S}$ be the continuous interval [0,s _max]. Recall that p _ij is the work required for job j on machine i, s _ij ∈[0,s _max] is the chosen speed to process job j on machine i, and p _ij /s _ij is the processing time of job j on machine i.

5.1 Arbitrary work requirements across machines

Lemma 5.1

In any optimal schedule for Problem 2.4, if job j immediately precedes job k, then $s_{1k}^{\alpha}+s_{2j}^{\alpha }=Q_{\max}=s_{\max}^{\alpha}$. Moreover, each block (j,k) with j≠0 and k≠0 in an optimal schedule is processed with overlap, and C _2j =C _1k .

Proof

Note that at any time, the total power consumption of the two machines must be exactly Q _max; otherwise we can increase the speeds of the jobs on the two machines so that the total power consumption is Q _max, and decrease the makespan.

Consider a block (j,k) with j≠0 and k≠0 in an optimal schedule. If block (j,k) is processed without overlap in the optimal schedule, then job j and k must be processed at the maximum speed s _max. That is, the minimum total processing time for block (j,k) without overlap is $p_{1}(j,k)=\frac{p_{2j}+p_{1k}}{(Q_{\max })^{\frac{1}{\alpha}}}$.

If block (j,k) is processed with overlap in the optimal schedule, then it must be nondelay; otherwise we can process the delayed job (job k) earlier with the same speed as follows:

This way, we can decrease the makespan without violating the power consumption constraints. As a result, when block (j,k) is processed with overlap, then job j on machine 2 and job k on machine 1 must be processed at the same start time. Moreover, we also have C _2j =C _1k . Otherwise, without loss of generality, suppose that C _2j >C _1k . Then we can decrease the speed of job k and increase the speed of job j until C _2j =C _1k .

This way, the total processing time of block (j,k) decreases, and so the makespan also decreases. Therefore for any block (j,k) with overlap, we have $\frac{p_{2j}}{s_{2j}}=\frac{p_{1k}}{s_{1k}}=p_{2}(j, k)$. Because $s_{2j}^{\alpha}+s_{1k}^{\alpha}=Q_{\max}$, we obtain that $p_{2}(j, k)=\frac{(p_{1k}^{\alpha}+p_{2j}^{\alpha})^{\frac {1}{\alpha }}}{(Q_{\max})^{\frac{1}{\alpha}}}$. Since p ₁(j,k)>p ₂(j,k) for any α>1, so we have p(j,k)=p ₂(j,k). □

Define $D_{jk}=(p_{1k}^{\alpha}+p_{2j}^{\alpha})^{\frac{1}{\alpha}}$ for j,k∈{0,…,n} such that j≠k. Since $p(j,k)=\frac {D_{jk}}{(Q_{\max})^{\frac{1}{\alpha}}}$ for all j,k∈{0,…,n} such that j≠k, our problem is equivalent to finding a permutation (j ₁,…,j _n ) of the jobs that minimizes $\sum_{i=0}^{n}D_{j_{i},j_{i+1}}$. Similar to the proof in Theorem 4.3, if we interpret D _jk as the distance of the arc from node j to node k in a complete directed graph on {0,1,…,n}, and define D _jj =+∞ for j=0,…,n, then this variant of the PFSPP problem is also a special case of the asymmetric TSP.

5.2 Consistent work requirements across machines

Although the asymmetric TSP is an NP-hard problem, many of its special cases can be solved efficiently in polynomial time. One such special case is when the arc distances satisfy the so-called Demidenko conditions, which state that the matrix D∈ℝ^(n+1)×(n+1) of arc distances satisfies the following conditions: for all i,j,l∈{0,1,…,n} such that i<j<j+1<l, we have

(5.1)

(5.2)

(5.3)

(5.4)

We say that a tour on cities 0,1,…,n is pyramidal if it is of the form (0,i ₁,…,i _r ,n,j ₁,…,j _n−r−1), where i ₁<i ₂<⋯<i _r and j ₁>j ₂>⋯>j _n−r−1. Demidenko (?Dem79) showed the following for the asymmetric TSP.

Theorem 5.2

(Demidenko ?Dem79)

If D∈ℝ^(n+1)×(n+1) satisfies the Demidenko conditions, then for any tour there exists a pyramidal tour of no greater cost. Moreover, a minimum cost pyramidal tour can be determined in O(n ²) time.

Coming back to Problem 2.4, suppose the work requirement of jobs is consistent across machines: that is, for any two jobs $j,k\in\mathcal{J}$, we have that p _1j ≤p _1k implies p _2j ≤p _2k . Then we have the following theorem.

Theorem 5.3

If the work required is consistent across machines, then there exists an optimal schedule for Problem 2.4 that corresponds to a pyramidal TSP tour, and such a schedule can be found in O(n ²) time.

Proof

Fix i,j,l∈{0,1,…,n} such that i<j<j+1<l. Without loss of generality, suppose p ₁₁≤p ₁₂≤⋯≤p _1n and p ₂₁≤p ₂₂≤⋯≤p _2n . We can do this since the work is assumed to be consistent across machines. Therefore, p _1i ≤p _1j ≤p _1,j+1≤p _1l and p _2i ≤p _2j ≤p _2,j+1≤p _2l . We prove that $D_{jk}=(p_{1k}^{\alpha }+p_{ij}^{\alpha})^{\frac{1}{\alpha}}$ for j,k∈{0,1,…,n} such that j≠k and D _jj =+∞ for j=0,1,…,n satisfies the Demidenko conditions.

Conditions (5.1): Let $g(x)=(x^{\alpha}+p_{2i}^{\alpha })^{\frac {1}{\alpha}}-(x^{\alpha}+p_{2,j+1}^{\alpha})^{\frac{1}{\alpha}}$. Then it is straightforward to verify that g′(x)≥0, and so we have g(p _1,j+1)≥g(p _1j ), i.e.

$$\bigl({p_{1,j+1}^{\alpha}+p_{2i}^{\alpha}} \bigr)^{\frac{1}{\alpha }}-\bigl(p_{1,j+1}^{\alpha}+p_{2,j+1}^{\alpha} \bigr)^{\frac{1}{\alpha}}\geq \bigl(p_{1j}^{\alpha}+p_{2i}^{\alpha} \bigr)^{\frac{1}{\alpha }}-\bigl(p_{1j}^{\alpha }+p_{2,j+1}^{\alpha} \bigr)^{\frac{1}{\alpha}}. $$

This is equivalent to

Let $f(x)=(x^{\alpha}+p_{2,j+1}^{\alpha})^{\frac{1}{\alpha }}-(x^{\alpha }+p_{2j}^{\alpha})^{\frac{1}{\alpha}}$. Similarly we can prove that f′(x)≤0, and so

$$\bigl(p_{1,j+1}^{\alpha}+p_{2,j+1}^{\alpha} \bigr)^{\frac{1}{\alpha }}-\bigl(p_{1,j+1}^{\alpha}+p_{2j}^{\alpha} \bigr)^{\frac{1}{\alpha}}\geq \bigl(p_{1l}^{\alpha}+p_{2,j+1}^{\alpha} \bigr)^{\frac{1}{\alpha }}-\bigl(p_{1l}^{\alpha }+p_{2j}^{\alpha} \bigr)^{\frac{1}{\alpha}}. $$

So we have

or equivalently

$$D_{i,j+1}-D_{ij}+D_{j+1,j}-D_{j,j+1}\geq D_{j+1,l}-D_{jl}, $$

which indicates that conditions (5.1) are satisfied.

Conditions (5.2): Similar to the proof of conditions (5.1).

Conditions (5.3): Let $h(x)=(x^{\alpha}+p_{2i}^{\alpha })^{\frac {1}{\alpha}}-(x^{\alpha}+p_{2l}^{\alpha})^{\frac{1}{\alpha}}$. Then it is straightforward to verify that h′(x)≥0, so we have

$$\bigl({p_{1,j+1}^{\alpha}+p_{2i}^{\alpha}} \bigr)^{\frac{1}{\alpha }}-\bigl(p_{1,j+1}^{\alpha}+p_{2l}^{\alpha} \bigr)^{\frac{1}{\alpha}}\geq \bigl(p_{1j}^{\alpha}+p_{2i}^{\alpha} \bigr)^{\frac{1}{\alpha }}-\bigl(p_{1j}^{\alpha }+p_{2l}^{\alpha} \bigr)^{\frac{1}{\alpha}}, $$

which indicates that conditions (5.3) are satisfied.

Conditions (5.4): Similar to the proof of conditions (5.3). □

In general, it may be the case that different jobs have their own speed ranges and power functions (e.g. Bansal et al. 2009). In other words, it may be the case that each job j has a power function of the form $a_{j}s_{j}^{\alpha}+c_{j}$, where $s_{j}\in[s_{j}^{\min}, s_{j}^{\max }]\triangleq\mathcal{S}_{j}$. Under this environment, we may obtain different functions p(j,k) with respect to p _1k and p _2j for each block (j,k) in Problem 2.4. Using the Demidenko conditions, we can extend Theorem 5.3 as follows.

Theorem 5.4

For Problem 2.4, if the functions p(j,k) for all j,k∈{0,1,…,n} with j≠k are determined by a twice differentiable function g(x,y) such that p(j,k)=g(p _1k ,p _2j ) and $\frac{\partial^{2}g}{\partial x\partial y}<0$, then there must exist an optimal schedule that corresponds to a pyramidal tour.

Proof

Fix i,j,l∈{0,1,…,n} such that i<j<j+1<l. Without loss of generality, suppose p ₁₁≤p ₁₂≤⋯≤p _1n and p ₂₁≤p ₂₂≤⋯≤p _2n . Similar to the proof of Theorem 5.3, we show that the matrix D such that D _jk =p(j,k) for all j,k∈{0,1,…,n} such that j≠k satisfies the Demidenko conditions under the above assumption.

To show conditions (5.1) are satisfied, we need to prove that

Let h(x)=g(x,p _2i )−g(x,p _2,j+1). Then $\frac{\partial h}{\partial x}=\frac{\partial g(x, p_{2i})}{\partial x}-\frac {\partial g(x, p_{2,j+1})}{\partial x}$. Because $\frac{\partial^{2}g}{\partial x\partial y}<0$, we obtain that $\frac{\partial h}{\partial x}\geq0$. So

$$g(p_{1,j+1},p_{2i})-g(p_{1,j+1},p_{2,j+1}) \geq g(p_{1j},p_{2i})-g(p_{1j},p_{2,j+1}). $$

Similarly, we can also prove that

$$g(p_{1,j+1},p_{2,j+1})-g(p_{1,j+1},p_{2j}) \geq g(p_{1l},p_{2,j+1})-g(p_{1l},p_{2j}). $$

Combining the above two results, conditions (5.1) are satisfied.

Using the same arguments as in the proof of Theorem 5.3 and above, we can verify conditions (5.2), (5.3), and (5.4) similarly. □

5.3 Equal work requirements across machines

If the work required for each job is equal on each machine—that is, for any job $j\in\mathcal{J}$, we have that p _1j =p _2j =p _j —then we can further refine the results of the previous subsection. By Theorem 5.3, there exists an optimal pyramidal tour for this variant of Problem 2.4. For this variant, we claim that there must exist an optimal schedule of the form (1,3,5,…,n,…,6,4,2), assuming that p ₁≤p ₂≤⋯≤p _n .

Lemma 5.5

Consider a subsequence of an optimal schedule as follows:

If p _i ≤p _c , then we must have p _j ≤p _b .

Proof

By contradiction. Suppose in an optimal schedule σ ₁, we have p _i ≤p _c but p _j >p _b . Consider rescheduling the jobs between job i and c in reverse order as follows (i.e. i→b→a→⋯→k→j→c). Denote this new schedule as σ ₂.

Denote the makespan of schedule σ _i as $C_{\sigma_{i}}$, i=1,2. Then we have

$$C_{\sigma_{1}}-C_{\sigma_{2}}=\frac{(p_{i}^{\alpha}+p_{j}^{\alpha })^{\frac{1}{\alpha}}+(p_{c}^{\alpha}+p_{b}^{\alpha})^{\frac {1}{\alpha}} -(p_{i}^{\alpha}+p_{b}^{\alpha})^{\frac{1}{\alpha}}-(p_{c}^{\alpha }+p_{j}^{\alpha})^{\frac{1}{\alpha}}}{(Q_{\max})^{\frac{1}{\alpha}}}. $$

Similar to the proof of Theorem 5.3, we can show that $C_{\sigma _{1}}-C_{\sigma_{2}}>0$, which contradicts schedule σ ₁ being optimal. □

Lemma 5.6

For any optimal schedule, suppose that the first job processed is job i, the second is b and the last is c. Without loss of generality, if we assume that p _i ≤p _c , then there must exist an optimal schedule which satisfies p _b ≥p _c .

Proof

By contradiction. If an optimal schedule σ ₁ does not satisfy p _b ≥p _c , i.e. p _b <p _c , then we reschedule job i so that i becomes the last job in the schedule, while maintaining the ordering of all the other jobs. We denote the new schedule as σ ₂:

Similar to the proof of Theorem 5.3, it is easy to verify that

$$C_{\sigma_{1}}-C_{\sigma_{2}}=\frac{p_{c}+(p_{i}^{\alpha }+p_{b}^{\alpha })^{\frac{1}{\alpha}} -p_{b}-(p_{i}^{\alpha}+p_{c}^{\alpha})^{\frac{1}{\alpha}}}{(Q_{\max })^{\frac{1}{\alpha}}}>0, $$

and so schedule σ ₁ is not optimal. □

Theorem 5.7

Assuming that p ₁≤p ₂≤⋯≤p _n , there must exist an optimal schedule of the form (1,3,5,…,n,…,6,4,2).

Proof

For simplicity, we denote the workload of the job in jth position of an optimal schedule as p _σ(j). Without loss of generality, we assume that p _σ(1)≤p _σ(n). By Lemma 5.5, we obtain that p _σ(i)≤p _σ(n−i+1) for $i=1,\dots ,\lfloor \frac{n}{2}\rfloor$. By Lemma 5.6, we have p _σ(2)≥p _σ(n). Consider the subsequence of an optimal schedule from the second position to the nth position. By Lemma 5.5, we obtain that p _σ(i+1)≥p _σ(n−i+1) for $i=1,\dots ,\lfloor\frac{n}{2}\rfloor$. Combining the above results, we have p _σ(1)≤p _σ(n)≤p _σ(2)≤p _σ(n−1)≤p _σ(3)≤⋯ , and so there exists an optimal schedule of the form (1,3,5,…,n,…,6,4,2). □

6 Conclusions and future work

To the best of our knowledge, our paper is one of the first to consider a multi-objective flow shop scheduling problem with traditional time-based objectives (i.e. makespan) as well as energy-based objectives (i.e. peak power consumption). In particular, in this paper, we studied the permutation flow shop problem with peak power consumption constraints (the PFSPP problem). We proposed two mixed integer programming formulations and accompanying valid inequalities for the case of discrete speeds. A key feature of our formulation is variables and constraints that keep track of jobs running concurrently across machines. This may be of interest in other applications.

We investigated the computational performance of these formulations with instances arising from the manufacture of cast iron plates. Although our valid inequalities for the assignment and positional formulation resulted in better computational performance, especially for small-to-moderate sized instances, we still had difficulty obtaining optimal schedules in a reasonable amount of time for instances with large numbers of jobs and machines. One potential direction for future research is to develop stronger valid inequalities for our formulations, in the hopes of strengthening these formulations and improving their computational performance.

We also showed that our scheduling problem can be recast as an asymmetric TSP when the flow shop has two machines with zero intermediate storage. In addition, we were able to obtain stronger structural characterizations of optimal schedules and polynomial time algorithms to find these schedules when the speed set is continuous and the work requirements satisfy certain conditions.

Of course, there are many other possible directions for future research stemming from this work. For example, the computational complexity of the PFSPP problem remains open when there are two machines. It would be interesting to fully characterize which two-machine variants of our scheduling problem are NP-hard or polynomial time solvable. Since minimizing the makespan in an ordinary permutation flow shop is NP-hard when there are three or more machines (Garey et al. 1976) and the PFSPP problem can be seen as a special case of this ordinary permutation flow shop problem (by setting the peak power consumption threshold Q _max sufficiently high), the PFSPP problem is also NP-hard when there are three or more machines. Another interesting direction would be to determine when our proposed formulations have strong LP relaxations. Last but not least, it would also be interesting to consider different time or energy objectives (e.g. total weighted completion time, carbon footprint) or some other complex machine environments with peak power consumption constraints.