# A Note on Multimachine Scheduling with Weighted Early/Late Work Criteria and Common Due Date

Authors: Kerang Cao; Xin Chen; Kwang-nam Choi; Yage Liang; Qian Miao; Xingong Zhang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In this note, we revisit two types of scheduling problem with weighted early/late work criteria and a common due date. For parallel identical machines environment, we present a dynamic programming approach running in pseudopolynomial time, to classify the considered problem into the set of binary NP-hard. We also propose an enumeration algorithm for comparison. For two-machine flow shop systems, we focus on a previous dynamic programming method, but with a more precise analysis, to improve the practical performance during its execution. For each model, we verify our studies through computational experiments, in which we show the advantages of our techniques, respectively.


---

## Body

## 1. Introduction

Scheduling with due date constraint [1, 2] has been widely studied in the field of combinatorial optimization, such as minimizing tardiness [3], lateness [4], or the number of late jobs [5]. Among all the criteria related to the due date, late work [6] and early work [7] are a pair of symmetrical objectives, in which the former one indicates the loss once a job is finished after its due date, while the latter one implies the profit when a job starts execution before this time.The concept of late work was first proposed in 1984 by Błażewicz [8], who was motivated from the scene of data collection in a control system, and, therefore, he called this parameter “information loss” at that time. Then, in 1992, Potts and Van Wassenhove [9] claimed that this criterion can model not only information collection but also other situations where a perishable commodity is involved, so they suggested using the term “late work.” After these pioneers, scheduling with late work minimization has attracted much attention from different research groups, for example, [10‒14].Although the formal investigation on the early work maximization problem was started from 2017 [7], this parameter has already appeared frequently in the literature since 2004, which was used as auxiliary metrics when analysing the optimal schedules for late work problems, for example, [10, 11]. Due to the symmetry of these two criteria, scheduling with late work minimization and early work maximization shares the same essence when the offline optimal solutions are constructed. However, since the difference when an approximation solution is evaluated [12], scheduling with early work criterion gradually became a new subject, and several studies were devoted to it [13, 14].In this note, we revisit two types of scheduling problem with a common due date to maximize total weighted early work of all jobs or, equivalently, to minimize total weighted late work (in sense of complexity and optimal offline solution analysis). We focus on the identical machines and two-machine flow shop environments, respectively, and, therefore, the problems considered in this paper could be presented asPm|dj=d|maxXw (or equally, Pm|dj=d|Yw) and F2|dj=d|maxXw (or equally, F2|dj=d|Yw), using the classical three-field notation in the scheduling field [15].The rest of this paper is organized as follows. In Section2, we give the formal definitions of the studies problems, i.e., Pmdj=dmaxXw and F2dj=dmaxXw, respectively. Section 3 is devoted to the former problem, where we propose a dynamic programming approach running in pseudopolynomial time and an enumeration algorithm in exponential time, on the basis of a property of an optimal schedule. In Section 4, we focus on a previous dynamic programming method in [16], by introducing some improvement techniques. Finally, the whole paper is concluded in Section 5.


## 2. Problem Formulation

The early work of a jobJj (denoted as Xj) is defined as the early part (if any) executed before its due date dj. That is, let pj and Cj be the processing and completion time of Jj, respectively; we have(1)Xj=pj,dj≥Cj;pj−Cj−dj,Cj−pj<dj<Cj;0,dj≤Cj−pj.Correspondingly, the late work ofJj (denoted as Yj) is the late part processing after dj, i.e.,(2)Yj=0,dj≥Cj;Cj−dj,Cj−pj<dj<Cj;pj,dj≤Cj−pj.Based on the definitions of these two parameters, we haveXj+Yj=pj.Thus, the problems we considered in this paper can be described as follows:(1)
Pm|dj=d|maxXw. Input: there are m identical machines and n jobs, and each job Jj is accompanied by its processing time pj, weight wj, as well as a common due date d (1≤j≤n).Output: assign then jobs to the m machines without preemption, with the goal of maximizing total weighted early work of all jobs (denoted as Xw), in which Xw=∑j=1nwjXj.As we mentioned before, the above problem could be presented asPm|dj=d|maxXw by the three-field notation, in which we use max in the γ field to emphasize that it is a maximization problem. Moreover, since the symmetry of early work maximization and late work minimization, we have wjYj=wjpj−wjXj (so does ∑j=1nwjYj=∑j=1nwjpj−∑j=1nwjXj), which implies that the results on the complexities and the constructions of the optimal offline solutions could be directly transferred from Pm|dj=d|maxXw to Pm|dj=d|Yw.(2)
F2|dj=d|maxXw. In this model, we are given a two-machine flow shop, and each job (also accompanied with pji-the processing time of Jj on Mi for i∈1,2, a weight wj , and a common due date d) has to be processed firstly on M1 and then on M2. Same as in the previous one, we are aimed to schedule these jobs into the system so that to maximize total weighted early work, i.e., ∑j=1nwjXj (here we define Xj=Xj1+Xj2, in which Xji is the early work of Jj on Mi, for i∈1,2). It is worth to be mentioned that, when analysing complexity and designing optimal offline algorithms, the problem could be treated as the same as F2|dj=d|Yw, which is the original representation in [16].


