On Scheduling Two-Stage Jobs on Multiple Two-Stage Flowshops
Guangwei Wu Jianer Chen Jianxin Wang
cs.DS



theoremTheorem[section]
lemma[theorem]Lemma
corollary[theorem]Corollary
proposition[theorem]Proposition






#14pt
  1pt#11pt
2pt










On Scheduling Two-Stage Jobs

   on Multiple Two-Stage FlowshopsThis work is supported in part by the National
   Natural Science Foundation of China under grants 61232001, 61472449, 61420106009, and 71221061.
    
Guangwei Wu^
         Jianer Chen^
         Jianxin Wang^[Corresponding author,
        email: jxwang@csu.edu.cn.]



^School of Information Science and Engineering

    Central South University

    ChangSha, Hunan 410083, P.R. China



^College of Computer and Information Engineering

    Central South University of Forestry and Technology

    ChangSha, Hunan 410004, P.R. China



^School of Computer Science & Education Software
 
     Guangzhou University

     Guangzhou, Guangdong 510006, China



^Department of Computer Science and Engineering 

    Texas A&M University

    College Station,  TX 77843, USA

    
=================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




Motivated by the current research in data centers and cloud computing, we study the problem of
scheduling a set of two-stage jobs on multiple two-stage flowshops. A new formulation for
configurations of such scheduling is proposed, which leads directly to improvements to the
complexity of scheduling algorithms for the problem. Motivated by the observation that the
costs of the two stages can be significantly different, we present deeper study on the
structures of the problem that leads to a new approach to designing scheduling algorithms for
the problem. With more thorough analysis, we show that the new approach gives very significant
improved scheduling algorithms for the problem when the costs of the two stages are different
significantly. Improved approximation algorithms for the problem are also presented.




keywords.
scheduling, two-stage flowshop, pseudo-polynomial time algorithm, approximation algorithm,
cloud computing





§ INTRODUCTION


Scheduling is concerned with the problems of optimally allocating available resources to
process a given set of jobs. In particular, scheduling jobs on multiple machines has received
extensive study in the past four decades, in computer science, operations research, and
system sciences <cit.>.

In this paper, we study the scheduling problems for two-stage jobs on multiple two-stage flowshops.
A machine M is a two-stage flowshop (or simply a flowshop) if it consists of an
R-processor M_R and a T-processor M_T that can run in parallel. A job J is
a two-stage job (or simply a job) if it consists of an R-operation R_J and
a T-operation T_J such that the T-operation T_J cannot start on the T-processor
M_T of a flowshop M until the R-operation R_J has been completed on the R-processor M_R
of the same flowshop M. When a two-stage job J is assigned to a two-stage flowshop
M, the flowshop M will first use its R-processor M_R to process the R-operation R_J of
J, then, at proper time after M_R completes the processing of R_J, use its T-processor M_T
to process the T-operation T_J of J. Thus, when we consider scheduling two-stage jobs on
multiple two-stage flowshops, we need to decide an assignment that assigns each job to a flowshop
and, for each flowshop, the execution orders of the R- and T-operations of the jobs that are
assigned to that flowshop.

Thus, the scheduling model studied in the current paper is as follows:

Given a set of n two-stage jobs and a set of m two-stage flowshops, construct a schedule of the
jobs on the flowshops that minimizes the makespan, i.e., the total time that elapses from the beginning
to the end for completing the execution of all the jobs.




 §.§ Motivations

Our scheduling model was motivated by the current research in data centers and cloud computing. A data center is
a facility used to house servers, storage systems, and network devices, etc. <cit.>. Today's data centers
contain hundreds of thousands of servers. Typical cloud computing providers rent infrastructures (IaaS), platforms
(PaaS), and softwares (SaaS) as services, while keeping the softwares and data stored in the servers in data centers.
Recently, a cloud paradigm called TransCom  <cit.>, based on the principle of transparent computing
<cit.>, has been proposed. This paradigm considers not only application softwares and data but also
traditional system softwares such as operation systems as resources. As a consequence, client devices in such a system
can be very light and significantly diversified, as long as they contain a small TransCom kernel and a new-generation
input/output system UEFI <cit.>. Traditional operation systems, application softwares, and data are stored as
resources in the cloud. Clients dynamically request these resources selected by users, and the cloud sends  the
resources to the clients via networks. The infrastructure of such a system is shown in Figure <ref>.


In such a system, a significant amount of resources requested by clients are executable codes of system/application
softwares, which in general are large by size and commonly used by many users. Because the main memory of servers
is limited, these codes are in general stored in secondary memory such as hard disks that can be accessed by the
servers. Therefore, when a server receives a request from a client for a specific code, it will have to first read
the code from the secondary memory into the main memory, then send the code to the client via networks. As a result,
a request from a client can be divided into two operations, one is a disk-read operation R that reads the requested
code/data from a secondary memory into the main memory, and the other is a network-transmission operation T that sends
the code/data via the network to the requesting client. It is also natural to require that the network-transmission
operation do not start until the requested code/data has been brought into the main memory.[One may argue
that such a disk-read/network-transmission process can be done in pipeline: in this case, we can simply regard each
data block of the requested data as a “inseparable” job. Now for each job network-transmission must wait until
the disk-read is completed, and the job becomes two-stage. See Section 6 for more discussions.] Therefore, in such
a system, the data requests become two-stage jobs, consisting of the disk-read and the network-transmission
operations, while each server becomes a two-stage flowshop, consisting of the disk-read and network-transmission
processors (note that the disk-read and network-transmission can run in parallel in the same server), and
scheduling a given set of such requests in a multiple-server center becomes an instance of the scheduling model
we have formulated. We should remark that the time for disk-read and the time for network-transmission in a typical
server are in general comparable, and, due to the impact of cache systems, they need not to have a linear relation
<cit.>. Therefore, neither can be simply ignored if we want to maintain good performance for the cloud system.



 §.§ Previous related work


Multiple machine scheduling and flowshop scheduling have been extensively studied. We first discuss the relationship
between our scheduling model and other related scheduling models studied in the literature. Then we review the
known results specifically on our scheduling model.

First of all, the classical Makespan problem can be regarded as scheduling one-stage jobs on multiple
one-stage machines <cit.>. On the other hand, scheduling two-stage jobs on a single two-stage flowshop
is the classical two-stage flowshop problem <cit.>.

Other scheduling models that deal with multiple-stage jobs include various “hybrid” shop scheduling problems,
such as the hybrid flow shop scheduling problem <cit.> and the hybrid/flexible job shop
scheduling problem <cit.>. The hybrid shop scheduling problems allow multiple machines for a stage
such that the execution of a stage operation of a job can be assigned to any machine for that stage. However,
in general there is no specific bonding requirement for the machine that executes an operation for a stage of a
job and the machine that executes the operation for the previous stage of the same job. This makes a major
difference between this model and our model: our model requires that once a job is assigned to a machine,
then the R-operation and the T-operation of the job must be executed by the R-processor and the
T-processor, respectively, of the same machine.

Indeed, in the hybrid/flexible job shop scheduling model, if each job is given a set of alternative routes,
where each route is a sequence of specific flowshops, one for a stage of the job, then our scheduling problem
can be formulated as a restricted version of this very general version of the hybrid job shop scheduling problem.
However, to the authors' knowledge, this general version of the hybrid job shop scheduling problem has not
been systematically studied. Moreover, since our scheduling problem has a strong constraint that the two
stage operations of the same job be bonded to the same flowshop, a general solution to the general version of the
hybrid job shop scheduling problem will probably be not efficient and effective enough for our scheduling problem.

Another model that deals with multiple-stage jobs is that of scheduling jobs with setup costs <cit.>,
where a job can also be regarded as a two-stage job in which one stage is the “setup” stage, and the other
stage is the “regular” processing stage. However, in the model of scheduling jobs with setup costs assumes
one-stage machines — a machine under such a model cannot run the setup stage for one job and the regular
processing stage for another job in parallel. On the other hand, a two-stage flowshop M under our model can
have its R-processor and T-processor run in parallel. Thus, when the R-processor of M is processing the
R-operation for a job, the T-processor of M can process the T-operation for another job at the same
time. Finally, our model is different from that of multi-processor job scheduling problem <cit.>,
where a job may require more than one processors and it holds all the requested processors during its execution.
On the other hand, a two-stage job under our current model requires the two requested processors to run one
after the other, and when one of the processors of a flowshop is running for the job, the other processor of the
flowshop may be used for processing other jobs.

Except some research directly related to specific applications, the problem of scheduling two-stage jobs on
multiple two-stage flowshops had not been studied thoroughly until very recently. He, Kusiak, and Artiba
<cit.> seem the first group who studied the problem, motivated by applications in glass manufacturing,
and proposed a heuristic algorithm. Vairaktarakis and Elhafsi <cit.> also considered the problem in
their study on the hybrid multi-stage flowshop problem. In particular, a pseudo-polynomial time algorithm was
proposed in <cit.> for scheduling two-stage jobs on two two-stage flowshops. Zhang and van de Velde
<cit.> presented constant ratio approximation algorithms for scheduling two-stage jobs on two and
three two-stage flowshops. Very recently,[In fact, our research is independent of <cit.>: we
became aware of the result of <cit.> only after the current paper had been completed.] following a formulation
similar to that of <cit.>, Dong et al. <cit.> proposed a pseudo-polynomial time algorithm
for scheduling two-stage jobs on m two-stage flowshops for a fixed constant m, and developed a fully
polynomial-time approximation scheme for the problem based on the pseudo-polynomial time algorithm. We also
note that approximation algorithms for k-stage jobs on multiple k-stage flowshops for general k have be
studied recently <cit.>.



 §.§ Our main results


