Two-Machine Flow Shop Scheduling Problem Under Linear Constraints

Abstract

We introduce a two-machine flow shop scheduling problem under linear constraints (2-FLC problem in short), in which the processing times of two stages of jobs are also decision variables and satisfy a system of linear constraints. The goal is to determine the processing times of each job, and to schedule the jobs to the two-machine flow shop such that the makespan, i.e., the completion time of all the jobs is minimized. This problem can find applications in various areas, such as industrial production and advertising planning. We study the computational complexity and algorithms for the 2-FLC problem. Particularly, we show that although the two-machine flow shop scheduling problem can be solved in polynomial time, the 2-FLC problem is generally NP-hard in the strong sense. Then we consider the design and analysis of algorithms on various settings of the 2-FLC problem. In particular, we propose a polynomial time algorithm for the 2-FLC problem when there is a fixed number of constraints. For the general case, we first propose a simple 2-approximation algorithm, and then design a polynomial time approximation scheme (PTAS).

This work has been supported by NSFC No. 11801589, No.11771245 and No. 11371216.

1 Introduction

This paper studies a generalization of the two-machine flow shop scheduling problem, in which the processing times of jobs are not given in advance, but can be determined by a system of linear constraints. Given a set of jobs and two machines, each job must be executed on the first machine, and then executed on the second machine, without interruption. The classical problem is to find the schedule which has minimum makespan, i.e., the completion time of the last job. It is usually denoted by $F2||C_{\max }$ [1]. In our problem, the processing times of jobs are not fixed and exogenously given, but are decision variables that satisfy a set of linear constraints. We call the problem a two-machine flow shop scheduling problem under linear constraints, and 2-FLC for short. The goal of this problem is to determine the processing times of the jobs, as well as finding the schedule that has minimum makespan among all the feasible choices.

The current work can be viewed as an extension of the existing works on the scheduling problem under linear constraints [2, 3]. In these works, several single-stage scheduling problems under linear constraints, including parallel machine scheduling [2], related machine scheduling [3] have been introduced and studied. Under this framework, some parameters of the scheduling problem, such as the processing times or machine speeds must satisfy a set of linear constraints. The scheduling problem under linear constraints can be simpler or harder than the original scheduling problem. These problems may have different computational complexities, and require different techniques in designing and analyzing algorithms. For instance, the parallel machine scheduling where the processing times satisfying linear constraints [2] can be solved in polynomial time if both the number of constraints and machines are fixed constants, whereas the parallel machine scheduling problem itself is NP-hard even when there are only two machines. These results suggest us to explore various scheduling models, and to study their complexities and design of algorithms under linear constraints. Apart from scheduling problems, these are also some other researches on various combinatorial optimization problems under linear constraints in the literature, such as bin packing problem [4] and knapsack problem [5].

Next we describe some application scenarios that motivate the study of our 2-FLC problem. We remark that the scenarios are actually the extensions of those introduced in [2, 3]. In fact, we can naturally replace the machine requirement from parallel machines to flow-shop machines in their examples.

• 1. Industrial Production Problem. Consider a problem arises in the steel industry, in which the decision maker requires certain amounts of different raw metals (say, iron, copper, aluminum, and etc.). The raw metals are obtained by extracting from several different types of steel. The extraction of each type of steel can be seen as a job. This is a typical application of flow shop scheduling problem on the industrial production (see, e.g., [6]). For example, each job should undergo wire-drawing first, and then annealing, which can be regarded as the two stages of flow-shop machines. The goal is to find a schedule of the jobs. e.g., to finish the entire production as early as possible. In practice, the processing time of each job depends on the processing quantities of steel that needs to be processed. Moreover, those quantities are usually determined by the demands of the raw metals and can be formulated as a blending problem [7, 8]. Table 1 is a concrete example.

  Let $x_i$ be the processing time of steel i to be processed in the first machine (e.g., wire-drawing), and $y_i$ be the processing time of steel i to be processed in the second machine (e.g., annealing). In the example shown in Table 1, the demand of iron is 56. If we assign $x_1 + y_1$ units of processing time on steel 1 in total, then we can produce $24(x_1 + y_1)$ unit of iron. Similarly, if we assign $x_2 + y_2$ units of processing time on steel 2 in total, then we can produce $8(x_2 + y_2)$ unit of iron. Then the requirement on the demand of iron can be represented as a linear inequality $24 (x_1+y_1) + 8(x_2+y_2) + 3 (x_3+y_4) + \cdots + 2 (x_n+y_n) \ge 56$. Moreover, the processing time of a job in the second stage always depend on the processing time and (amounts of steel) first stage. For example, if the processing time (amounts) of steel 1 the first stage is $x_1$ units, then we require exactly $x_1/2$ units of processing time on the second machine, which can be represented as a linear equality $x_1 = 2y_1$. Due to the environment of the machines, there are usually some limits on the processing times of the steels on both machines. For example, the maximum processing time of steel 1 on the first machine is 10, and the processing time of steel 1 on the second machine should be within [2, 7]. Therefore, we have constraints $x_1 \le 10$ and $5 \le y_1 \le 7$. Similarly, we can write linear constraints for the demand of other required metals and other constraints. In this problem, the decision maker needs to determine the nonnegative job processing times $x_1,\ldots ,x_n$, $y_1, \ldots , y_n$ satisfying the above linear constraints, and then assign these jobs to the two-machine flow shop machines such that the last completion time is minimized. This problem can be viewed as a minimum makespan two-machine flow shop scheduling problem, where the processing times of jobs satisfy several linear constraints.