## 3. Exact Approaches forPm|dj=d|maxXw

In this section, we first introduce a property of an optimal schedule for problemPm|dj=d|maxXw, based on which we propose two exact approaches. Among them, the former one is a dynamic programming method running in pseudopolynomial time, so that we can decide that problem Pm|dj=d|maxXw belongs to the set of binary NP-hard, while the latter is an enumeration one, which can help us to verify the correctness and efficiency of the dynamic programming by computational experiments.


### 3.1. Property of an Optimal Schedule

We now introduce a property of an optimal schedule in Lemma1, which could help us to design the exact methods for problem Pm|dj=d|maxXw latter.Lemma 1.
There exists an optimal schedule for problemPm|dj=d|maxXw such that on each machine, jobs are sequenced in nonincreasing order of their weights.Proof.
Suppose that there exists one of the optimal schedulesπ, in which on machine Mi (1≤i≤m), there are two jobs Jk and Jh such that Jk≺Jh while wk<wh, where Jk≺Jh means that Jk precedes (close to) Jh on Mi. Then, we can construct a new schedule π′ by exchanging the positions of the two jobs and show that the criterion value Xw cannot decrease after this modification.
We prove the above declaration based on the possible values of the common due date, i.e.,d. Denote Sj and Cj as the start and completion time of the job Jj in π, respectively (1≤j≤n).Case 1.
d≤Sk, which means that both jobs are late in π (also in π′). Then, the total weighted early work of these two jobs is equal to 0, in both π and π′.Case 2.
d≥Ch, where both jobs are early in π (also in π′). Then, the criterion value of these two jobs is equal to wk·pk+wh·ph, in both π and π′.Case 3.
Sk<d<Ch. Then, the total weighted early work of these two jobs in π is equal to wk·Xk+wh·Xh=wk⋅minpk,d−Sk+wh⋅max0,d−Sh. We claim that the criterion value would be increased in π′, since the length of the early parts of the two jobs remains the same (as in π), while the weight becomes higher after the exchanging.
Therefore, in any optimal schedule, by adjusting the positions of the two adjacent jobs which do not follow this order, we can finally get another optimal schedule, which concludes this lemma.


### 3.2. Dynamic Programming Approach

Based on Lemma1, we could construct an optimal solution with the following process: (1) we first reorder the job sequence in nondecreasing order of jobs’ weights, i.e., w1≤w2≤…≤wn; (2) then, we assign the jobs in the ordered sequence one by one to a suitable machine, using a dynamic programming approach defined as follows.Letfj,E1,E2,…,Em denote the maximal total weighted early work of the first j jobs scheduled on m machines, where the early parts are executed for at most E1,E2,…,Em units on M1,M2,…,Mm, respectively. The initial condition should be set as f0,E1,E2,…,Em=0 for all the 0≤Ei≤d1≤i≤m, and the optimal criterion value is output as fn,d,d,…,d.The recurrence procedure runs according to the following formula:(3)fj,E1,E2,…,Em=maxfj−1,max0,E1−pj,E2,…,Em+wj⋅minpj,E1,fj−1,E1,max0,E2−pj,…,Em+wj⋅minpj,E2,…,fj−1,E1,E2,…,max0,Em−pj+wj⋅minpj,Em.We give the complete procedure in Algorithm1, denoted as Algo_DPp.Algorithm 1:Algo_DPp.
(1)
Reorder the jobs by nondecreasing order of their weights, i.e.,w1≤w2≤⋯≤wn;(2)
AssignJ1 to M1;(3)
for (2≤j≤n)(4 )
do Calculatefj,d,d,…,d to find a suitable machine for Jj with the(current) maximal criterion value, sayMs;(5)
ScheduleJj on the first position of Ms, and move the alreadyscheduled jobs onMs (if any) backward;The sorting process requiresOnlogn time, and the dynamic programming approach runs in Ondm. Summing up, the time consumption of Algo_DPp is Omaxnlogn,ndm, which is pseudopolynomial when m is fixed. Then, we have the following theorem.Theorem 2.
ProblemPm|dj=d|maxXw belongs the set of binary NP-hard.Proof (Proof of Theorem2).
This theorem holds since the existence ofAlgo_DPp.