Our research in the current paper was motivated by our current project on data center and cloud computing,
as described in the previous section. Therefore, we are looking for more efficient algorithms for scheduling
two-stage jobs on multiple two-stage flowshops, which not only improve previous best theoretical complexity
bound, but also run much faster in practice.

First of all, we propose a new formulation to describe configurations for schedules of two-stage jobs on multiple
two-stage flowshops. Our formulation is very different from those studied in the literature <cit.>.
We show that dynamic programming based on our formulation directly leads to improvements on the complexity of
algorithms for scheduling two-stage jobs on multiple two-stage flowshops, in terms of both theoretical bound
and practical performance.

Our further study on the problem was motivated by the observation that in many cases in practice, the 
execution times for the two stages can differ very significantly. We present deeper study on the structures 
of the problem that leads to a more carefully designed algorithm. With more thorough analysis, we are able 
to show that the new approach will give a very significantly improved scheduling algorithm for the problem 
when the costs of the two stages are significantly different. Improved approximation algorithms for the 
problem are also presented.

The paper is organized as follows. Formal definitions and some preliminary results related to the
problem are given in Section 2. The new scheduling formulation for the problem is proposed and
improved pseudo-polynomial time exact algorithms based on the new formulation are presented in
Section 3. Section 4 is devoted to faster algorithms for the case when the execution times of the
two stages are significantly different. An improved approximation algorithm for the problem is given
in Section 5 for the problem when the number of flowshops is bounded by a constant. We conclude the
paper in Section 6 with remarks and suggested future research.




§ SINGLE FLOWSHOP SCHEDULING AND DUAL SCHEDULING

For n two-stage jobs J_1, …, J_n to be processed in a system {M_1, …, M_m} of m identical
two-stage flowshops, we make the following “standard” assumptions (variations and extensions of this model will
be discussed in Section 6
):

 
  * each job consists of an R-operation and a T-operation;

 


 
  * each flowshop has an R-processor and a T-processor that can run in parallel and can process the
   R-operations and the T-operations, respectively, of the jobs;

 


 
  * the R-operation and T-operation of a job must be executed in the R-processor and T-processor,
     respectively, of the same flowshop, in such a way that the T-operation cannot start unless the
     R-operation is completed;

 


 
  * there is no precedence constraints among the jobs; and

 


 
  * preemption is not allowed.


Under the model above, each job J_i can be represented by a pair (r_i, t_i) of integers, where r_i, the
R-time, is the time for processing the R-operation of J_i by an R-processor, and t_i, the
T-time, is the time for processing the T-operation of J_i by a T-processor. A schedule
S of a set of jobs {J_1, …, J_n} on m flowshops M_1, …, M_m consists of an
assignment that assigns each job to a flowshop, and, for each flowshop, the execution orders of the R-
and T-operations of the jobs assigned to that flowshop in its corresponding processors. The completion
time of a flowshop M under the schedule S is the time when M finishes the execution of the last
T-operation for the jobs assigned to M (assuming all flowshops are available at the initial time 0).
The makespan C_max of S is the largest flowshop completion time under the schedule
S over all flowshops. Following the three-field notation α|β|γ suggested by Graham
et al. <cit.>, this scheduling model can be written as P |  | C_max, or
P_m |  | C_max if the number m of flowshops is a fixed constant.



 §.§ Two-stage job scheduling on a single two-stage flowshop


For m = 1, the problem P_1 ||C_max becomes the two-stage flow shop problem. Without loss of
generality, a schedule of a set of two-stage jobs on a single two-stage flowshop can be given by an ordered
sequence ⟨ J_1, J_2, …, J_t ⟩ of the jobs such that both the executions of the R-operations
and T-operations of the jobs, by the R-processor and T-processor of the flowshop, respectively, strictly
follow the given order <cit.>. If our interests are in minimizing the makespan of schedules, then we
can make the following assumptions.



Let S = ⟨ J_1, J_2, …, J_t ⟩ be a two-stage job schedule on a single two-stage
flowshop, where J_i = (r_i, t_i), for 1 ≤ i ≤ t. Let ρ̅_h and τ̅_h, respectively,
be the times at which the R-operation and the T-operation of job J_h are started. Then for all h,
1 ≤ h ≤ t, we can assume:



(1)   ρ̅_h = ∑_i=1^h-1 r_i; and



(2)  τ̅_h = max{ρ̅_h + r_h, τ̅_h-1 + t_h-1}.


By the assumption, both the executions of the R-operations and the T-operations of the jobs follow the
given order. Since the R-operation of the job J_h cannot start unless the R-operations of all jobs J_1,
…, J_h-1 are completed on the R-processor of the flowshop, we must have
ρ̅_h ≥∑_i=1^h-1 r_i. If ρ̅_h > ∑_i=1^h-1 r_i, then we can let the
R-operation of the job J_h start at time ρ̅_h' = ∑_i=1^h-1 r_i. Note that this change
does not delay any other process — in particular, since the T-operation of J_h starts at time
τ̅_h, which must be at least ρ̅_h + r_i. Now since the R-operation of J_h starts at
time ρ̅_h' = ∑_i=1^h-1 r_i and finishes at time ρ̅_h' + r_i < ρ̅_h + r_i,
the T-operation of J_h can still start at time τ̅_h  ≥ρ̅_h + r_i > ρ̅_h' + r_i.
For all other jobs, since the starting and finishing times of their R-operations and T-operations are
unchanged, the schedule remains a valid schedule, with no change in the completion time of the flowshop.
Applying this process repeatedly, we can fill all “gaps” in the execution of the R-processor of the flowshop
(i.e., the idle time in the R-processor of the flowshop between the finish of the R-operation of a job and
the start of the R-operation of the next job). The result is a valid schedule of the jobs, with no change
in the completion time of the flowshop, and satisfies the condition ρ̅_h = ∑_i=1^h-1 r_i for
all 1 ≤ h ≤ t. This proves (1).

The proof of (2) is simple: the R-operation of the job J_h is finished at time ρ̅_h + r_h, and
the T-operation of the job J_h-1 is finished at time τ̅_h-1 + t_h-1. Therefore, at time
max{ρ̅_h + r_h, τ̅_h-1 + t_h-1}, the T-operation of the job J_h can always start,
with no reason to further wait if our objective is to minimize the completion time of the flowshop. Moreover,
this is the earliest time at which the T-operation of J_h can start.



Scheduling two-stage jobs on a single two-stage flowshop, i.e., the two-stage flow shop problem
P_1||C_max, can be solved optimally in time O(n log n) using the classical Johnson's
algorithm. In terms of our model, Johnson's algorithm can be described as follows  (for more details,
see <cit.>):

  Johnson's Algorithm <cit.>.

  Given a set of two-stage jobs (r_i, t_i), 1 ≤ i ≤ n, divide the jobs into two disjoint groups
  G_1 and G_2, where G_1 contains all jobs (r_h, t_h) with r_h ≤ t_h, and G_2 contains all
  jobs (r_g, t_g) with r_g > t_g. Order the jobs in a sequence such that the first part consists of the
  jobs in G_1, sorted in nondecreasing order of R-times, and the second part consists of the jobs in
  G_2, sorted in nonincreasing order of T-times. The schedule using the order of this sequence minimizes
  the completion time of the flowshop over all schedules of the jobs on the flowshop.


Johnson's order of a set of two-stage jobs is to order the jobs into a sequence that satisfies the conditions
given by Johnson's Algorithm above. Therefore, once we determined how the jobs are assigned to the flowshops,
Johnson's order of the jobs assigned to each flowshop will give an optimal execution order for the flowshop. As a
result, what that remains unsolved is how we determine the assignment of the jobs to the flowshops. Unfortunately,
this task is intractable. In fact, in the special case where the R-time of every job is 0, the problem becomes
the classical Makespan problem P | | C_max, where we are asked to optimally schedule a set of (one-stage)
jobs on a set of identical (one-stage) machines. The Makespan problem is NP-hard for two machines <cit.>,
and is strongly NP-hard for three or more machines <cit.>. As a consequence, our problem P_m||C_max
is NP-hard when m ≥ 2 and NP-hard in the strong sense when m ≥ 3.

Johnson's orders of jobs on all flowshops can be constructed by a single sorting process on the input job set, as
given by the following lemma, whose proof is straightforward thus is omitted.



If a job sequence S satisfies Johnson's order, then every subsequence of S also satisfies Johnson's
order.


Therefore, if we first sort the input job set in Johnson's order, which can obviously be done in time O(n log n),
then pick the jobs in that order and assign them to flowshops, then every flowshop receives a subset of jobs in
their Johnson's order, which directly gives the optimal execution order of the job subset on the flowshop. In the
rest of this paper, we will always assume that any sequence of jobs in our consideration is in Johnson's order,
unless we explicitly indicate otherwise.