• 2. Advertising Media Production and Planning Problem. The flow shop scheduling problem can find application in the area of media and Internet (see, e.g., [9, 10]). For example, deciding the sequences of the media production and broadcast can be regarded as two stages of the flow shop machine scheduling problem. Consider a scenario that a media production company has several potential advertisements that need to be produced and then be broadcast. Let $x_i$ be the entire production time (say, e.g., casting, filming and post production) and $y_i$ be the duration of the advertisement i. Each advertisement i must be broadcast after its production is finished, and the goal is to finish the entire broadcast of all the advertisements as early as possible. The whole process can be viewed as a two-machine flow shop scheduling problem. Furthermore, the decision maker is required to decide the production time and duration for the advertisements, that is, the processing times of the jobs. It can always be represented as several linear constraints. An example of such a problem is given in Table 2.

  In Table 2, there is a budget of the production of all advertisements. Each unit production time of advertisement 1 costs 100, each unit production time of advertisement 2 costs 200, and so forth. The total budget constraint is no more than 10000, and hence can be represented as $100x_1 + 200 x_2 + \cdots + 150 x_n \le 10000$. Moreover, the company will gain revenue $2000y_1$ for $y_1$ units of broadcasting time of advertisement 1. The company requires a total revenue at least 15000, which can be represented as $1000x_1 + 2000 x_2 + \cdots + 1500 x_n \ge 150000$. The production time always depending on the duration (broadcast time) of the advertisement. For example, each unit of broadcast time of advertisement 1 requires at least 10 units of production time, which can be represented as $x_1 \ge 10 y_1$. Similar to the first example, we can formulate the other constraints as several linear constraints. The above-described problem can be naturally formulated as a two-machine flow shop scheduling problem scheduling problem in which the processing times (running times of the advertisements) are determined by a system of linear constraints.

Table 1. Example for the industrial production problem

Table 2. Example for the advertising media production and planning problem

In this paper, we study the computational complexity and algorithms for the 2-FLC problem. First, we show that the problem is generally NP-hard in the strong sense. It is well-known that the original two-machine flow shop scheduling problem can be solved in $O(n\log n)$ time by Johnson’s rule [11], where n is the number of jobs. This result suggests that the 2-FLC problem with arbitrary number of constraints has a very different complexity from the original two-machine flow shop scheduling problem. Then we consider the design of algorithms on various settings of the 2-FLC problem. In particular, we design a polynomial time algorithm for the 2-FLC problem when there is a fixed number of constraints. For the general case, we first propose a simple 2-approximation algorithm, and then design a polynomial time approximation scheme (PTAS).

The remainder of this paper is organized as follows: In Sect. 2, we give a formal definition of the 2-FLC problem studied in this paper, and briefly review some related literature. In Sect. 3, we study the computational complexity of the 2-FLC problem. In Sect. 4, we discuss the case with a fixed number of constraints. In Sect. 5, we study the approximation algorithm for the general case. We provide some concluding remarks in Sect. 6.

2 Problem Description

In this paper, we consider the following the two-machine flow shop scheduling problem under linear constraints (2-FLC) problem stated below:

Definition 1