### 3.3. Enumeration Algorithm

To further reveal the correctness and efficiency ofAlgo_DPp, we also propose an enumeration algorithm for comparison. We first sort the jobs in nonincreasing order of their weights and then enumerate all the possible partitions to find the optimal solution. The procedure is presented in Algorithm 2 denoted as Algo_EM.Algorithm 2:Algo_EM.
(1)
Reorder the jobs by nonincreasing order of their weights, i.e.,w1≥w2≥⋯≥wn;(2)
Enumerate all the possible partitions of the job set;(3)
for each partition(4)
do Keep the nonincreasing order of the jobs on each machine;(5)
Calculate the criterion value for this schedule;(6)
Output the best solution with the maximal criterion value;Since there arem machines and n jobs, it takes Omn time to check all the possible schedules. Therefore, Algo_EM runs in Omaxnlogn,ndm time.


### 3.4. Computational Experiments

To compare the two algorithms proposed in Sections3.2 and 3.3, we design a set of numerical experiments in this part. Since both of them return the optimal solutions, we focus on the efficiencies of these approaches, i.e., their time consumption.Motivated by [7], we set the experiment data by the following process. The job processing time pj was randomly taken with a discrete uniform distribution from 1,20, and the weight wj was taken also from this range. The common due date d is set to be d=∑j=1npj/m. Moreover, due to the memory limitation, we set n∈15,20,25,30,35,40,45,50 when m=2, and n∈5,8,10,15,20,25,30,35 when m=3.Both of the two algorithms were implemented in C++ with the IDE of Microsoft Visual Studio 2017 and executed on a PC with Intel Core i7-8550U 1.8 GHz CPU and 8 GB DDR4 RAM. For each pair ofm,n, we generate 25 random instances and show the results in Table 1, in which the running time of Algo_DPp and Algo_EM is reported in milliseconds (ms).Table 1
Running time (ms) of Algo_DPp and Algo_EM.
mnAlgo_DPpAlgo_EM2154.7875.18208.862431.072518.6994018.373044.00—3593.98—40169.97—45380.40—50891.51—357.594.411021.01326.031555.0427998.2520166.15—25442.99—30901.01—351977.48—404807.40—From Table1, we can find that Algo_DPp works much more efficiently than Algo_EM. Basically, the time consumption of Algo_DPp is Omaxnlogn,ndm (Ondm for most of the case) while Algo_EM takes Omn time, which results in the fact that the latter one needs more time when processing the same setting of m,n than the former. More precisely, for a fixed m, the time consumption of Algo_DPp increases slowly while Algo_EM increases drastically, along with the increment of n. This is mainly because that ndm could be considered as a linear function of n while mn is an exponential one, when m is fixed. Finally, Algo_EM has to stop at n=25 when m is 2, and n=15 when m is 3, due to the limitation of memory. However, Algo_DPp could solve all the test sequences, mostly within 1 second in our experiments.


## 3.1. Property of an Optimal Schedule