Lemma <ref> indicates that in an optimal schedule on a single flowshop based on Johnson's order, we can
simply follow Johnson's order and let the R-processor of the flowshop consecutively execute the R-operations
of the jobs without idle time until all R-operations are completed, and start immediately the T-operation of
the job J_h as soon as the R-operation of J_h and the T-operation of the job J_h-1 are completed. This
observation greatly helps us in dealing with two-stage jobs on multiple two-stage flowshops. In particular, for a
partial assignment of jobs on a flowshop, its corresponding (optimal) schedule now can be characterized by a
pair (ρ, τ), which gives the finish times of the R-operation and the T-operation of the last job
assigned to the flowshop. The pair (ρ, τ), which will be called the status of the schedule,
can be easily updated, based on the formulas given in Lemma <ref>, when a new job is added to the flowshop.



 §.§ Dual jobs and dual schedules


For a two-stage job J_i = (r_i, t_i), the dual job of J_i is J_i^d = (t_i, r_i) (i.e., the dual
job J_i^d is obtained from the original job J_i by swapping its R- and T-times). Let
S = ⟨ J_1, J_2, …, J_n ⟩ be a schedule of two-stage jobs on a two-stage flowshop.
The dual schedule of S on the dual jobs of S is given by
S^d = ⟨ J_n^d, …, J_2^d, J_1^d ⟩, where J_i^d is the dual job of J_i for
1 ≤ i ≤ n. It is interesting to observe and easy to verify that if the schedule S follows
Johnson's order, then the dual schedule S^d also follows Johnson's order. In fact, we have a more
general result, as giving in the following theorem.



For 1 ≤ i ≤ n, let J_i^d be the dual job of the two-stage job J_i. On a single two-stage flowshop,
the optimal schedule of the job set G = { J_1, J_2, …, J_n } and the optimal schedule of the dual
job set G^d = { J_1^d, J_2^d, …, J_n^d } have the same completion time. Moreover, if a schedule
S is optimal for the job set G then its dual schedule S^d is optimal for the dual job
set G^d.


For each h, let J_h = (r_h, t_h). Thus, the dual job of J_h is J_h^d = (t_h, r_h). Let
S = ⟨ J_1, J_2, …, J_n ⟩ be an optimal schedule for the job set G, where, by
Lemma <ref>, for each job J_h, the R-operation starts at time ρ̅_h = ∑_i=1^h-1 r_i
and finishes at time ρ̅_h + r_h, and the T-operation starts at time
τ̅_h = max{ρ̅_h + r_h, τ̅_h-1 + t_h-1} and finishes at time τ̅_h + t_h.
The completion time of the schedule S is τ^* = τ̅_n + t_n.

Now consider the schedule S_1^d = ⟨ J_n^d, …, J_2^d, J_1^d ⟩ for the dual job set
G^d, where for each dual job J_h^d = (t_h, r_h), 1 ≤ h ≤ n, the R-operation of J_h^d starts at
time ρ̅_h' = τ^* - (τ̅_h + t_h) and finishes at time ρ̅_h” = τ^* - τ̅_h,
and the T-operation of J_h^d starts at time τ̅_h' = τ^* - ∑_i=1^h r_i and finishes at time
τ̅_h” = τ^* - ∑_i=1^h-1 r_i (see Figure <ref> for an illustration).


Note that since τ̅_h+1≥τ̅_h + t_h, the job J_h^d has its R-operation starting
at time ρ̅_h' = τ^* - (τ̅_h + t_h), which is not earlier than the finish time
ρ̅_h+1” = τ^* - τ̅_h+1 of the R-operation of the job J_h+1^d. Similarly, the
job J_h^d has its T-operation starting at time τ̅_h' = τ^* - ∑_i=1^h r_i, which is not
earlier than (actually, is equal to) the finish time τ̅_h+1” = τ^* - ∑_i=1^h r_i of the
T-operation of the job J_h+1^d. Finally, since τ̅_h ≥ρ̅_h + r_h = ∑_i=1^h r_i,
the starting time τ̅_h' = τ^* - ∑_i=1^h r_i of the T-operation of the job J_h^d is not
earlier than the finish time ρ̅_h” = τ^* - τ̅_h of the R-operation of the same job
J_h^d. This shows that S_1^d is a valid schedule for the dual job set G^d. Since the last job
J_1^d in the schedule S_1^d finishes at time τ̅_1” = τ^*, the completion time of
S_1^d is τ^*. Now, by Lemma <ref>, we can convert the schedule S_1^d into the
standard dual schedule S^d of S, without increasing the completion time, where S^d
is a schedule for the dual job set G^d and satisfies the conditions in Lemma <ref>.

By our assumption, S is an optimal schedule for the job set G and has completion time τ^*. Thus,
the fact that the completion time of the dual schedule S^d for the dual job set G^d is not larger
than τ^* implies that the completion time of an optimal schedule for the job set G is not smaller than
that of an optimal schedule for the dual job set G^d.

For the other direction, we start with an optimal schedule S^d for the dual job set G^d. Using exactly
the same procedure, we can show that the schedule ( S^d)^d that is dual to S^d for the job set
(G^d)^d that is dual to G^d has its completion time not larger than that of S^d. Since the job set
(G^d)^d that is dual to the dual job set G^d is just the original job set G, this shows that the completion
time of an optimal schedule for the dual job set G^d is not smaller than that of an optimal schedule for the
original job set G.

Combining these results, we conclude that the optimal schedule of the job set G and the optimal schedule of
the dual job set G^d have the same completion time. This implies that if the completion time of an optimal
schedule S for the job set G is τ^*, then the completion time of the dual schedule S^d
for the dual job set G^d is also τ^*. Thus, S^d must be optimal for the dual job set G^d.



Now consider scheduling two-stage jobs on multiple two-stage flowshops. Let G = {J_1, J_2, …, J_n } be
a set of two-stage jobs, and let G^d = {J_1^d, J_2^d, …, J_n^d } be the dual job set, where for each
h, J_h^d is the dual job of the job J_h.



On multiple two-stage flowshops, the optimal schedule of the job set G and the optimal schedule of the dual
job set G^d have the same makespan. Moreover, an optimal schedule for the job set G can be easily obtained
from an optimal schedule for the dual job set G^d.


Suppose that S is an optimal schedule of the job set G on m two-stage flowshops, where for each
i, 1 ≤ i ≤ m, S assigns a subset G_i of jobs in G to the i-th flowshop. Without loss of
generality, we can assume that S optimally schedules the jobs in G_i on the i-th flowshop. Now for
each i, replace the schedule of G_i on the i-th flowshop by its dual schedule for the dual job set
G_i^d. This gives a schedule S^d on the m flowshops for the dual job set G^d. By Theorem <ref>,
under the schedule S^d, the completion time for each flowshop is the same as that under the schedule
S. Thus, the makespan of the schedule S^d for the dual job set G^d on the m flowshops is the
same as that of the schedule S for the job set G. This proves that the makespan of an optimal schedule
for G on the m flowshops is not smaller than that of an optimal schedule for G^d.

Conversely, starting with an optimal schedule of the dual job set G^d on m two-stage flowshops, we can
similarly construct a schedule for the original job set G whose makespan is equal to that of the optimal
schedule for G^d, which implies that the makespan of an optimal schedule for G^d on the m flowshops
is not smaller than that of an optimal schedule for G.

Combining these results shows that the optimal schedule of the job set G and the optimal schedule of the
dual job set G^d have the same makespan. The discussion also explains that starting with an optimal schedule
S^d for the dual job set G^d, by replacing the schedule on each flowshop with its dual schedule
we can obtain an optimal schedule of the job set G.



Theorem <ref> provides flexibility when we work on scheduling two-stage jobs on multiple two-stage
flowshops: sometimes working on the job set that is dual to the given input job set may have certain advantages.
In this case, we can simply work on the dual job set, whose optimal solutions can be easily converted into
optimal solutions for the original job set. This property will be used in Section 4.




§ PSEUDO-POLYNOMIAL TIME ALGORITHMS FOR P_M |  | C_MAX



In this section, we study the problem P_m |  | C_max, i.e., the problem of scheduling
two-stage jobs on m two-stage identical flowshops, where m is a fixed constant. Our input
is a set of two-stage jobs G = {J_1, J_2, …, J_n}, where for each i, J_i = (r_i, t_i), and
we are looking for a schedule of the jobs on m identical two-stage flowshops M_1, …, M_m,
that minimizes the makespan. Let R_0 = ∑_i=1^n r_i, T_0 = ∑_i=1^n t_i, and for
0 ≤ k ≤ n, let G_k = {J_1, J_2, …, J_k} be the set of the first k jobs in G.