There are n jobs and two flow-shop machines. Each job has to be processed on the first machine and then on the second machine without interruption. The processing times of job i on the first machine and the second machine are $x_i$ and $y_i$ respectively, which are determined by k linear constraints. The goal of the two-machine flow shop scheduling under linear constraints (2-FLC) problem is to determine the processing times of the jobs such that they satisfy the linear constraints and to schedule the jobs to the two flow-shop machines such that the makespan is minimized.

Let $A, C\in \mathbb {R}^{k\times n}$, $\varvec{b} \in \mathbb {R}^{k\times 1}$, the processing times $\varvec{x} = \{x_1, ..., x_n\}$, $\varvec{y} = \{y_1, ..., y_n\}$ should be feasible solutions to $A\varvec{x} + C\varvec{y} \ge \varvec{b}$, $\varvec{x}, \varvec{y}\ge 0$. It is well-known that the two-machine flow shop scheduling problem $F2||C_{\max }$ has an optimal schedule which is a permutation schedule (see, e.g., [9]), i.e., the orders of jobs in both machines are identical. Therefore, we can denote a schedule of our problem as $\sigma = \{\sigma (1), ..., \sigma (n)\}$, where $\sigma (i)$ indicates the job that is assigned on position i in the schedule. The makespan $C_{\max }$ of a schedule is thus the completion time of job $\sigma (n)$ on the second machine.

Here we give a brief literature review on the flow shop scheduling and related problems. Flow shop scheduling is one of the three basic models (open shop, flow shop, job shop) of multi-stage scheduling problems. The flow shop scheduling which minimizes the makespan is usually denoted by $Fm||C_{\max }$, where m is the number of machines. Garey et al. proved that $Fm||C_{\max }$ is strongly NP-hard for $m \ge 3$ [12], and Hall proposed a PTAS algorithm for $Fm||_{\max }$ [13]. Particularly, the two-machine flow shop scheduling problem $F2||C_{\max }$ can be solved by Johnson’s algorithm in $O(n\log n)$ time [11]. If all the jobs are processed in the same order, then we call this schedule a permutation schedule. It has been shown in [14] that $F2||C_{max}$ or $F3||C_{max}$ has an optimal permutation schedule.

3 Computational Complexity of 2-FLC Problem

We first study the computation complexity of 2-FLC problem. We show that this problem is NP-hard in the strong sense, even though the original $F2||C_{\max }$ problem can be solved in polynomial time by Johnson’s algorithm.

Theorem 1

The 2-FLC problem with two machines is NP-hard in the strong sense.

Proof

We reduce the Exact Cover by 3-Sets problem (X3C) to the 2-FLC problem. Given a ground set S with $|S| = 3n$ ($n\ge 1$) and a collection $\mathcal {C}$ of 3-element subsets of S. The X3C problem is to decide if there exists a subset $\mathcal {C'}$ of $\mathcal {C}$ with size n, in which every element of S occurs in $\mathcal {C'}$ exactly once. Let $m = |\mathcal {C}|$ be the total number of subsets and assume that $m>n$ without loss of any generality. We construct an instance of 2-FLC with $m + 1$ jobs. Each subset $S_i\in \mathcal {C}$ is associated with a job i that has processing times $x_i$ and $y_i$ in the two stages, respectively. The remaining job ${m+1}$ has processing times $x_{m+1} = n$ in the first stage and $y_{m+1} = m - n$ in the second stage. The processing times are determined by the following linear constraints:

$$\begin{aligned}&\sum _{i:j\in S_i}y_i = 1 \qquad \qquad \qquad \quad \forall ~j \in S \end{aligned}$$

(1a)

$$\begin{aligned}&x_j = 1 - y_j \qquad \qquad \qquad \qquad \forall ~i = 1, \ldots , m \end{aligned}$$

(1b)

$$\begin{aligned}&x_{m+1} = n,~y_{m+1} = m - n \\&\varvec{x}, \varvec{y} \ge 0. \nonumber \end{aligned}$$

(1c)

We show that the instance for X3C is YES if and only if there exists a schedule of 2-FLC in which the processing times are feasible to (1) and has makepan at most m.

First, suppose that theres exist an exact cover $C'$ of S. Let $x_i = 0$, $y_i = 1$ if $S_i \in C'$ and $x_i = 1$, $y_i = 0$ otherwise, and $x_{m+1} = n, y_{m+1} = m - n$ . Since $C'$ is an exact cover, it can be seen that the linear constraints (1) are satisfied. By Johnson’s rule, the jobs correspond to $S_i \in C'$ are scheduled first, then the job ${m + 1}$, and last the jobs correspond to $S_i \not \in C'$. Note that the number of subsets in every exact cover is n, therefore the makespan of the schedule is exactly $n + (m - n) = m$.