We now introduce a property of an optimal schedule in Lemma1, which could help us to design the exact methods for problem Pm|dj=d|maxXw latter.Lemma 1.
There exists an optimal schedule for problemPm|dj=d|maxXw such that on each machine, jobs are sequenced in nonincreasing order of their weights.Proof.
Suppose that there exists one of the optimal schedulesπ, in which on machine Mi (1≤i≤m), there are two jobs Jk and Jh such that Jk≺Jh while wk<wh, where Jk≺Jh means that Jk precedes (close to) Jh on Mi. Then, we can construct a new schedule π′ by exchanging the positions of the two jobs and show that the criterion value Xw cannot decrease after this modification.
We prove the above declaration based on the possible values of the common due date, i.e.,d. Denote Sj and Cj as the start and completion time of the job Jj in π, respectively (1≤j≤n).Case 1.
d≤Sk, which means that both jobs are late in π (also in π′). Then, the total weighted early work of these two jobs is equal to 0, in both π and π′.Case 2.
d≥Ch, where both jobs are early in π (also in π′). Then, the criterion value of these two jobs is equal to wk·pk+wh·ph, in both π and π′.Case 3.
Sk<d<Ch. Then, the total weighted early work of these two jobs in π is equal to wk·Xk+wh·Xh=wk⋅minpk,d−Sk+wh⋅max0,d−Sh. We claim that the criterion value would be increased in π′, since the length of the early parts of the two jobs remains the same (as in π), while the weight becomes higher after the exchanging.
Therefore, in any optimal schedule, by adjusting the positions of the two adjacent jobs which do not follow this order, we can finally get another optimal schedule, which concludes this lemma.


## 3.2. Dynamic Programming Approach

Based on Lemma1, we could construct an optimal solution with the following process: (1) we first reorder the job sequence in nondecreasing order of jobs’ weights, i.e., w1≤w2≤…≤wn; (2) then, we assign the jobs in the ordered sequence one by one to a suitable machine, using a dynamic programming approach defined as follows.Letfj,E1,E2,…,Em denote the maximal total weighted early work of the first j jobs scheduled on m machines, where the early parts are executed for at most E1,E2,…,Em units on M1,M2,…,Mm, respectively. The initial condition should be set as f0,E1,E2,…,Em=0 for all the 0≤Ei≤d1≤i≤m, and the optimal criterion value is output as fn,d,d,…,d.The recurrence procedure runs according to the following formula:(3)fj,E1,E2,…,Em=maxfj−1,max0,E1−pj,E2,…,Em+wj⋅minpj,E1,fj−1,E1,max0,E2−pj,…,Em+wj⋅minpj,E2,…,fj−1,E1,E2,…,max0,Em−pj+wj⋅minpj,Em.We give the complete procedure in Algorithm1, denoted as Algo_DPp.Algorithm 1:Algo_DPp.
(1)
Reorder the jobs by nondecreasing order of their weights, i.e.,w1≤w2≤⋯≤wn;(2)
AssignJ1 to M1;(3)
for (2≤j≤n)(4 )
do Calculatefj,d,d,…,d to find a suitable machine for Jj with the(current) maximal criterion value, sayMs;(5)
ScheduleJj on the first position of Ms, and move the alreadyscheduled jobs onMs (if any) backward;The sorting process requiresOnlogn time, and the dynamic programming approach runs in Ondm. Summing up, the time consumption of Algo_DPp is Omaxnlogn,ndm, which is pseudopolynomial when m is fixed. Then, we have the following theorem.Theorem 2.
ProblemPm|dj=d|maxXw belongs the set of binary NP-hard.Proof (Proof of Theorem2).
This theorem holds since the existence ofAlgo_DPp.


## 3.3. Enumeration Algorithm

To further reveal the correctness and efficiency ofAlgo_DPp, we also propose an enumeration algorithm for comparison. We first sort the jobs in nonincreasing order of their weights and then enumerate all the possible partitions to find the optimal solution. The procedure is presented in Algorithm 2 denoted as Algo_EM.Algorithm 2:Algo_EM.
(1)
Reorder the jobs by nonincreasing order of their weights, i.e.,w1≥w2≥⋯≥wn;(2)
Enumerate all the possible partitions of the job set;(3)
for each partition(4)
do Keep the nonincreasing order of the jobs on each machine;(5)
Calculate the criterion value for this schedule;(6)
Output the best solution with the maximal criterion value;Since there arem machines and n jobs, it takes Omn time to check all the possible schedules. Therefore, Algo_EM runs in Omaxnlogn,ndm time.


## 3.4. Computational Experiments