With a preprocessing, we can assume that the sequence ⟨ J_1, J_2, …, J_n ⟩ is in Johnson's
order. If we pick the jobs in this order and assign them to the flowshops, then, by Lemma <ref>, the
subsequence received by each flowshop M_h is also in Johnson's order, which thus gives an optimal schedule
of the jobs assigned to the flowshop M_h. Therefore, the status of the flowshop M_h at any moment can be
represented by a pair (ρ_h, τ_h) for the corresponding schedule, where ρ_h and τ_h
are the completion times of the R-processor and the T-processor, respectively, of the flowshop M_h. By
Lemma <ref>, the status (ρ_h, τ_h) of the flowshop M_h can be easily updated when a new job
(r, t) is added to the flowshop M_h: the new completion time of the R-processor will be ρ_h + r,
and the new completion time of the T-processor will be max{ρ_h + r, τ_h} + t. For each schedule
S of the job subset G_k, the tuple (k; ρ_1, τ_1, …, ρ_m, τ_m) will be called the
configuration of S if under the schedule S for G_k, the status of the flowshop M_h
is (ρ_h, τ_h), for all h.

The key observation, which can be easily verified, is that for each k > 0, we have:



Fact A.  The tuple (k; ρ_1, τ_1, …, ρ_m, τ_m) is a configuration of a schedule
for the job subset G_k if and only if there is a flowshop M_d such that the tuple
(k-1; ρ_1', τ_1', …, ρ_m', τ_m') is a configuration of a schedule for the job subset
G_k-1, where for i ≠ d, ρ_i' = ρ_i, τ_i' = τ_i, and ρ_d' and τ_d' satisfy
ρ_d = ρ_d' + r_k and τ_d = max{ρ_d' + r_k, τ_d'} + t_k, i.e., the schedule given by
(k; ρ_1, τ_1, …, ρ_m, τ_m) is obtained by adding the job J_k to flowshop M_d in the
schedule given by (k-1; ρ_1', τ_1', …, ρ_m', τ_m').



Fact A suggests a dynamic programming algorithm that starts with the tuple (0; 0, 0, …, 0, 0),
which corresponds to the unique schedule for the initial empty job subset G_0, and applies Fact A
repeatedly to construct all possible configurations for the schedules for the given job set G = G_n.
Moreover, the value max_h {τ_h} for a configuration (n; ρ_1, τ_1, …, ρ_m, τ_m)
gives the makespan of the schedule described by the configuration. Therefore, The configuration
(n; ρ_1, τ_1, …, ρ_m, τ_m) with max_h {τ_h} being minimized over all configurations
gives a schedule for the job set G on the m flowshops whose makespan is the minimum over all schedules
of the job set G.

It is easy to see that for all 1 ≤ h ≤ m, the value ρ_h is an integer bounded between 0 and
R_0, and the value τ_h is an integer bounded between 0 and R_0 + T_0. Therefore, a straightforward
implementation of the dynamic programming algorithm runs in time O(n m^2R_0^m (R_0+T_0)^m), which will be quite
significant when the values of R_0 and T_0 are large. In the following, we study how the complexity of the
algorithm is improved.

Let (ρ_h, τ_h) be the status of the flowshop M_h. By definition, we always have ρ_h ≤τ_h.
Moreover, for any job J_i assigned to the flowshop M_h, by Lemma <ref>, if the T-operation of
J_i starts no earlier than ρ_h, then it can always start immediately after the T-operation of the
previous job assigned to M_h is completed, i.e., there is no “gap” in the execution of the T-processor
of M_h after time ρ_h. This gives τ_h - ρ_h ≤ T_0. This observation suggests that we can
use the pair (ρ_h, δ_h) instead of the pair (ρ_h, τ_h), where δ_h = τ_h - ρ_h,
and 0 ≤δ_h ≤ T_0. Note that the pair (ρ_h, τ_h) can be easily obtained from the pair
(ρ_h, δ_h).

Therefore, for a configuration (k; ρ_1, τ_1, …, ρ_m, τ_m) for a schedule for the job
subset G_k, we will represent it by the tuple (k; ρ_1, δ_1, …, ρ_m, δ_m), where
for all h, δ_h = τ_h - ρ_h with 0 ≤δ_h ≤ T_0, which will be called the
s-configuration of the schedule.



Remark. Our configurations and s-configurations defined above are very different from those
proposed in the literature <cit.>, where a configuration is defined based on the makespan of
the schedule (see <cit.> for more details). We will show that based on the formulation of
our configurations, much faster algorithms can be developed for the P_m |  | C_max problem.



Our next improvement is based on reducing the dimension of the s-configurations. Let
S_k = (k; ρ_1, δ_1, …, ρ_m, δ_m) be an s-configuration for the job subset
G_k. Let R_0^k = ∑_i=1^k r_i. By Lemma <ref>, there is no “gap” in the execution of the
R-processors of the flowshops. Therefore, ∑_h=1^m ρ_h = R_0^k. This gives



Fact B. The value ρ_1 can be computed from the values ρ_2, …, ρ_m:
ρ_1 = R_0^k - ∑_h=2^m ρ_h.



Let S_k = (k; ρ_1, δ_1, ρ_2, δ_2, …, ρ_m, δ_m) and
S_k' = (k; ρ_1, δ_1', ρ_2, δ_2, …, ρ_m, δ_m) be s-configurations
for the job subset G_k that only differ in the completion time of the T-processor of flowshop M_1, with
δ_1 < δ_1'. It is easy to see that if we can assign the rest of the jobs J_k+1, …,
J_n to S_k' to build a minimum makespan schedule for the entire job set G, then the same way of
assigning the jobs J_k+1, …, J_n to S_k will also give a minimum makespan schedule of
the job set G. Therefore, when all other parameters are identical, we really only have to record the smallest
completion time (thus the smallest value δ_1) for the T-processor of the flowshop M_1.

This suggests that we can represent all “useful” s-configurations for G_k by a (2m-1)-dimensional array H
such that

    H[k; ρ_2, δ_2, …, ρ_m, δ_m] = (δ_1, d),