Now we prove the opposite direction. Note that the job ${m+1}$ has total processing time $n + (m - n) = m$, hence the makespan of this schedule is exactly m. The constraints in (1b) guarantees that all the $x_i$s and $y_i$s are binary, as otherwise the makespan of the schedule must be more than m. To see this, if there are some job k which has processing time $x_k \ge y_k >0$ (the case with $0< x_k < y_k$ is analogous), then job k must be assigned after job $m+1$ by Johnson’s rule, which leads to a schedule with makespan at least $n + (m-n) + y_k > m$. This contradicts to the condition that the schedule has makespan at most m. Denote $J'$ as the jobs having processing time $x_i = 0$, $y_i = 1$ and $\bar{J}$ as the remaining jobs, that is, the jobs have processing time $x_i = 1$, $x_i = 0$. Again, by Johnson’s rule and the makespan is m, it can be seen that there is exactly n jobs in $J'$. By (1a), the subsets in $\mathcal {C}$ corresponds to $J'$ constitute an exact cover of S.$\Box$

4 Fixed Number of Constraints

In this section, we study the case when the number of constraints is fixed.

Lemma 1

The 2-FLC problem has an optimal solution, in which each machine has at most k jobs with nonzero processing time.

Proof

We first show that given any optimal solution to the 2-FLC problem, we can construct an optimal solution that at most k jobs have nonzero processing time in the second machine. Now we fix the permutation of jobs in an optimal solution. Note that the jobs have same orders in both machines. To simplicity of notation, we denote the order of the jobs as $1, \ldots , n$. We can construct the following linear program:

$$\begin{aligned} \min&\;\;\;\;t\end{aligned}$$

(2a)

$$\begin{aligned} \mathrm {s.t.}&\sum ^{l}_{i = 1} x_i + \sum ^{n}_{i = l} y_i\le t \qquad \;\;\;\; \forall ~l = 1, \ldots , n\end{aligned}$$

(2b)

$$\begin{aligned}&\sum ^{n}_{i = 1}a_{ji}x_i + c_{ji}y_i \ge b_j \qquad \forall ~j = 1, \ldots , k \\&t, x_i, y_i \ge 0 \qquad \qquad \qquad \,\,\, \forall ~i = 1, \ldots , n. \nonumber \end{aligned}$$

(2c)

It can be seen that any optimal solution to (2) is also optimal to the 2-FLC problem. To see this, let $(\varvec{x}^{*}, \varvec{y}^{*})$ be the processing times of the optimal solution to the 2-FLC problem. Then by the $(\varvec{x}, \varvec{y})$ is the optimal solution to (2), we have $t = \max _{l = 1, ..., n}\left\{ \sum ^{l}_{i = 1} x_i + \sum ^{n}_{i = l} y_i\right\} \ge \left\{ \sum ^{l}_{i = 1} x_i^{*} + \sum ^{n}_{i = l} y_i^{*}\right\} = C_{\max }^{*}$, where $C_{\max }^{*}$ is the optimal makespan to the 2-FLC problem.

Introducing slack variables to (2b), we obtain a system of n constraints:

$$\begin{aligned} \sum ^{l}_{i = 1} x_i + \sum ^{n}_{i = l} y_i + z_i = t \;\;\;\; \forall ~l = 1, \ldots , n. \end{aligned}$$

(3)

Applying Gaussian elimination to (3), we obtain

$$\begin{aligned} x_1&= t - \sum ^{n}_{i=1}y_i - z_1 \\ x_i&= y_{i-1} + z_{i-1} - z_{i} \;\;\;\; \forall ~i = 2, \ldots , n . \nonumber \end{aligned}$$

(4)

Therefore, (2a) is equivalent to the following linear program:

$$\begin{aligned} \min \;\;&\;\;\;t \end{aligned}$$

(5a)

$$\begin{aligned} \mathrm {s.t.}&\;\;x_1 +z_1 = t - \sum ^{n}_{i=1}y_i \end{aligned}$$

(5b)