To compare the two algorithms proposed in Sections3.2 and 3.3, we design a set of numerical experiments in this part. Since both of them return the optimal solutions, we focus on the efficiencies of these approaches, i.e., their time consumption.Motivated by [7], we set the experiment data by the following process. The job processing time pj was randomly taken with a discrete uniform distribution from 1,20, and the weight wj was taken also from this range. The common due date d is set to be d=∑j=1npj/m. Moreover, due to the memory limitation, we set n∈15,20,25,30,35,40,45,50 when m=2, and n∈5,8,10,15,20,25,30,35 when m=3.Both of the two algorithms were implemented in C++ with the IDE of Microsoft Visual Studio 2017 and executed on a PC with Intel Core i7-8550U 1.8 GHz CPU and 8 GB DDR4 RAM. For each pair ofm,n, we generate 25 random instances and show the results in Table 1, in which the running time of Algo_DPp and Algo_EM is reported in milliseconds (ms).Table 1
Running time (ms) of Algo_DPp and Algo_EM.
mnAlgo_DPpAlgo_EM2154.7875.18208.862431.072518.6994018.373044.00—3593.98—40169.97—45380.40—50891.51—357.594.411021.01326.031555.0427998.2520166.15—25442.99—30901.01—351977.48—404807.40—From Table1, we can find that Algo_DPp works much more efficiently than Algo_EM. Basically, the time consumption of Algo_DPp is Omaxnlogn,ndm (Ondm for most of the case) while Algo_EM takes Omn time, which results in the fact that the latter one needs more time when processing the same setting of m,n than the former. More precisely, for a fixed m, the time consumption of Algo_DPp increases slowly while Algo_EM increases drastically, along with the increment of n. This is mainly because that ndm could be considered as a linear function of n while mn is an exponential one, when m is fixed. Finally, Algo_EM has to stop at n=25 when m is 2, and n=15 when m is 3, due to the limitation of memory. However, Algo_DPp could solve all the test sequences, mostly within 1 second in our experiments.


## 4. Precise Analysis onF2|dj=d|maxXw

In this section, we focus on a previous dynamic programming approach proposed in [16] (denoted as Algo_DPf in this paper) for problem F2|dj=d|maxXw and introduce several improvement techniques by carefully analysing the characteristics of some parameters. Through computational experiments, we show that these skills are effective to help us to obtain the optimal solutions faster than the original version.


### 4.1. Brief Introduction onAlgo_DPf

In [16], the authors considered problem F2|dj=d|Yw (which is the same as F2|dj=d|maxXw since they focused on the complexity and the construction of the offline optimal solutions) and proposed a dynamic programming approach Algo_DPf running in On2d4. The result is very important since it can solve the problem optimally and clarify the problem complexity clearly (binary NP-hard).For a job setJ, Algo_DPf adopts an enumeration with a recurrence process to find the first partially late job (denoted as J∗) and divides the remaining jobs into three subsets, which are JE (all the totally early jobs), JP (all the partially late jobs except for J∗), and JL (all the totally late jobs). Then, Algo_DPf returns an optimal schedule as JE≺J∗≺JP≺JL, in which(1)
Jobs inJE are sequenced by Johnson’s order [17](2)
A special job inJP should take the last position in this set if it exists, while the others are sequenced arbitrarily(3)
Jobs inJL are scheduled arbitrarilyAlgo_DPf enumerates each job one time as the potential J∗. For each selection (say J∗i), it uses a recurrence process to obtain the maximal total weighted early work, under the assumption that J∗i is the “first partially late job.” The recurrence process runs based on a state function fkA,B,t,a, which denotes the maximum weighted early work among jobs Jk,Jk+1,…Jn (Jn is actually J∗i in the current case), when these jobs start exactly at time A on M1 and not earlier than at time B on M2. Moreover, parameter t means that there are exactly t time units remained on M1 after J∗i and before the common due date d, while a = 0 (or 1) means that there is no job (or only one job) among J1,J2,…Jk−1 partially executed on M1 after J∗i and before d. For each selection of J∗i, the initial state is set to be fnA,B,t,a for all 0≤A,B,t≤d, and a∈0,1 based on several different conditions, while the optimal weighted early work under this assumption (J∗i is the first partially late job) is output by f10,0,0,0. The above recurrence process needs Ond4 time, and, therefore, considering the enumeration of every job as J∗i, the whole procedure of Algo_DPf requires On2d4 time. For further details of this approach, refer to [16] or [18].


### 4.2. Several Improvement Techniques