if by letting ρ_1 = R_0^k - ∑_h=2^m ρ_h, the value δ_1 is the smallest δ_1' such
that (k; ρ_1, δ_1', ρ_2, δ_2, …, ρ_m, δ_m) is a valid s-configuration for the job
subset G_k.

Now we are ready for our algorithm, which is given in Figure <ref>.


We give some explanations for the algorithm. Steps 3.4-3.7 add the job J_k+1 to the
d-th flowshop in the schedule for the job subset G_k with an s-configuration
S = (k; ρ_1, δ_1, ρ_2, δ_2, …, ρ_m, δ_m). Thus, before adding
the job J_k+1, the completion times of the R-processor and the T-processor of the d-th
flowshop are ρ_d and ρ_d + δ_d, respectively. By Lemma <ref>, after adding the job
J_k+1, the completion time of the R-processor becomes ρ_d' = ρ_d + r_k+1, and the
completion time of the T-processor is max{ρ_d + r_k+1, ρ_d + δ_d} + t_k+1. Therefore,
by the definition, after adding the job J_k+1, we should have

    δ_d'     =     (max{ρ_d + r_k+1, ρ_d + δ_d} + t_k+1) - ρ_d' 
        =    max{r_k+1, δ_d} + ρ_d + t_k+1 - (ρ_d + r_k+1)
        =    max{r_k+1, δ_d} + t_k+1 - r_k+1,

as shown in step 3.5 of the algorithm.

Note that the last row H[n; *, …, *] of the (2m-1)-dimensinal array H includes all
possible s-configurations of the schedules for the job set G = G_k on the m flowshops. Moreover,
the value max_1 ≤ h ≤ m{ρ_h + δ_h} for an element
H[n; ρ_2, δ_2, …, ρ_m, δ_m] = (δ_1, d) (where ρ_1 = R_0 - ∑_h=2^m ρ_h)
gives the makespan of the schedule described by H[n; ρ_2, δ_2, …, ρ_m, δ_m] = (δ_1, d).
Therefore, the one with max_1 ≤ h ≤ m{ρ_h + δ_h} being minimized over all
H[n; ρ_2, δ_2, …, ρ_m, δ_m] = (δ_1, d) with δ_1 ≠ +∞, as the
one returned in step 4 of the algorithm, gives a schedule for the job set G on the m flowshops whose
makespan is the minimum over all schedules of the job set G. According to the algorithm, the value
H[k; ρ_2, δ_2, …, ρ_m, δ_m] = (δ_1, d) also records that the last job J_k in
the job subset G_k was added to the flowshop M_d to obtain the s-configuration corresponding to
H[k; ρ_2, δ_2, …, ρ_m, δ_m] = (δ_1, d). With this information, the actual schedule
corresponding to the element H[k; ρ_2, δ_2, …, ρ_m, δ_m] = (δ_1, d) can be
re-constructed as follows: (1) if d ≠ 1, then look through H[k-1; ρ_2, δ_2, …, ρ_d-1,
δ_d-1, ρ_d - r_k, δ_d', ρ_d+1, δ_d+1, …, ρ_m, δ_m] = (δ_1, d)
with δ_1 ≠ +∞ for all 0 ≤δ_d' ≤ T_0; and (2) if d = 1, then look at 
the element H[k-1; ρ_2, δ_2, …, ρ_m, δ_m] = (δ_1', d), we will find an element 
H[k-1; ρ_2', δ_2', …, ρ_m', δ_m'] for the job subset G_k-1 that, when J_k is 
added to the flowshop M_d, gives the array element H[k; ρ_2, δ_2, …, ρ_m, δ_m].
Now with this array element H[k-1; ρ_2', δ_2', …, ρ_m', δ_m'] for G_k-1, we 
will find where the job J_k-1 went and what is the corresponding array element for G_k-2, and so 
on. Thus, starting from the array element returned in step 4 of the algorithm DynProg-I, we will be 
able to re-construct an optimal schedule for the job set G.

Since we have 0 ≤ k ≤ n, and 0 ≤ρ_h ≤ R_0, 0 ≤δ_h ≤ T_0, for all
2 ≤ h ≤ m, the (2m-1)-dimensional array H has a size O(nR_0^m-1T_0^m-1). The algorithm
basically goes through the array H, element by element, and applies steps 3.2-3.7 on each element,
which take time O(m^2). Thus, the algorithm takes time O(n m^2 R_0^m-1 T_0^m-1) and space
O(n R_0^m-1 T_0^m-1) (i.e., the space for the array H). Note that if we want to re-construct the
optimal schedule based on the element returned in step 4 of the algorithm, we can go through the rows 
H[k; *, …, *] of the array H (i.e., the first index of the array) backwards (i.e., k goes 
from n to 1), as we described above. This will
take additional O(nm T_0) time. Now we are ready to conclude the algorithm with the following theorem.



An optimal schedule for n two-stage jobs on m two-stage flowshops can be constructed in time
O(n m^2 R_0^m-1 T_0^m-1) and space O(n R_0^m-1 T_0^m-1).


We compare Theorem <ref> with the existing result given in <cit.>, which is the only known result
for the P_m |  | C_max problem. The algorithm given in <cit.> is based on a very different
definition for configurations for schedules of two-stage jobs on m two-stage flowshops, and has running
time O(nm^2(R_0 + T_0)^2m-1) and space O(m(R_0 + T_0)^2m-2). Therefore, in terms of the running time,
our algorithm in Theorem <ref> not only replaces the larger factor R_0 + T_0 by smaller factors R_0
and T_0, but also reduces the exponent from 2m-1 to 2m-2. In terms of the space complexity, our algorithm
seems to use more space because in general n > m. However, a careful examination shows that the algorithm
given in <cit.> seems to only return the value of the makespan of an optimal schedule without giving
the actual optimal schedule. In order to also return an actual schedule, the algorithm in <cit.>
seems to have to increase its space complexity to at least O(n m (R_0 + T_0)^2m-2). On the other
hand, if we are only interested in the value of the makespan of an optimal schedule for the given job
set, then we can modify our algorithm to run in space O(R_0^m-1 T_0^m-1): according to the algorithm
DynProg-I, each row H[k+1; *, …, *] of the array H is computed based solely on the
previous row H[k; *, …, *]. Therefore, we only need to keep two rows of the array H, and
repeatedly compute the next row based on the current row. This will use space O(R_0^m-1 T_0^m-1),
which also improves the space complexity of the algorithm in <cit.>. In conclusion, our algorithm
in Theorem <ref> improves both time complexity and space complexity of the algorithm given in
<cit.>.




§ DEALING WITH THE CASE WHEN R_0 AND T_0 DIFFER SIGNIFICANTLY


In certain cases in practice, the values R_0 and T_0 can differ very significantly. Consider
the situation in data centers as we described in Section 1. In order to improve the process of
data-read/network-transformation, severs in the center may keep certain commonly used software codes
in the main memory so that the time-consuming process of data-read can be avoided (see, for example,
<cit.>). Thus, client requests for the code will become two-stage jobs J_i = (r_i, t_i)
with r_i = 0. As a consequence, the value R_0 = ∑_i=1^n r_i can be significantly smaller
than the value T_0 = ∑_i=1^n t_i. On the other hand, certain data centers may consist of a
large number of slow-speed servers (e.g., PC's) but equipped with high-speed networks <cit.>,
which may make T_0 much smaller than R_0.

In this section, we will study how to reduce the sizes of the dimensions of the configurations for
the schedules in the case where the values R_0 and T_0 differ very significantly. This will lead
to significant improvements on the complexity of scheduling algorithms. We divide the study into two
cases: (1) T_0 is significantly larger than R_0 (i.e., T_0 ≫ R_0), and (2) R_0 is significantly
larger than T_0 (i.e., T_0 ≪ R_0). We first consider the case T_0 ≫ R_0.

Since all flowshops are identical, we can arbitrarily re-order the flowshops. In particular, we can
order the flowshops so that the completion times of the R-operations of the flowshops are non-increasing.
We call an s-configuration (k; ρ_1, δ_1, …, ρ_m, δ_m) canonical if
ρ_1 ≥ρ_2 ≥⋯≥ρ_m. Any s-configuration of a schedule can be converted into
a canonical s-configuration by properly re-ordering the flowshops. Therefore, we only need to consider
canonical s-configurations.

Let (k; ρ_1, δ_1, …, ρ_m, δ_m) be a canonical s-configuration for a schedule
S_k for the job subset G_k. By Lemma <ref>, there is no “gap” in the execution of the
R-processors of the flowshops, so ∑_h=1^m ρ_i ≤ R_0. This gives reduced upper bounds for
the completion time of the R-processors of the flowshops:



Fact C. In a canonical s-configuration (k; ρ_1, δ_1, …, ρ_m, δ_m),
ρ_h ≤ R_0/h, for all 1 ≤ h ≤ m.



As we explained in the previous section, if our objective is to minimize the makespan, then when all the
values k, ρ_1, ρ_2, δ_2, …, ρ_m, δ_m are given, we only need to record
the smallest δ_1' such that (k; ρ_1, δ_1', ρ_2, δ_2, …, ρ_m, δ_m)
corresponds to a valid schedule for the job subset G_k. This reduces the number of dimensions for
the s-configurations by 1.[However, unlike algorithm DynProg-I, we will not be able to
remove the dimension for ρ_1 in s-configurations. This will become clearer in our discussion.]

In contrast to Fact C, the values δ_h can be very large (recall T_0 ≫ R_0). We now consider
how to deal with the situations when the values δ_h are large.

Fix an h, and consider the h-th flowshop. By Fact C, the completion time of the R-processor of
the flowshop can never be larger than R_0/h ≤ R_0. If the completion time ρ_h + δ_h of
the h-th flowshop is larger than or equal to R_0, then for any further job J_p assigned to the
flowshop, the T-operation of J_p can always start immediately when the T-processor is available.
Therefore, all further jobs assigned to the flowshop can have their T-operations executed consecutively
with no execution “gaps” in the T-processor of the flowshop.[Actually by Fact C, this
statement holds true for the h-th flowshop when ρ_h + δ_h ≥ R_0/h. However, since later
we may need to re-order the flowshops to keep the s-configurations canonical, the h-th flowshop may
become the h'-the flowshop with ρ_h + δ_h < R_0/h'. Thus, here we pick the looser but
more universal bound ρ_h + δ_h ≥ R_0 that is independent of h and also simplifies our
discussion.] Thus, the completion time of the flowshop will only depend on the T-operations of the
further assigned jobs, while is independent of the R-operations of these jobs. We can use a single
value ρ_h = R_0/h + 1 to record this situation so that the pair (R_0/h+1, δ_h) represents
a real status (ρ_h', δ_h') of the flowshop where ρ_h' + δ_h' ≥ R_0, and
δ_h = ρ_h' + δ_h' - R_0. Note that when a new job J_p = (r_p, t_p) is added to the
flowshop, the corresponding pair of the flowshop is simply changed to (R_0/h+1, δ_h + t_p).

This observation enables us to represent the status of the h-th flowshop by a pair (ρ_h, δ_h),
where either 0 ≤ρ_h ≤ R_0/h and 0 ≤ρ_h + δ_h < R_0 (which implies
0 ≤δ_h < R_0), or ρ_h = R_0/h+1 and 0 ≤δ_h ≤ T_0 (which implies that the
completion time for the T-processor of the flowshop is R_0 + δ_h). A pair is a valid pair
for the h-th flowshop if it satisfies these conditions. The total number of valid pairs for the h-th
flowshop is bounded by (R_0/h + 1)R_0 + (T_0 + 1) = O(R_0^2/h + T_0). Note that all valid pairs can be
given by a two-dimensional array (i.e., a matrix) with R_0/h + 2 rows in which each of the first
R_0/h + 1 rows contains R_0 elements and the last row contains T_0 + 1 elements (if you like, you
can also regard this matrix as an (R_0/h+1) × R_0 matrix plus a one-dimensional array of size T_0 + 1).

Summarizing the above discussions, we conclude that all “useful” canonical s-configurations for the job
subset G_k, for all k, can be represented by a (2m)-dimensional array H' whose elements are
(m+1)-tuples, such that if

    H'[k; ρ_1, ρ_2, δ_2, …, ρ_m, δ_m] = (d_k, δ_1', ρ_2', …, ρ_m'),

where 0 ≤ρ_1 ≤ R_0, and for 2 ≤ h ≤ m, (ρ_h, δ_h) is a valid pair for the h-th flowshop,
then there is a canonical s-configuration (k; ρ_1', δ_1', ρ_2', δ_2', …, ρ_m', δ_m')
for a valid schedule for the job subset G_k, where ρ_1' = ρ_1 and δ_1' is the smallest when all
other parameters satisfy their conditions, such that for each h, 2 ≤ h ≤ m,



(1) if ρ_h ≤ R_0/h, then ρ_h + δ_h < R_0, ρ_h' = ρ_h and δ_h' = δ_h, and

(2) if ρ_h = R_0/h + 1, then ρ_h' + δ_h' ≥ R_0, and δ_h = ρ_h' + δ_h' - R_0.



Finally the value d_k in the array element, 1 ≤ d_k ≤ m, indicates that the last job J_k in the
job subset G_k is assigned to the d_k-th flowshop.

Note that in the case ρ_h = R_0/h + 1, there can be many different values for ρ_h' that thus
correspond to many different canonical s-configurations that satisfy the above conditions. As
explained earlier, in this case, different choices of the values ρ_h' will not affect the
makespan of the final schedule of the job set G. Thus, we can pick any valid values (not necessarily
the smallest) for these ρ_h', as long as their sum plus ρ_1 is equal to ∑_i=1^k r_i.

Since the total number of valid pairs for the h-th flowshop, for 2 ≤ h ≤ m, is O(R_0^2/h + T_0),
and 0 ≤ k ≤ n, we conclude that the number of elements in the array H' is bounded by

    O((n+1) (R_0+1) ∏_h=2^m (R_0^2/h + T_0)) = O(n (R_0^2m-1/m! + R_0 T_0^m-1)).

Finally, since each element of H' is an (m+1)-tuple, we conclude that the array H' takes space
O(nm(R_0^2m-1/m! + R_0 T_0^m-1)).

We explain how to extend a schedule for the job subset G_k to a schedule for the job subset
G_k+1 when the job J_k+1 is added. For this, suppose that we have a canonical s-configuration
S_k = (k; ρ_1', δ_1', ρ_2', δ_2', …, ρ_m', δ_m')
for G_k that is given by the element of the array H':

    H'[k; ρ_1, ρ_2, δ_2, …, ρ_m, δ_m] = (d_k, δ_1', ρ_2', …, ρ_m'),

as explained above. Note that the s-configuration S_k can be completely re-constructed when the
corresponding element of H' is given:



(1)  the status (ρ_1', δ_1') for the first flowshop is (ρ_1, δ_1');

(2)  for 2 ≤ h ≤ m,

(2.1) if 0 ≤ρ_h ≤ R_0/h, then the status (ρ_h', δ_h') of the h-th flowshop is
    (ρ_h, δ_h); and

(2.2) if ρ_h = R_0/h+1, then the status (ρ_h', δ_h') of the h-th flowshop is
    (ρ_h', R_0 + δ_h - ρ_h').



Note that in case (2.2), what matter is that the completion time of the T-processor is
equal to ρ_h' + (R_0 + δ_h - ρ_h') = R_0 + δ_h, while the value ρ_h' may vary
as long as it satisfies ρ_1 + ∑_h=2^m ρ_h' = R_0.

Now suppose that we decide to add the job J_k+1 = (r_k+1, t_k+1) to the d-th flowshop in the
s-configuration S_k. Then the resulting configuration for the job subset G_k+1 will become

    (k+1; ρ_1”, δ_1”, ρ_2”, δ_2”, …, ρ_m”, δ_m”),

where ρ_d” = ρ_d' + r_k+1 and δ_d” = max{r_k+1, δ_d'} + t_k+1 - r_k+1
(see the explanation given for algorithm DynProg-I in the previous section), and for h ≠ d,
ρ_h” = ρ_h' and τ_h” = τ_h'. This, after properly sorting the flowshops using the
values of ρ_h”, becomes a canonical s-configuration

    S_k+1 = (k; ρ̅_1', δ̅_1', ρ̅_2', δ̅_2',
           …, ρ̅_m', δ̅_m')