$$\begin{aligned}&\;\; x_i + z_i = y_{i-1} + z_{i-1} \;\;\;\; \forall ~i = 2, \ldots , n \end{aligned}$$

(5c)

$$\begin{aligned}&\sum ^{n}_{i = 1}a_{ji}x_i + c_{ji}y_i \ge b_j \quad \;\; \forall ~j = 1, \ldots , k \\&\;\;t, x_i, y_i,z_i \ge 0 \qquad \qquad \; \forall ~i = 1, \ldots , n, \nonumber \end{aligned}$$

(5d)

Now we find the optimal basic feasible solution to (5), which is also an optimal solution to the 2-FLC problem. Note that there are at most $n+k$ variables among $x_i$, $y_i$, $z_i$, and t can have nonzero processing time. If $t = 0$, then all $x_i$s and $y_i$s are zero and the lemma is proved. Therefore, we assume that $t>0$ and thus at most $n+k-1$ of $x_i$, $y_i$, and $z_i$ have nonzero processing time. Let $S = \{i \in \{2,..., n\}~|~x_i + z_i > 0\}$ be the subset of indices that with $x_i + z_i$ is positive. If $|S|=n-1$, then at most k of the $y_i$s have nonzero processing times, since the total number of remaining variables which can have nonzero processing times it at most $n+k-1-(n-1) = k$. Otherwise, $|S| < n-1$ and there exists some i such that $x_i+z_i = 0$. Note that by constraint (5c), the corresponding $y_{i-1} = z_{i-1} = 0$. Now we fix the processing times of all those $x_i$, $z_i$ and $y_{i-1}$ to be zero, and consider the linear program without these variables:

$$\begin{aligned} \min \;\; \;\;\;t \end{aligned}$$

(6a)

$$\begin{aligned} \mathrm {s.t.}&\;\;x_1 +z_1 = t - \sum _{i \in S}y_{i-1} \end{aligned}$$

(6b)

$$\begin{aligned}&\;\; x_i + z_i = y_{i-1} + z_{i-1} \;\;\;\; \qquad \qquad \qquad \forall ~i \in S \end{aligned}$$

(6c)

$$\begin{aligned}&\sum _{i \in \{1\}\cup S}a_{ji}x_i + \sum _{i \in S}c_{j,i-1}y_{i-1} \ge b_j \qquad \forall ~j = 1, \ldots , k \\&\;\;t, x_1, z_1, x_i, y_{i-1}, z_i \ge 0 \qquad \qquad \qquad \;\; \forall ~i \in S. \nonumber \end{aligned}$$

(6d)

Note that the optimal solution to (5) is feasible to (6), hence the optimal solution to (6) is still optimal to 2-FLC. We repeat the above procedure, that is, find an optimal basic feasible solution to (6), which has at most $|S| + k$ variables with nonzero processing time. If at some point $x_i + z_i$ is strictly greater than zero for all $i\in S$, then we obtain an optimal basic feasible solution in which at most $|S| + k - |S| = k$ of the $y_i$s have nonzero processing times; otherwise we can reduce the size of |S| and find the optimal basic feasible solution to the reduced linear program similar to (6), and repeat the above procedure. It can be observed that the size of S is strictly decreasing. Therefore if the procedure continues, we must have $|S| \le k$ at some point. In that case, we obtain an optimal basic feasible solution which has at most k of the $x_i + z_i$s have nonzero processing times (note that the $x_i + z_i$ for all $i\not \in S$ have been fixed to be zero before), and so for the $x_i$s and $y_i$s. Therefore, there exists an optimal solution that the second machine must have at most k nonzero processing time jobs. Fixed the processing times on the second machine and applied the same method on the first machine, we obtain a solution that each machine has at most k nonzero processing time jobs.

   $\square$

Based on Lemma 1, we can propose a polynomial time algorithm for the 2-FLC problem when the number of constraints is a fixed number of constraints. We summarize the algorithm as Algorithm 1 and Theorem 2.

Theorem 2

The 2-FLC problem when the number of constraints is fixed has a polynomial time algorithm with complexity $O(n^{k+3}L)$.

The proofs of the subsequent lemmas/theorems will be provided in Appendix.

5 General Case: Approximation Algorithms

First we propose a simple 2-approximation algorithm for the problem. We solve the linear program with minimum total progressing time subject to $Ax = b$ to obtain the processing times $\varvec{x}$, $\varvec{y}$. Then we assign the jobs with processing times $\varvec{x}$, $\varvec{y}$ by Johnson’s rule.