Algo_DPf is a very important result for F2|dj=d|maxXw (so does for F2|dj=dYw) since it declared problem complexity more precisely. However, from the implementation point of view, we found that some details could be analysed, which can result in the fact that some unnecessary calculations could be avoided.Based on the characteristic of flow shop scheduling, we claim the relationship ofA and B in each state fkA,B,t,a, in Property 1.Property 1.
For each statefkA,B,t,a in Algo_DPf, B≥A+mink≤j≤npj1, where pj1 means the processing time of Jj on M1.Moreover, due to the definitions oft, A, and d in the state function, we declare Property 2.Property 2.
For each statefkA,B,t,a in Algo_DPf, t≤d−A+∑j=knpj1.Therefore, for the states that violate the above properties, we set their values directly as “−∞” without further calculations. Consequently, we denote the procedure introducing these two properties as Algo_DPf′.


### 4.3. Computational Experiments

The same as in section3.4, we introduce a series of numerical experiments to show the advantages of the properties in 4.2, i.e., we compare Algo_DPf′ with Algo_DPf.We adopt the data set from [18] for our experiments, in which Algo_DPf, an enumeration algorithm, and several heuristics for problem F2|dj=dYw (also available for F2|dj=d|maxXw) were compared. According to this literature, the job number n was selected from 10,12,14,16,18, while the processing time pji and the job weight wj were randomly taken from 1,10 and 1,5, respectively. Finally, the common due date d was set to be 30% of the mean machine load, i.e., d=30%×∑j=1npj1+pj2/2.We use the same language and platform as in Section3.4, i.e., C++ and a PC with Intel Core i7-8550U 1.8 GHz CPU and 8 GB DDR4 RAM. For each value of n, we generate 25 random instances and report the experiment results in Table 2. For each procedure, its average running time (in milliseconds, ms) is shown in the columns of “time (ms)”. Moreover, the improvement ratio from Algo_DPf to Algo_DPf′, calculated as 1−t′/t×100% (where t′ and t are the running time of Algo_DPf′ and Algo_DPf, respectively), is displayed in column “Imp (%)”.Table 2
Comparison betweenAlgo_DPf and Algo_DPf′.
nAlgo_DPfAlgo_DPf′Time (ms)Time (ms)Imp (%)10200.18132.4233.8512474.83342.7727.8114966.04738.2623.58162044.311623.0520.61183710.852993.8619.32avg.1479.241166.0721.17Now, we see the power of the two properties in Section4.2, at least from the implementation point of view. For all the settings of value n, Algo_DPf′ beats Algo_DPf, and, on average, the former procedure saves 21.17% of the execution time of the latter one. The reason is that Algo_DPf′ can avoid several unnecessary calculations if the two properties are violated.


## 4.1. Brief Introduction onAlgo_DPf

In [16], the authors considered problem F2|dj=d|Yw (which is the same as F2|dj=d|maxXw since they focused on the complexity and the construction of the offline optimal solutions) and proposed a dynamic programming approach Algo_DPf running in On2d4. The result is very important since it can solve the problem optimally and clarify the problem complexity clearly (binary NP-hard).For a job setJ, Algo_DPf adopts an enumeration with a recurrence process to find the first partially late job (denoted as J∗) and divides the remaining jobs into three subsets, which are JE (all the totally early jobs), JP (all the partially late jobs except for J∗), and JL (all the totally late jobs). Then, Algo_DPf returns an optimal schedule as JE≺J∗≺JP≺JL, in which(1)
Jobs inJE are sequenced by Johnson’s order [17](2)
A special job inJP should take the last position in this set if it exists, while the others are sequenced arbitrarily(3)
Jobs inJL are scheduled arbitrarilyAlgo_DPf enumerates each job one time as the potential J∗. For each selection (say J∗i), it uses a recurrence process to obtain the maximal total weighted early work, under the assumption that J∗i is the “first partially late job.” The recurrence process runs based on a state function fkA,B,t,a, which denotes the maximum weighted early work among jobs Jk,Jk+1,…Jn (Jn is actually J∗i in the current case), when these jobs start exactly at time A on M1 and not earlier than at time B on M2. Moreover, parameter t means that there are exactly t time units remained on M1 after J∗i and before the common due date d, while a = 0 (or 1) means that there is no job (or only one job) among J1,J2,…Jk−1 partially executed on M1 after J∗i and before d. For each selection of J∗i, the initial state is set to be fnA,B,t,a for all 0≤A,B,t≤d, and a∈0,1 based on several different conditions, while the optimal weighted early work under this assumption (J∗i is the first partially late job) is output by f10,0,0,0. The above recurrence process needs Ond4 time, and, therefore, considering the enumeration of every job as J∗i, the whole procedure of Algo_DPf requires On2d4 time. For further details of this approach, refer to [16] or [18].