for the job subset G_k+1. Assume the d-th flowshop in S_k becomes the d_k+1-th flowshop
in S_k+1. Now let ρ̅_1 = ρ̅_1', and for each h, 2 ≤ h ≤ m, if
ρ̅_h' + δ̅_h' < R_0 then let ρ̅_h = ρ̅_h' and
δ̅_h = δ̅_h', and if ρ̅_h' + δ̅_h' ≥ R_0 then let
ρ̅_h = R_0/h + 1 and δ̅_h = ρ̅_h' + δ̅_h' - R_0. With these values,
look at the array element

    H'[k+1; ρ̅_1, ρ̅_2, δ̅_2, …, ρ̅_m, δ̅_m].

If the element has not been assigned a value, yet, then assign it the value
(d_k+1, δ̅_1', ρ̅_2', …, ρ̅_m'). If the element already has a value
(d', δ̅_1”, ρ̅_2”, …, ρ̅_m”) but δ̅_1' < δ̅_1”,
then change its value to (d_k+1, δ̅_1', ρ̅_2', …, ρ̅_m'). This completes
the process of extending the canonical s-configuration given by the array element
H'[k, ρ_1, ρ_2, δ_2, …, ρ_m, δ_m], when job J_k+1 is added to the d-th
flowshop, to an array element for a canonical s-configuration for the job subset G_k+1. It is easy
to see that this process takes time O(m).

Using the above description to replace the steps 3.1-3.7 in the algorithm DynProg-I gives the procedure of
extending a canonical s-configuration for G_k to a canonical s-configuration for G_k+1. This, plus certain
obvious modifications in other steps, gives a new algorithm DynProg-II for the P_m||C_max
problem. Since the number of elements of the array H' is bounded by O(n (R_0^2m-1/m! + R_0 T_0^m-1)),
we conclude that the time complexity of the algorithm DynProg-II is O(n m^2(R_0^2m-1/m! + R_0 T_0^m-1)).
Similarly as we explained for the algorithm DynProg-I, once we apply algorithm DynProg-II and
find the array element of H' that gives a minimum makespan schedule of the job set G on the m flowshops,
we can use the array to construct the actual schedule by backtracking the array, row by row, in the same
amount of time.

Now we describe how to deal with job sets G when T_0 ≪ R_0. Let G^d be the dual job set of G, and
let R_0' and T_0' be the sums of the times of the R-operations and of the T-operations, respectively, of
the jobs in G^d. By the definition, R_0' = T_0 and T_0' = R_0. Therefore, we have T_0' ≫ R_0'. Thus,
applying the algorithm DynProg-II on the dual job set G^d will construct an optimal schedule for G^d
in time O(nm^2 ((R_0')^2m-1/m! + R_0' (T_0')^m-1)) = O(nm^2 (T_0^2m-1/m! + T_0 R_0^m-1)). By Theorem <ref>,
an optimal schedule for the job set G can be easily constructed from the optimal schedule for the dual job
set G^d returned by the algorithm DynProg-II.

This allows us to close this section with the following theorem:



An optimal schedule for a set of two-stage jobs {J_1, …, J_n} on m two-stage flowshops, where
J_k = (r_k, t_k), can be constructed in time O(nm^2 (T_min^2m-1/m! + T_min T_max^m-1)) and
space O(nm (T_min^2m-1/m! + T_min T_max^m-1)), where T_min and T_max are the smaller
and the larger, respectively, of the values ∑_k=1^n r_k and ∑_k=1^n t_k.


When T_max≫ T_min, Theorem <ref> provides significant improvements. For example, if
T_max = T_min^2, then, for a fixed constant m, the time complexity of the algorithm given
in Theorem <ref> is of the order O(n T_min^2m-1) = O(n T_max^m-1/2), which almost
matches the best pseudo-polynomial time algorithm for the Makespan problem P_m | | C_max
on m machines <cit.>, which can be regarded as a much simpler version of the
P_m | | C_max problem in which all jobs are one-stage jobs and all machines are
one-stage flowshop. On the other hand, the time complexity of algorithm DynProg-I given in the
previous section is of the order O(n T_min^3m-3) = O(n T_min^m-1 T_max^m-1).




§ APPROXIMATION ALGORITHMS FOR P_M |  | C_MAX


Based on the well-known techniques in approximation algorithms <cit.>, we can use the
pseudo-polynomial time algorithms given in previous sections to develop approximation algorithms
for the problem P_m |  | C_max. We present such approximation algorithms in this
section.

Since the problem P_1 |  | C_max of scheduling two-stage jobs on a single
two-stage flowshop can be solved optimally in polynomial time, we will assume m ≥ 2
in our discussion in this section.

Let S be a schedule for a set G = {J_1, J_2, …, J_n} of two-stage jobs on m
two-stage flowshops. The schedule S can be described by a partition of the job set G into
m subsets, which can be given by a job index partition (P_1, P_2, …, P_m), which is
a disjoint partition of {1,2, …, n}. Thus, under the schedule S, the job subset
G_h = {J_k | k ∈ P_h} of G is assigned to the h-th flowshop M_h, for all h. The
schedule S can be easily implemented if for each h, we order the jobs in G_h in Johnson's
order. For each h, let C( S, h) be the completion time of the flowshop M_h under the
schedule S. Thus, the makespan C_max( S) of the schedule S is equal
to max_1 ≤ h ≤ m{C( S, h)}. We say that the schedule S achieves
its makespan on the flowshop M_h if C_max( S) = C( S, h).

The following lemma will be useful in the analysis of our approximation algorithms.



Let S_k = ⟨ J_1, J_2, …, J_k ⟩ be a schedule on a two-stage flowshop
M. If we replace each job J_i = (r_i, t_i) with the job J_i' = (r_i+1, t_i+1) in the
schedule S_k, then the completion time τ_k' of the resulting schedule
S_k' = ⟨ J_1', J_2', …, J_k' ⟩ is bounded by k+1 plus the completion
time τ_k of S_k.


We prove the lemma by induction on k. For k=1, the lemma holds true since it is easy to
see that increasing both the R-time and T-time of the job J_1 increases the completion
time of the single-job schedule for {J_1} by at most 2.

Now consider the case k > 1. Consider the “partial” schedule
S_k-1 = ⟨ J_1, J_2, …, J_k-1⟩ which is obtained by taking off
the last job J_k from the schedule S_k. Let the completion times of the R-processor
and the T-processor of the flowshop M under the schedule S_k-1 be ρ_k-1 and
τ_k-1, respectively. By Lemma <ref>, τ_k=max{ρ_k-1+r_k, τ_k-1}+t_k.

Now replace each job J_i = (r_i, t_i) in the schedule S_k-1 with the job J_i' = (r_i+1, t_i+1),
for 1 ≤ i ≤ k-1. By the inductive hypothesis, the completion time τ_k-1' of the
resulting schedule S_k-1' = ⟨ J_1', J_2', …, J_k-1' ⟩ is bounded by
τ_k-1 + (k-1) + 1 = τ_k-1 + k. Again by Lemma <ref>, the completion time ρ_k-1'
of the R-processor of M on the schedule S_k-1' is equal to ρ_k-1 + (k-1). Now we
can add the job J_k' = (r_k+1, t_k+1) to the schedule S_k-1' to obtain the schedule
S_k' = ⟨ J_1', J_2', …, J_k' ⟩. By Lemma <ref>, the completion time
τ_k' of the flowshop M under the schedule S_k' is

    τ_k'     =    max{ρ_k-1' + (r_k + 1), τ_k-1' } + (t_k + 1) 
       ≤   max{ρ_k-1 + (k-1) + (r_k + 1), τ_k-1 + k } + (t_k + 1) 
        =    max{ρ_k-1 + r_k + k, τ_k-1 + k } + (t_k + 1)
        =     (max{ρ_k-1 + r_k, τ_k-1} + t_k) +  (k + 1)
        =    τ_k + (k + 1).

This completes the proof of the lemma.



Now we are ready to present the approximation algorithm, which is given in Figure <ref>.


We first study how well the schedule S returned by the algorithm can approximation the
optimal schedule for the job set G on the m flowshops.

Both the schedule S' for the job set G' and the schedule S for the job set G
use the same job index partition (P_1, …, P_m). Suppose that S achieves its makespan
C_max( S) on flowshop M_h and that S' achieves its makespan C_max( S')
on flowshop M_h'. Let S_0 be an optimal schedule for the job set G that has a job
index partition (P_1', …, P_m') and achieves its makespan C_max( S_0) on flowshop
M_d. Let S_0' be the schedule for the job set G' that also uses the job index partition
(P_1', …, P_m') and achieves its makespan C_max( S_0') on flowshop M_d'.

We need some further notations for our analysis. As we defined, for a schedule S based on the
job index partition (P_1, …, P_m) and a flowshop M_h, C( S, h) denotes the completion
time of the flowshop M_h under the schedule S. Let K be the number defined in step 1 of
the algorithm. We will use the notation C( S/K, h) to denote the completion time of the flowshop
M_h under the schedule S with each J_k = (r_k, t_k) of the jobs in the job subset
{J_i | i ∈ P_h} replaced by the job (r_k/K, t_k/K), i.e., we shrink each of the jobs by a
factor K. Note here the jobs may no longer have integral R-time and T-time – this will not affect
the complexity of our algorithms and the correctness of our analysis because we will only use this
notation and our algorithms will not take advantage of this relaxation. With these notations, we have

    C_max( S)     =     C( S, h) = K · C( S/K, h) 
       ≤    K · C( S', h) + Kn ≤ K · C( S', h') + Kn 
       ≤    K · C( S_0', d') + Kn ≤ K · C( S_0/K, d') + Kn 
        =     C( S_0, d') + Kn ≤ C( S_0, d) + Kn 
        =     Opt(G) + Kn


We explain the derivations in (<ref>)-(<ref>). The first equality in (<ref>) is
because by our assumption, the schedule S achieves its makespan on flowshop M_h. The
second equality in (<ref>) is obvious: if we proportionally shrink the R-time and the
T-time of each job in flowshop M_h by a factor K, then the completion time of the flowshop
M_h is also shrunk by a factor K.

Now consider (<ref>). To simplify the notations without loss of generality, let 
⟨ J_1, J_2, …, J_k ⟩ be the schedule on the flowshop M_h induced from the 
schedule S. Since there are m ≥ 2 flowshops, we have k ≤ n-1. The schedule 
S/K on the “shrunk” jobs induces a schedule ⟨ J_1/K, J_2/K, …, J_k/K ⟩ 
on the flowshop M_h, where J_p/K = (r_p/K, t_p/K), 1 ≤ p ≤ k. If we replace each 
shrunk job J_p/K = (r_p/K, t_p/K) in the flowshop M_h by the job 
(J_p/K)^+ = (⌊ r_p/K ⌋ + 1, ⌊ t_p/K ⌋ + 1) with larger R-time and
T-time, the completion time C(( S/K)^+, h) of the flowshop M_h under the resulting
schedule ( S/K)^+ = ⟨ (J_1/K)^+, …, (J_k/K)^+ ⟩ will not be decreased. 
That is, C( S/K, h) ≤ C(( S/K)^+, h). On the other hand, the schedule
( S/K)^+ on the flowshop M_h can be obtained from the schedule S/K, via the
schedule S' defined in step 4 of the algorithm Approx, as follows: first we 
replace in S/K each shrunk job J_p/K = (r_p/K, t_p/K) in M_h by the job 
J_p' = (⌊ r_p/K ⌋, ⌊ t_p/K ⌋), as defined in step 3 of the algorithm
Approx. Since neither of the R-time and T-time of each job is increased, the resulting
schedule S', as given in step 4 of the algorithm that shares the same job index partition
with S, has its completion time on the flowshop M_h not larger than that of S/K.
That is, C( S', h) ≤ C(( S/K), h). Now the schedule ( S/K)^+ on the
flowshop M_h is obtained from the schedule S' by increasing both R-time and T-time
of each job in M_h by 1. By Lemma <ref>,
C(( S/K)^+, h) ≤ C( S', h) + (k+1) ≤ C( S', h) + n (here we have used the
fact k ≤ n-1). This, combined with C( S/K, h) ≤ C(( S/K)^+, h) proved above,
gives immediately C( S/K, h) ≤ C( S', h) + n. This proves the first inequality
in (<ref>). The second inequality in (<ref>) is because we assume the schedule S'
achieves its makespan on flowshop M_h'.

By the algorithm Approx, S' is an optimal schedule for the job set G' that achieves 
its makespan on flowshop M_h'. By our assumption, S_0' is also a (not necessarily optimal) 
schedule for the job set G' that achieves its makespan on flowshop M_d'. This explains the first 
inequality in (<ref>). The second inequality in (<ref>) is based on the observation that if 
we replace the R-time and T-time of each job J_p' = (⌊ r_p/K ⌋, ⌊ t_p/K ⌋) 
in flowshop M_d' by not smaller numbers r_p/K and t_p/K, respectively, the completion time of 
the flowshop M_d' would not decrease.

The reason for the equality in (<ref>) is the same as that for the second equality in (<ref>).
The inequality in (<ref>) is because the schedule S_0 achieves its makespan on flowshop
M_d. Finally, the equality in (<ref>) is because we assume S_0 is an optimal schedule
for the job set G (here we have used Opt(G) for the makespan of an optimal schedule for the job
set G).

According to the derivation in (<ref>)-(<ref>), C_max( S) ≤ Opt(G) + Kn. From
K = ϵ· T_max/(nm), we get Kn = ϵ· T_max/m ≤ϵ· Opt(G),
where the inequality is based on the obvious fact T_max/m ≤ Opt(G). This gives us the following
relation:

    C_max( S) ≤ Opt(G) (1 + ϵ) 
        C_max( S)/Opt(G) ≤ 1 + ϵ.


The time complexity of the algorithm Approx depends on the algorithm A we use
in step 4 of the algorithm to construct the optimal schedule S' for the job set
G' = {J_1', J_2', …, J_n'}. For example, if we use the algorithm DynProg-I in
Figure <ref>, then by Theorem <ref>, the running time of the algorithm DynProg-I,
thus the running time of the algorithm Approx will be O(n m^2 (R_0')^m-1(T_0')^m-1),
where

    R_0' = ∑_i=1^n r_i'
         = ∑_i=1^n ⌊ r_i/K ⌋≤1/K( ∑_i=1^n r_i )
         = ( ∑_i=1^n r_i ) ·nm/ϵ· T_max≤nm/ϵ,

here we have used the inequality ∑_i=1^n r_i = R_0 ≤ T_max. Similarly,
T_0' ≤ (nm)/ϵ. This shows that the running time of the algorithm Approx is
bounded by O(n^2m-1m^2m/ϵ^2m-2). This concludes the discussion of this
section with the following theorem.



There is an algorithm for the P_m |  | C_max problem
that on a set G of n two-stage jobs and any real number ϵ > 0, constructs a schedule
for the job set G on m two-stage flowshops with a makespan bounded by Opt(G)(1 + ϵ).
Moreover, the running time of the algorithm is O(n^2m-1m^2m/ϵ^2m-2).


Compared to the approximation algorithm given in <cit.>, which also produces a schedule with
makespan bounded by Opt(G)(1 + ϵ) but runs in time O(2^2m-1n^2mm^2m+1/ϵ^2m-1),
our algorithm in Theorem <ref> gives an obvious improvement on the running time.

When m is a fixed constant, the algorithm in Theorem <ref> runs in time polynomial in n
and 1/ϵ. In the literature of approximation algorithms, such approximation algorithms with
a ratio 1 + ϵ are called fully polynomial-time approximation schemes (FPTAS) <cit.>.
Thus, Theorem <ref> claims that the P_m |  | C_max problem has an FPTAS when
m is a fixed constant.



§ CONCLUSION


Motivated by the current research in data centers and cloud computing, we studied the scheduling
problem of two-stage jobs on multiple two-stage flowshops, which in particular addresses the
scheduling issues of data transmissions between clients and servers in data centers in the cloud
computing framework based on the principle of transparent computing. The problem is NP-hard.
Pseudo-polynomial time algorithms for the problem were presented that produce optimal solutions
for the problem when the number of flowshops is a fixed constant. In particular, with thorough
analysis, we show that for certain cases, much faster pseudo-polynomial time algorithms can be
achieved. Approximation algorithms for the problem have also been developed and studied. Our
algorithms improve previous known algorithms for the problem.

Needs and considerations in cloud computing practice suggest many further research topics that require
the study of variations and extensions of our scheduling model. We list some of them below for future
research.

A cloud computing center may have many servers with different powers, ranging from large mainframe
computers to small PC's. The disks connected to the servers and the network bandwidth available for
the servers can also differ. Moreover, the disk-read on a server at some moment may even not be needed
if the requested data is already in the server's main memory. This calls for the study of scheduling
two-stage jobs on heterogeneous two-stage flowshops. Our scheduling model can be easily extended to
include this situation: suppose that we need to schedule n jobs J_1, …, J_n on m flowshops
M_1, …, M_m that may not be identical, then we can represent each two-stage job J_i by
m pairs { (r_i,j, t_i,j) | 1 ≤ j ≤ m }, where (r_i,j, t_i,j) gives the R-time
and the T-time, respectively, for the job J_i to be processed by the flowshop M_j. Of course,
constructing optimal schedules and developing good approximation algorithms on this more general model
become more challenging. We are currently working on this extended version of the scheduling model.

In many cases, a data request from a client is for a file, which consists of a number of data blocks
stored in either secondary or main memory. In a real system, it is possible that the disk-read and
network-transmission of the same file are executed in a pipeline manner in units of data blocks. Thus,
once a data block of a file is read entirely into the main memory, the block can be transmitted via
networks to the client even if some other data blocks for the file have not been read into the main
memory, yet. In particular, in such a model, preemption of processing data transmissions from servers
to clients becomes possible: after transmitting a few data blocks for a file F, a server may switch
to processing a different task, and come back later to continue transmitting the remaining data blocks
for the file F. Under this assumption, each data request from a client can be given by its size,
corresponding to the number of data blocks of the data, and the data request can be decomposed into a
continuous sequence of two-stage jobs, each corresponds to the disk-read and network-transmission of
a data block. Preemptions now are allowed on processing a data request from a client. However, frequent
preemptions for processing data requests should be avoided since restarting disk-read for a file will
require new disk search, which is significantly more time-consuming compared to reading a data block.
Therefore, when we study scheduling on this model, penalty on preemptions should be considered.

Scheduling with job precedences is very common in cloud computing practice. For example, a user who
wants to run a Microsoft application on a transparent computing platform may need from the cloud both
the code of the application as well as the code of Microsoft Windows software. However, the application
cannot be installed until the Windows software is installed on the client device <cit.>. As
a consequence, there is a need to study the scheduling problems under our model in which job
precedence is presented.


1

  queue
  D. Abts and B. Felderman, 
  A guided tour through data-center networking,
  Queue, 10(5), 10-23, (2012).

  setup
  A. Allahverdi, C. Ng, T. E. Cheng, and M. Y. Kovalyov, 
  A survey of scheduling
  problems with setup times or costs, 
  European Journal of Operational Research, 187(3), 985-1032, (2008).

  hjs1
  P. Brucker and R. Schlie, 
  Job-shop scheduling with multi-purpose machines,
  Computing, 45(4), 369-375, (1990).

  bruno74
  J. Bruno, E. G. Coffman Jr, and R. Sethi, 
  Scheduling independent tasks to reduce mean finishing time, 
  Communications of the ACM, 17(7), 382-387, (1974).

  lee
  J. Chen and C.-Y. Lee, 
  General multiprocessor task scheduling, 
  Naval Research Logistics, 46(1), 57-74, (1999).

  
  chenmiranda
  J. Chen and A. Miranda, 
  A polynomial time approximation scheme for general multiprocessor job scheduling, 
  SIAM Journal on computing, 31(1), 1-17, (2001).

  hjs2
  J. C. Chen, K. H. Chen, J. J. Wu, and C. W. Chen, 
  A study of the flexible job shop scheduling problem with parallel machines and reentrant process, 
  The International Journal of Advanced Manufacturing Technology, 39(3-4), 344-354, (2008).

  dong
  J. Dong, W. Tong, T. Luo, X. Wang, J. Hu, Y. Xu, and G. Lin, 
  An FPTAS for the parallel two-stage flowshop problem, 
  Theoretical Computer Science, in press.

  gj
  M. R. Gary and D. S. Johnson, 
  Computers and intractability: A guide to the theory of NP-completeness, 
  WH Freeman and Company, New York, 1979.

  graham
  R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. R. Kan, 
  Optimization and approximation in deterministic sequencing and scheduling: a survey,
  Annals of discrete mathematics, vol. 5, 1979, pp. 287-326.


  davidhe
  D. W. He, A. Kusiak, and A. Artiba, 
  A scheduling problem in glass manufacturing, 
  IIE transactions, 28(2), 129-139, (1996).

  ik75
  O. H. Ibarra and C. E. Kim, 
  Fast approximation algorithms for the knapsack and sum of subset problems, 
  Journal of the ACM (JACM), 22(4), 463-468, (1975).

  johnson
  S. M. Johnson, 
  Optimal two-and three-stage production schedules with setup times included, 
  Naval research logistics quarterly, 1(1), 61-68, (1954).

  hfs99
  R. Linn and W. Zhang, 
  Hybrid flow shop scheduling: a survey,
  Computers & industrial engineering, 37(1), 57-61, (1999).

  book16
  M. L. Pinedo, 
  Scheduling: Theory, Algorithms, and Systems, 
  Springer Science, New York, 2016.

  
  y50
  C. N. Potts and V. A. Strusevich, 
  Fifty years of scheduling: a survey of milestones, 
  Journal of the Operational Research Society, 60(1), S41-S68, (2009).

  hfs10
  R. Ruiz and J. A. Vázquez-Rodríguez, 
  The hybrid flow shop scheduling problem, 
  European Journal of Operational Research, 205(1), 1-18, (2010).

  tong
  R. G. W. Tong, E. Miyano, and G. Lin, 
  A PTAS for the muliple parallel identical multi-stage flow-shops to minimize the makespan, 
  Proc. FAW2016, Lecture Notes in Computer Science, springer, vol. 9711, 2016, pp. 227–237.

  elhafsi
  G. Vairaktarakis and M. Elhafsi, 
  The use of flowlines to simplify routing complexity in two-stage flowshops, 
  IIE Transactions, 32(8), 687-699, (2000).

	
  xzhang
  X. Zhang and S. van de Velde, 
  Approximation algorithms for the parallel flow shop problem, 
  European Journal of Operational Research, 216(3), 544-552, (2012).

  transcomp
  Y. Zhang and Y. Zhou, 
  Transparent computing: a new paradigm for pervasive computing, 
  in Proceedings of the Third International Conference on Ubiquitous Intelligence and Computing, Springer, 2006, pp. 1–11.

  virtual
  Y. Zhang and Y. Zhou, 
  Separating computation and storage with storage virtualization, 
  Computer Communications, 34(13), 1539-1548, (2011).

  transos
  Y. Zhang and Y. Zhou, 
  Transos: a transparent computing-based operating system for the cloud, 
  International Journal of Cloud Computing, 1(4), 287-301, (2012).

  uefi
  V. Zimmer, M. Rothman, and S. Marisetty, 
  Beyond BIOS: developing with the unified extensible firmware interface, Intel Press, 2010.