Theorem 3

There is a 2-approximation algorithm for the 2-FLC problem.

Now we propose a PTAS for the problem. First, we run the 2-approximation algorithm and obtain a value $C_{\max }$. By Theorem 1, $C_{\max }/2$ and $C_{\max }$ are lower bound and upper bound of the optimal makespan of the 2-FLC problem, respectively. We denote $LB = C_{\max }/2$ and $UB = C_{\max }$.

Given $\epsilon > 0$, we denote the job sets (with respect to $\varvec{x}$ and $\varvec{y}$) as follow:

$$\begin{aligned} J_1 = \{i \in J~|~x_i \le y_i\}, \quad&L_1 = \{i \in J~|~x_i \le y_i,~y_i> \epsilon C^*_{\max }(\varvec{x}, \varvec{y})\}, \nonumber \\ J_2 = \{i \in J~|~x_i \ge y_i\}, \quad&L_2 = \{i \in J~|~x_i \ge y_i,~x_i > \epsilon C^*_{\max }(\varvec{x}, \varvec{y})\}, \end{aligned}$$

(8)

where $C^*_{\max }(\varvec{x}, \varvec{y})$ is the makespan of optimal schedule of $F2||C_{\max }$ with processing time $\varvec{x}$ and $\varvec{y}$. Note that we have the sizes of $L_1$ and $L_2$ are $|L_1| \le 1/\epsilon$ and $|L_2| \le 1/\epsilon$ as otherwise we have $\sum _{i=1}^{n}x_i > C^*_{\max }(\varvec{x}, \varvec{y}) \ge C^*_{\max }$ or $\sum _{i=1}^{n}y_i >C^*_{\max }(\varvec{x}, \varvec{y}) \ge C^*_{\max }$, which leads to a contradiction. The algorithm first guesses the value of the optimal makespan, then guesses the set $L_1$ and $L_2$ in an optimal solution (w.r.t. $\varvec{x^*}$ and $\varvec{y^*}$), as well as enumerating all the possible permutations of these jobs. During each guess, we obtain the values of the processing times of jobs by checking the feasibility of a specific linear program. The jobs are then scheduled by the Johnson’s rule. The algorithm finally returns the best schedule among all these iterations. We summarize the details as Algorithm 2.

To establish the approximation performance result of Algorithm 2, we first state a property of a specified schedule in the classical two-machine flow shop scheduling problem $F2||C_{\max }$, which has makespan at most $1+\epsilon$ of the optimal solution to $F2||C_{\max }$ and allows us to design a PTAS for the 2-FLC problem. Fixed any processing times $\varvec{x}$ and $\varvec{y}$ for the jobs, $J_1$, $J_2$, $L_1$, $L_2$, $C^*_{\max }(\varvec{x}, \varvec{y})$ are defined as (8), $S_{1} = J_1 \setminus L_{1} = \{i \in J~|~x_i \le y_i,~y_i \le \epsilon C^*_{\max }(\varvec{x}, \varvec{y})\}$ and $S_{2} = J_2 \setminus L_{2} = \{i \in J~|~x_i \ge y_i,~x_i \le \epsilon C^*_{\max }(\varvec{x}, \varvec{y})\}$. The lemma is described as below.

Lemma 2

Let $C'_{\max }(\varvec{x},\varvec{y})$ be the makespan of schedule obtained by assigning the jobs in the order $S_{1}$, $L_{1}$, $L_{2}$, $S_{2}$ (identical for both machines), where the jobs in $L_{1}$ and $L_{2}$ are scheduled according to Johnson’s rule, $S_{1}$ and $S_{2}$ are scheduled arbitrarily. Then, $C'_{\max }(\varvec{x},\varvec{y}) \le (1+\epsilon )C^*_{\max }(\varvec{x}, \varvec{y})$.

Based on this lemma, we have the following result.

Theorem 4

Algorithm 2 is a PTAS for the 2-FLC problem.

6 Conclusions

We study the two-machine flow shop scheduling problem under linear constraints in this paper. The problem is NP-hard in the strong sense, and we propose several optimal or approximation algorithms for various settings of it. An immediate research question is to study the FLC problem where the number of machines is more than 2. Furthermore, it is also interesting to consider the shop scheduling problem under linear constraints where the machine environment is open shop or job shop, and the shop scheduling problem with additional constraints, such as the no-wait case.