## 4.2. Several Improvement Techniques

Algo_DPf is a very important result for F2|dj=d|maxXw (so does for F2|dj=dYw) since it declared problem complexity more precisely. However, from the implementation point of view, we found that some details could be analysed, which can result in the fact that some unnecessary calculations could be avoided.Based on the characteristic of flow shop scheduling, we claim the relationship ofA and B in each state fkA,B,t,a, in Property 1.Property 1.
For each statefkA,B,t,a in Algo_DPf, B≥A+mink≤j≤npj1, where pj1 means the processing time of Jj on M1.Moreover, due to the definitions oft, A, and d in the state function, we declare Property 2.Property 2.
For each statefkA,B,t,a in Algo_DPf, t≤d−A+∑j=knpj1.Therefore, for the states that violate the above properties, we set their values directly as “−∞” without further calculations. Consequently, we denote the procedure introducing these two properties as Algo_DPf′.


## 4.3. Computational Experiments

The same as in section3.4, we introduce a series of numerical experiments to show the advantages of the properties in 4.2, i.e., we compare Algo_DPf′ with Algo_DPf.We adopt the data set from [18] for our experiments, in which Algo_DPf, an enumeration algorithm, and several heuristics for problem F2|dj=dYw (also available for F2|dj=d|maxXw) were compared. According to this literature, the job number n was selected from 10,12,14,16,18, while the processing time pji and the job weight wj were randomly taken from 1,10 and 1,5, respectively. Finally, the common due date d was set to be 30% of the mean machine load, i.e., d=30%×∑j=1npj1+pj2/2.We use the same language and platform as in Section3.4, i.e., C++ and a PC with Intel Core i7-8550U 1.8 GHz CPU and 8 GB DDR4 RAM. For each value of n, we generate 25 random instances and report the experiment results in Table 2. For each procedure, its average running time (in milliseconds, ms) is shown in the columns of “time (ms)”. Moreover, the improvement ratio from Algo_DPf to Algo_DPf′, calculated as 1−t′/t×100% (where t′ and t are the running time of Algo_DPf′ and Algo_DPf, respectively), is displayed in column “Imp (%)”.Table 2
Comparison betweenAlgo_DPf and Algo_DPf′.
nAlgo_DPfAlgo_DPf′Time (ms)Time (ms)Imp (%)10200.18132.4233.8512474.83342.7727.8114966.04738.2623.58162044.311623.0520.61183710.852993.8619.32avg.1479.241166.0721.17Now, we see the power of the two properties in Section4.2, at least from the implementation point of view. For all the settings of value n, Algo_DPf′ beats Algo_DPf, and, on average, the former procedure saves 21.17% of the execution time of the latter one. The reason is that Algo_DPf′ can avoid several unnecessary calculations if the two properties are violated.


## 5. Conclusions

In this paper, we considered two problems of scheduling on multimachine with weighted early work maximization (or equivalently, late work minimization):(1)
For identical machines version, i.e., problemPm|dj=d|maxXw, we proposed a dynamic programming approach (Algo_DPp) running in pseudopolynomial time and, therefore, showed that the problem is NP-hard in the weak sense. We also designed an enumeration algorithm (Algo_EM), to reveal the correctness and efficiency of Algo_DPp through computational experiments.(2)
For two-machine flow shop setting (F2|dj=d|maxXw), we studied a previous dynamic programming approach by precise analyses. By introducing two properties in the state function, some unnecessary calculations could be avoided during processing. Finally, we again used the computational experiments to show that these improvements are efficient at least from the implementation point of view.For the future work, one can consider the more general cases, e.g., the individual due date models, and design exact or heuristic algorithms to solve them. Moreover, the approximation analyses for some special cases, especially for the flow or job shop setting, could be considered as another research direction.



---

*Source: 6611493-2021-04-17.xml*