# Heuristic and Exact Algorithms for the Two-Machine Just in Time Job Shop Scheduling Problem

Authors: Mohammed Al-Salem; Leonardo Bedoya-Valencia; Ghaith Rabadi
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

The problem addressed in this paper is the two-machine job shop scheduling problem when the objective is to minimize the total earliness and tardiness from a common due date (CDD) for a set of jobs when their weights equal 1 (unweighted problem). This objective became very significant after the introduction of the Just in Time manufacturing approach. A procedure to determine whether the CDD is restricted or unrestricted is developed and a semirestricted CDD is defined. Algorithms are introduced to find the optimal solution when the CDD is unrestricted and semirestricted. When the CDD is restricted, which is a much harder problem, a heuristic algorithm is proposed to find approximate solutions. Through computational experiments, the heuristic algorithms’ performance is evaluated with problems up to 500 jobs.


---

## Body

## 1. Introduction and Literature Review

Many objectives in scheduling are linked to due dates, which focus on meeting costumers’ delivery dates. When a CDD is considered, a set of components must be assembled into a finished product, for example, or several jobs must be shipped together to a certain customer. In Just in Time (JIT) manufacturing and production systems, it is intended to reduce both earliness and tardiness by constructing a job schedule in which the jobs are finished as close as possible to their due date. Minimizing tardiness reduces the cost of missing due dates and increases customers’ satisfaction, while minimizing earliness reduces the holding and inventory cost.Most of the published literature on minimizing earliness/tardiness (E/T) addressed the single machine E/T problem (e.g., Kanet [1], Sundararaghavan and Ahmed [2], Szwarc [3], Bagchi et al. [4], Hall and Posner [5], Hall et al. [6], Hariri and Potts [7], Rabadi et al. [8], Mason et al. [9], Rabadi et al. [10], Atan and Selim Akturk [11], Hepdogan et al. [12], Baptiste et al. [13], and Cheng et al. [14]). Baker and Scudder [15] published a comprehensive state-of-the-art review for different variants of the E/T problem including the problem with a CDD. Also, many papers addressed the same objective in multimachine scheduling environment such as parallel machines (e.g., Emmons [16], Cheng and Chen [17], Alvarez-Valdes et al. [18], Kayvanfar et al. [19], Li et al. [20], Kubiak et al. [21]) and flow shops (e.g., Sarper [22], Sung and Min [23], Mosheiov [24], Gupta et al. [25], Lauff and Werner [26], Chandra et al. [27], Behnamian et al. [28], and M’Hallah [29]). Much less has been published on scheduling problems for job shops (e.g., Lauff and Werner [30], Baptiste et al. [31], Yang et al. [32], and Wang and Li [33]). Gordon et al. [34] have reviewed more recent literature of the E/T problem with CDD. Lauff and Werner [30, 35] reviewed multistage systems involving earliness and tardiness problems with CDD as well.Kanet [1] developed an algorithm to find an optimal solution for the single machine E/T problem with an unrestricted CDD. In his work, some properties of optimal solutions were proved and used to construct a polynomial algorithm. Sundararaghavan and Ahmed [2] developed a heuristic algorithm for the same problem but with a restricted CDD (i.e., when the CDD is small enough to constrain the schedule) where they used some of the properties defined for the unrestricted case by Kanet. Bagchi et al. [4] extended Kanet’s work and developed an exact algorithm to generate alternate optimal solutions. They also developed an implicit enumeration procedure for the restricted case in a single machine environment. Raghavachari [36] extended the V-shape property of optimal schedules established by Kanet [1] to any CDD.Hoogeveen and van de Velde [37] developed a dynamic programming (DP) algorithm to solve the single machine scheduling problem with a small CDD and a positive weight for each job. They found out that the problem with equal processing times for all jobs and the problem with equal weight to processing time rates are polynomially solvable. Also, Hall and Posner [5] developed a DP algorithm for the single machine problem considering an unrestricted CDD and different weights for the jobs. Hall et al. [6] constructed an exact algorithm based on DP to find optimal solutions for the unweighted version of the single machine E/T problem with restricted CDD. Rabadi et al. [8] developed a branch-and-bound procedure to find optimal solutions for single machine problems with an unrestricted CDD and considering sequence-dependent setup times.In multimachine environments, Emmons [16] developed an algorithm that is able to solve the identical parallel machine scheduling problem when all jobs have a CDD and earliness and tardiness have different cost rates. Cheng and Chen [17] studied the problem of assigning a common due date and sequencing a set of simultaneously available jobs on several identical parallel machines.Sarper [22] developed a mixed integer linear programming formulation for the two-machine Flow Shop Scheduling Problems (FSSP) with unweighted earliness and tardiness cost over a CDD. Sung and Min [23] studied the two-machine FSSP with batch processing machines and a CDD. Mosheiov [24] studied the unit processing time on anm-machine flow shop E/T problem over nonrestricted and restricted CDD. Gupta et al. [25] defined some properties of optimal schedules for the two-machine E/T FSSP, developed lower and upper bounds, derived dominance criteria, and proposed an enumerative algorithm for finding an optimal schedule. Finally, based on some structural properties of the problem, Lauff and Werner [26] developed heuristic algorithms, both constructive and enumerative, to solve the two-machine FSSP with a given CDD considering asymmetric linear and quadratic penalty functions. Wang and Li [33] presented hybrid heuristic that combines variable neighborhood search with mathematical programming to minimize the sum of earliness and tardiness for the job shop scheduling problem with multiple due dates. Baptiste et al. [31] defined an integer programming model for the JITJSSP problem and proposed methods based on two Lagrangian relaxations of the model to derive lower and upper bounds. Yang et al. [32] introduced an enhanced genetic algorithm to solve the job shop scheduling problem of minimizing the weighted tardiness and earliness of jobs in the presence of due dates and deadlines. So far, there is no reported research on the job shop scheduling problem (JSSP) considering E/T over a CDD, and therefore, the two-machine JSSP is addressed in this paper.In the next section, a formulation of the problem with its three different cases is given. In section three, optimality conditions are introduced for two out of the three cases. Section4 presents a dynamic programming algorithm to optimally solve the semirestricted case and a heuristic algorithm to solve the restricted case. Then, in Section 5, computational experiments for the three cases are analyzed. Finally, Section 6 discusses the results and Section 7 presents the conclusions and further research.


## 2. Formulation of the Two-Machine Job Shop Scheduling Problem with a Common Due Date

This article addresses a nonpreemptive, no recirculation (jobs do not revisit the same machine)E/T JSSP with two machines,n jobs, and an integer CDD when all jobs are available at time t=0. Although JIT entails more detail and concepts, the E/T problem seems to mathematically capture the scheduling essence of it.LetCj, Ej, and Tj represent the completion time, earliness, and tardiness of jobj, respectively; Ej and Tj can be defined as(1)Ej=max0,CDD-Cj=CDD-Cj,Tj=max0,Cj-CDD=Cj-CDD.Associated with each job there is an earliness penalty αj>0 and a tardiness penalty βj>0 per time unit, which in this research are all equal to 1 (unweighted problem). The basic earliness and tardiness (E/T) objective function for a scheduleS can be written as f(S) as follows:(2)minfS=∑j=1nαjEj+βjTj.The CDD is restricted when it is small enough to restrict the scheduling decision and hence impacts the optimal sequence. The restricted version of the problem is much harder than the unrestricted version [30]. For the single machine E/T problem over a CDD, it would be desirable to construct a schedule in which half of the jobs are before the CDD [37]. If the CDD were too tight, then not enough jobs would be scheduled before the CDD, because they cannot start before time zero. For the single machine problem, the unrestricted case can be solved by using a polynomial algorithm [1]. In the JSSP, if the CDD is large enough, the problem can be solved in polynomial time by solvingm (m = 2 in this paper) single machine problems [30].Formally, there is a quantitative procedure to decide if a CDD is restricted or unrestricted for the single machine problem. In this paper, such procedure will be extended to theE/T JSSP over a CDD with two machines.Initially, for theE/T single machine problem, Kanet [1] assumed that CDD≥∑j=1npj, where pj is the processing time for jobj so that the problem can be solved optimally by using his algorithm SCHED. Later, Bagchi et al. [4] showed that Kanet’s algorithm is able to reach optimal solutions under the weaker assumption that the CDD ≥ Δ, where(3)Δ=p1+p3+⋯+pn,ifnisodd,p2+p4+⋯+pn,ifniseven,p1≤p3≤⋯≤pn.For a CDD in a two-machine JSSP to be unrestricted, two conditions must hold. First, the remaining time to process the last operations on each machine must be enough to apply the SCHED algorithm [1] as if each machine is an unrestricted single machine problem. Second, the completion time of each job’s first operation on its corresponding machine has to be less than or equal to the starting time of its subsequent last operation. This starting time is given by the SCHED algorithm. The second condition is equivalent to finding a schedule for each single machine problem where no jobs are tardy.In order to minimize the deviation over the CDD for all the jobs, the first operations of each job should have priority on each machine in order to allow the subsequent operations to be processed. The set of first operations and the set containing the last operations to be scheduled on each machine before the CDD compete for the time available within the interval fromt = 0 tot = CDD. If the CDD is loose enough, say if CDD ≥ PT, where(4)PT=∑i=12∑j=1npij,where pij is the processing time for the operation of jobj to be performed on machinei withi = 1, 2, then, the SCHED algorithm can be applied to the two machines and an optimal solution will be obtained. The closer the CDD to t=0 the tighter (i.e., more restricted) the schedule. This fact can be used to define whether the CDD is restricted or not. LetM 1 = set with jobs to be finished on machine 1,M 2 = set with jobs to be finished on machine 2,M 1 = n1 = number of jobs to be finished on machine 1,M 2 = n2 = number of jobs to be finished on machine 2.Also, let(5)Δ1=p11+p13+⋯+p1n1,ifn1isodd,p12+p14+⋯+p1n1,ifn1iseven,Δ2=p21+p23+⋯+p2n2,ifn2isodd,p22+p24+⋯+p2n2,ifn2iseven,where(6)p11≤p12≤⋯≤p1n1,p21≤p22≤⋯≤p2n2.Finally, let(7)F1=∑j∈M1Cp1j,F2=∑j∈M2Cp2j,where M1C is the complement of M1 and M2C is the complement of M2.Definition 1.
A CDD is unrestricted if CDD ≥max{F1+Δ1,F2+Δ2} and the number of tardy jobs in sets M1C and M2C are equal to zero.Discussion. If max{F1+Δ1,F2+Δ2} = F1 + Δ1, let B1={i=1,1≤j≤n,j∈M1∣C1j≤CDD}, where C1j is the completion time of the jobs with their last operation on machine 1 and to be completed before or on CDD. Similarly, let A1={i=1,1≤j≤n,j∈M1∣C1j>CDD}, where C1j is the completion time of the jobs with their last operation on machine 1 and to be completed after CDD and Δ1 is the summation of processing times of the jobs in B1. The optimal schedule for the machine 1 can be obtained by applying Kanet’s SCHED algorithm to the jobs in sets A1 and B1. The starting times of the jobs in sets A1 and B1 provide the due dates for their first operations to be processed on machine 2 (i.e., jobs in set M2C). The jobs whose first operation must be performed on machine 1, jobs in M1C, are processed before the jobs in B1 without interfering with the optimal schedule since CDD≥F1+Δ1.In order to find out if the number of tardy jobs inM1C is equal to zero, the earliest due date (EDD) rule needs to be applied to jobs in M1C. If an EDD sequence yields either zero or one tardy job, then it minimizes the number of tardy jobs [38].LetB2={i=2,1≤j≤n,j∈M2∣C2j≤CDD}, where C2j is the completion time of the jobs with their last operation on machine 2 to be completed before or on the CDD and Δ2 is the summation of processing times of the jobs in B2. Since F2+Δ2≤F1+Δ1, jobs to be finished on machine 2 can be optimally scheduled by applying Kanet’s SCHED algorithm to the jobs in sets A2 and B2, where A2 is defined similarly to A1. In the same way, the starting times of the jobs in sets A2 and B2 provide the due dates for their first operations to be processed on machine 1 (i.e., jobs in set M1C). The jobs whose first operation must be performed on machine 2, jobs in M2C, are performed before the jobs in B2 without interfering with the optimal schedule. Also, it is possible to find whether the number of tardy jobs in M2C is equal to zero by applying the EDD rule to jobs in M2C.The same reasoning can be applied ifmax{F1+Δ1, F2+Δ2} = F2+Δ2. Tables 1 and 2 show the processing times and the operation-machine assignment for a seven-job example. Figure 1 illustrates the optimal solution for this example when the CDD is unrestricted and equal to 30. In this case max{F1+Δ1, F2+Δ2}=max{8+13,20+10} = F2+Δ2 = 30. Note that if the CDD > 30, the problem is still unrestricted.Table 1
Processing times.
Job Processing time for first operation Processing time for second operation 1 9 3 2 2 7 3 1 4 4 6 2 5 2 3 6 4 10 7 4 3Table 2
Operation-machine assignment.
Job First operation at machine Second operation at machine 1 2 1 2 1 2 3 2 1 4 2 1 5 1 2 6 2 1 7 1 2Figure 1
Example optimal schedule for the unrestricted version.Definition 2.
A CDD is semirestricted if CDD ≥min{F1+Δ1, F2+Δ2} and CDD < max{F1+Δ1, F2+Δ2} and the number of tardy jobs in the sets M1C and M2C are equal to zero.Discussion. If max{F1+Δ1, F2+Δ2} = F2+Δ2, then min{F1+Δ1, F2+Δ2} = F1+Δ1. B1 and B2 are as in Definition 1. Hence, Δ1 and Δ2 are the summation of processing times of the jobs in B1 and B2, respectively. Given CDD≥F1+Δ1, in an optimal schedule jobs in M1C are performed before the jobs in B1 without interference with the jobs in B1. The optimal schedule for machine 1 can be obtained by applying Kanet’s SCHED algorithm to the jobs in B1 and A1. The starting times of the jobs in sets A1 and B1 provide the due dates for their first operations to be processed on machine 2 (i.e., jobs in the set M2C), which are processed before the jobs in B2. But given that CDD<F2+Δ2, jobs in M2 cannot be optimally scheduled by using the SCHED algorithm; instead this problem needs to be treated as a single machine problem with a restricted CDD, which can be optimally solved by using the dynamic programming (DP) procedures proposed by Hall et al. [6]. The starting times of the jobs in M2 given by the optimal solution provide the due dates for their first operations to be processed on machine 1 (i.e., jobs in the set M1C). The jobs whose first operation must be performed on machine 1, jobs in M1C, are processed before the jobs in B1 without interfering with the optimal schedule since CDD≥F1+Δ1. Similar to the unrestricted case, jobs in M1C and M2C need to be sequenced by using the EDD rule to check if the number of tardy jobs is equal to zero. If both sequences yield zero tardy jobs then the problem is semirestricted. Following the same numeric example, Figure 2 describes the case when the CDD is equal to 23 which is greater than min{F1+Δ1,F2+Δ2}=F1+Δ1=21 and is less than max{F1+Δ1, F2+Δ2} = F2+Δ2 = 30.Figure 2
Example optimal schedule for the semirestricted version.In this sense, a CDD is semirestricted when the optimal schedule of either one of the machines can be obtained by using Kanet’s SCHED algorithm. The optimal schedule for the other machine has different features, and so the SCHED algorithm will not be able to find it. Instead, the DP procedures developed by Hall et al. [6] need to be used to find the optimal schedule. This procedure is extended to the problem studied here in the next section.Definition 3.
A CDD is restricted if neither Definition1’s conditions nor Definition 2’s conditions hold.Discussion. If CDD<min{F1+Δ1,F2+Δ2}, let min{F1+Δ1, F2+Δ2}=F1+Δ1, and B1={i=1,1≤j≤n,j∈M1∣C1j≤CDD}, where C1j is the completion time of the jobs with their last operation on machine 1. Hence, Δ1 is the summation of processing times of the jobs in B1. Since CDD<F1+Δ1, there is no way to optimally schedule jobs in M1 without modifying the starting times of the jobs in M1C (the first operations of jobs in M2). Hence, a tradeoff between jobs in M1C and jobs in B1 must be made. The jobs in M1C (those with their first operation to be performed on machine 1) interfere with the optimal schedule on this machine. On the other hand, if at least one of the jobs in M1C is delayed, this delay interferes with the optimal schedule on machine 2. The same reasoning can be applied if min{F1+Δ1, F2+Δ2} = F2+Δ2. Following the same numeric example, Figure 3 illustrates the case when the CDD = 15 which is less than min{F1+Δ1, F2+Δ2}=F1+Δ1=21.Figure 3
Example final scheduled for the restricted version.Additionally, if there is at least one tardy job in the cases given in Definitions1 or 2, then the CDD is also considered restricted since precedence constraints for at least one job (i.e., the tardy job) do not hold.Next, optimality conditions for the unrestricted and semirestricted case are presented. Also, two properties of the optimal solution for the restricted case are proved and used to construct approximate solutions.


## 3. Optimality Conditions

Optimal solutions for the two-machineE/T JSSP with restricted CDD are difficult to characterize. In this paper, optimal solutions will be defined when the CDD is unrestricted and semirestricted. Approximate solutions, obtained by a heuristic procedure, will be defined when the CDD is restricted.


### 3.1. Unrestricted CDD

If the CDD is unrestricted as described in Definition1, the optimal solution can be found by using Kanet’s SCHED procedure on each machine. The properties of the optimal schedule as defined in Kanet [1] will be extended for our use.Property 1.
There is no idle time between jobs in setsM1 and M2.Property 2.
The jobs in bothB1 and B2 are sequenced by longest processing time first (LPT).Property 3.
The last jobs inB1 and B2 are completed at time t=CDD.Property 4.
LetA1 and A2 represent an ordered set of jobs pertaining, respectively, to M1 and M2 to be scheduled without inserted idle time such that the first job in both A1 and A2 starts at time t=CDD. In an optimal schedule, jobs in both A1 and A2 are sequenced by shortest processing time (SPT) first.Property 5.
Ifn1 is even then B1=A1. If n1 is odd then B1=A1+1. If n2 is even then B2=A2. If n2 is odd then B2=A2+1.Property 6.
There is a one-to-one mapping of the jobs in bothA1 and A2 onto the jobs in B1 and B2 such that k1∈A1 and k2∈A2 and j1∈B1 and j2∈B2⇒p1k1≤p1j1 and p2k2≤p2j2.The proofs of these properties and the proof that SCHED yields optimal solutions can be easily extended from Kanet [1] and Definition 1. It is important to note that SCHED runs in polynomial time as discussed by Kanet [1]. Figure 1 shows the optimal schedule of the same numerical example when the CDD is unrestricted.


### 3.2. Semirestricted CDD

If the CDD is semirestricted as described in Definition2, the optimal solution can be found by using Kanet’s SCHED procedure on the machine with min{F1+Δ1,F2+Δ2}. The optimal solution in this machine preserves the properties given for the unrestricted case. For the other machine, some properties must be defined in order to characterize the optimal solution. The properties of the optimal schedule as defined by Hall et al. [6] will be extended for our use.Lett1∗ or t2∗ denote the starting times in an optimal schedule of the first job processed on either M1 or M2, respectively, corresponding to the machine where max{F1+Δ1,F2+Δ2} holds.Also, defineE12={i=1(2),1≤j≤n∣C1(2)j<CDD}, E12′={i=1(2),1≤j≤n∣C1(2)j≤CDD}, T1(2)={i=1(2),1≤j≤n∣C12j-p1(2)j≥CDD}, and T12′={i=1(2),1≤j≤n∣C1(2)j>CDD}.Property 1.
There exists at least one of the following:An optimal schedule with eithert1∗=F1 or t2∗=F2.An optimal schedule withC1(2)a=CDD, where a is a job with its last operation on machine 1(2) starting before CDD and completing at CDD or later.Property 2.
In an optimal schedule, the jobs inE12′ are in LPT order, and the jobs in T1(2) are in SPT order.Property 3.
Each optimal schedule is weakly V-shaped. A weakly V-shaped schedule means a job does not necessarily end at the CDD.Definition 4.
On machine1(2) a schedule is early V-Shaped (EVS) if p1(2)a≤p1(2)tmin.Definition 5.
On machine1(2) a schedule is tardy V-Shaped (TVS) if p1(2)a≤p1(2)emin, where emin=min{p1(2)j∈E12′}, and tmin=min{p1(2)j∈T1(2)}.Property 4.
Ift1∗=F1, then E1≥T1-1 or if t2∗=F2, then E2≥T2-1.Property 5.
ConsiderE12≤T12+1.Property 6.
IfC1(2)a=CDD, then ∑j∈E1(2)′p1(2)j≤∑j∈T1(2)p1(2)j+2p1(2)s, where job s is the first job scheduled on machine 1(2).The proofs of these properties can be extended from Hall et al. [6] and Definition 2.Based on these properties, the DP procedure can be introduced to find the optimal solution examining all EVS and TVS schedules ift12∗=F1(2) by using EVS and TVS procedures described by Hall et al. [6]. If t12∗>F1(2), then it is possible to assume that C1(2)a=CDD and the Nosplit procedure described by Hall and Posner [5] can be extended to find an optimal schedule in which a job is completed at CDD. By jointly using these procedures, an optimal solution can be found for the two-machine JSSP with a semirestricted CDD. More detail on these procedures will be presented in the next section. It is important to note that, in the general case, the dynamic programming approach proposed by Hall et al. [6] for the single machine restricted case runs in pseudopolynomial time. Figure 2 shows the optimal schedule of the same previous numerical example when the CDD is semirestricted.


### 3.3. Restricted CDD

To characterize the optimal solution when the CDD is restricted is difficult. Hence, two properties are defined in order to develop a heuristic algorithm to obtain approximate solutions for the two-machine JSSP.DefineI1 = the set of jobs to be finished on machine 1 and to be scheduled around the restricted CDD. I2 = the set of jobs to be finished on machine 2 and to be scheduled around the restricted CDD.Clearly,I1⊆M1 and I2⊆M2.Property 1.
Jobs inI1 and I2 are scheduled without idle time.Proof.
By contradiction and similar to the approach by Baker [38], assume that there exists an optimal scheduleS with an idle interval of lengtht between consecutive jobsa andb, withb followinga;a, b∈I1 (I2), and the predecessors ofa andb are already scheduled at machine 2(1). If joba is early (C1(2)a<CDD), then the total penalty cost can be reduced by shifting joba (and any jobs that precedes it) later by an amount Δt, where Δt≤min(t,CDD-C1(2)a) without affecting the feasibility of S. Denoting the values after the shift with primes, it follows that T12k′=T1(2)k and T12k′≤T1(2)k strictly for at least one job. Similarly, if jobb is tardy (C1(2)b>CDD), then the total penalty cost can be reduced by shifting jobb (and any jobs that follows it) earlier by an amountΔt, where Δt≤min(t,C1(2)b-CDD) without affecting the feasibility ofS. Hence, it follows that E12k′=E1(2)k and T12k′≤T1(2)k strictly for at least one job. Since any schedule must have either joba early or jobb tardy, then scheduleS can be improved, and therefore, it cannot be optimal.Property 2.
The optimal schedule for the jobs inI1 and I2 is weakly V-shaped, where a scheduleS is weakly V-shaped if all jobs completed before the CDD are ordered according to LPT and all jobs that begin their processing after the CDD ordered according to SPT.Proof.
By contradiction and similar to the approach in Baker [38], assumeS denotes an optimal schedule in which some adjacent pair of early jobs in I1(2) is not in LPT order. Then a pairwise interchange of these two jobs will reduce the total earliness penalty and leave the tardiness penalty unchanged on machine 1(2) without affecting the feasibility ofS. Similarly, ifS is an optimal schedule containing an adjacent pair of jobs that starts late in I1(2) and that violates the SPT order, then an adjacent pairwise interchange will reduce the total tardiness penalty and leave the total earliness penalty unchanged on machine 1(2). In either case,S cannot be an optimal schedule.Once the jobs to be included inI1 and I2 have been defined, there are still two questions to be answered. First, in an optimal schedule, is there some job that must be completed exactly at t=CDD? It was shown by Hall et al. [6] for the single machine case with a restricted CDD that this is not necessarily true. Second, in an optimal schedule, which jobs are early and which ones are tardy? Figure 3 shows an approximate schedule of the numerical example when the CDD is restricted.In order to find an approximate solution for the restricted version of the problem addressed in this paper,Restricted Heuristic, a heuristic procedure based on Properties 1 and 2 is proposed. By iteratively eliminating the job with the longest processing time in either machine 1 or machine 2, sets I1 and I2 are defined. This procedure tries to reduce a restricted problem to the semirestricted version in order to apply the SCHED, EVS, TVS, and Nosplit procedures. Given the jobs removed are going to be tardy anyway, the SPT rule is applied in order to minimize their tardiness. Each time a remaining tardy job is scheduled, an improvement procedure tries to look for early slots of time in the current schedule in order to decrease the tardiness cost.Restricted Heuristic reduces the problem to a semirestricted one in order to apply the dynamic programming approach proposed by Hall et al. [6] for the single machine restricted case; hence, it runs in pseudopolynomial time. It is important to note thatRestricted Heuristic does not guarantee an optimal solution.


## 3.1. Unrestricted CDD

If the CDD is unrestricted as described in Definition1, the optimal solution can be found by using Kanet’s SCHED procedure on each machine. The properties of the optimal schedule as defined in Kanet [1] will be extended for our use.Property 1.
There is no idle time between jobs in setsM1 and M2.Property 2.
The jobs in bothB1 and B2 are sequenced by longest processing time first (LPT).Property 3.
The last jobs inB1 and B2 are completed at time t=CDD.Property 4.
LetA1 and A2 represent an ordered set of jobs pertaining, respectively, to M1 and M2 to be scheduled without inserted idle time such that the first job in both A1 and A2 starts at time t=CDD. In an optimal schedule, jobs in both A1 and A2 are sequenced by shortest processing time (SPT) first.Property 5.
Ifn1 is even then B1=A1. If n1 is odd then B1=A1+1. If n2 is even then B2=A2. If n2 is odd then B2=A2+1.Property 6.
There is a one-to-one mapping of the jobs in bothA1 and A2 onto the jobs in B1 and B2 such that k1∈A1 and k2∈A2 and j1∈B1 and j2∈B2⇒p1k1≤p1j1 and p2k2≤p2j2.The proofs of these properties and the proof that SCHED yields optimal solutions can be easily extended from Kanet [1] and Definition 1. It is important to note that SCHED runs in polynomial time as discussed by Kanet [1]. Figure 1 shows the optimal schedule of the same numerical example when the CDD is unrestricted.


## 3.2. Semirestricted CDD

If the CDD is semirestricted as described in Definition2, the optimal solution can be found by using Kanet’s SCHED procedure on the machine with min{F1+Δ1,F2+Δ2}. The optimal solution in this machine preserves the properties given for the unrestricted case. For the other machine, some properties must be defined in order to characterize the optimal solution. The properties of the optimal schedule as defined by Hall et al. [6] will be extended for our use.Lett1∗ or t2∗ denote the starting times in an optimal schedule of the first job processed on either M1 or M2, respectively, corresponding to the machine where max{F1+Δ1,F2+Δ2} holds.Also, defineE12={i=1(2),1≤j≤n∣C1(2)j<CDD}, E12′={i=1(2),1≤j≤n∣C1(2)j≤CDD}, T1(2)={i=1(2),1≤j≤n∣C12j-p1(2)j≥CDD}, and T12′={i=1(2),1≤j≤n∣C1(2)j>CDD}.Property 1.
There exists at least one of the following:An optimal schedule with eithert1∗=F1 or t2∗=F2.An optimal schedule withC1(2)a=CDD, where a is a job with its last operation on machine 1(2) starting before CDD and completing at CDD or later.Property 2.
In an optimal schedule, the jobs inE12′ are in LPT order, and the jobs in T1(2) are in SPT order.Property 3.
Each optimal schedule is weakly V-shaped. A weakly V-shaped schedule means a job does not necessarily end at the CDD.Definition 4.
On machine1(2) a schedule is early V-Shaped (EVS) if p1(2)a≤p1(2)tmin.Definition 5.
On machine1(2) a schedule is tardy V-Shaped (TVS) if p1(2)a≤p1(2)emin, where emin=min{p1(2)j∈E12′}, and tmin=min{p1(2)j∈T1(2)}.Property 4.
Ift1∗=F1, then E1≥T1-1 or if t2∗=F2, then E2≥T2-1.Property 5.
ConsiderE12≤T12+1.Property 6.
IfC1(2)a=CDD, then ∑j∈E1(2)′p1(2)j≤∑j∈T1(2)p1(2)j+2p1(2)s, where job s is the first job scheduled on machine 1(2).The proofs of these properties can be extended from Hall et al. [6] and Definition 2.Based on these properties, the DP procedure can be introduced to find the optimal solution examining all EVS and TVS schedules ift12∗=F1(2) by using EVS and TVS procedures described by Hall et al. [6]. If t12∗>F1(2), then it is possible to assume that C1(2)a=CDD and the Nosplit procedure described by Hall and Posner [5] can be extended to find an optimal schedule in which a job is completed at CDD. By jointly using these procedures, an optimal solution can be found for the two-machine JSSP with a semirestricted CDD. More detail on these procedures will be presented in the next section. It is important to note that, in the general case, the dynamic programming approach proposed by Hall et al. [6] for the single machine restricted case runs in pseudopolynomial time. Figure 2 shows the optimal schedule of the same previous numerical example when the CDD is semirestricted.


## 3.3. Restricted CDD

To characterize the optimal solution when the CDD is restricted is difficult. Hence, two properties are defined in order to develop a heuristic algorithm to obtain approximate solutions for the two-machine JSSP.DefineI1 = the set of jobs to be finished on machine 1 and to be scheduled around the restricted CDD. I2 = the set of jobs to be finished on machine 2 and to be scheduled around the restricted CDD.Clearly,I1⊆M1 and I2⊆M2.Property 1.
Jobs inI1 and I2 are scheduled without idle time.Proof.
By contradiction and similar to the approach by Baker [38], assume that there exists an optimal scheduleS with an idle interval of lengtht between consecutive jobsa andb, withb followinga;a, b∈I1 (I2), and the predecessors ofa andb are already scheduled at machine 2(1). If joba is early (C1(2)a<CDD), then the total penalty cost can be reduced by shifting joba (and any jobs that precedes it) later by an amount Δt, where Δt≤min(t,CDD-C1(2)a) without affecting the feasibility of S. Denoting the values after the shift with primes, it follows that T12k′=T1(2)k and T12k′≤T1(2)k strictly for at least one job. Similarly, if jobb is tardy (C1(2)b>CDD), then the total penalty cost can be reduced by shifting jobb (and any jobs that follows it) earlier by an amountΔt, where Δt≤min(t,C1(2)b-CDD) without affecting the feasibility ofS. Hence, it follows that E12k′=E1(2)k and T12k′≤T1(2)k strictly for at least one job. Since any schedule must have either joba early or jobb tardy, then scheduleS can be improved, and therefore, it cannot be optimal.Property 2.
The optimal schedule for the jobs inI1 and I2 is weakly V-shaped, where a scheduleS is weakly V-shaped if all jobs completed before the CDD are ordered according to LPT and all jobs that begin their processing after the CDD ordered according to SPT.Proof.
By contradiction and similar to the approach in Baker [38], assumeS denotes an optimal schedule in which some adjacent pair of early jobs in I1(2) is not in LPT order. Then a pairwise interchange of these two jobs will reduce the total earliness penalty and leave the tardiness penalty unchanged on machine 1(2) without affecting the feasibility ofS. Similarly, ifS is an optimal schedule containing an adjacent pair of jobs that starts late in I1(2) and that violates the SPT order, then an adjacent pairwise interchange will reduce the total tardiness penalty and leave the total earliness penalty unchanged on machine 1(2). In either case,S cannot be an optimal schedule.Once the jobs to be included inI1 and I2 have been defined, there are still two questions to be answered. First, in an optimal schedule, is there some job that must be completed exactly at t=CDD? It was shown by Hall et al. [6] for the single machine case with a restricted CDD that this is not necessarily true. Second, in an optimal schedule, which jobs are early and which ones are tardy? Figure 3 shows an approximate schedule of the numerical example when the CDD is restricted.In order to find an approximate solution for the restricted version of the problem addressed in this paper,Restricted Heuristic, a heuristic procedure based on Properties 1 and 2 is proposed. By iteratively eliminating the job with the longest processing time in either machine 1 or machine 2, sets I1 and I2 are defined. This procedure tries to reduce a restricted problem to the semirestricted version in order to apply the SCHED, EVS, TVS, and Nosplit procedures. Given the jobs removed are going to be tardy anyway, the SPT rule is applied in order to minimize their tardiness. Each time a remaining tardy job is scheduled, an improvement procedure tries to look for early slots of time in the current schedule in order to decrease the tardiness cost.Restricted Heuristic reduces the problem to a semirestricted one in order to apply the dynamic programming approach proposed by Hall et al. [6] for the single machine restricted case; hence, it runs in pseudopolynomial time. It is important to note thatRestricted Heuristic does not guarantee an optimal solution.


## 4. Dynamic Programming Algorithm for the Two-Machine JSSP

The algorithm JSSPET presented here uses a DP algorithm to find optimal solutions for the two-machineE/T JSSP when the CDD is semirestricted. This algorithm partitions the solution space into schedules with either t1∗=F1 or t2∗=F2 and those with either t1∗>F1 or t2∗>F2. In the first case, jobs either in M1 or M2 are scheduled in the interval [F1,F1+P1] or [F2,F2+P2], where P1=∑j∈M1p1j and P2=∑j∈M2p2j. Based on Property 3, any optimal schedule is either EVS or TVS, and soEVS (TVS) procedure discussed next will find optimal EVS (TVS) schedules which is completed at either F1+P1 or F2+P2. In the second case, suppose that either t1∗>F1 or t2∗>F2 and based on Property 1, it is possible to assume that either C1a=CDD or C2a=CDD so thatNosplit procedure discussed later will find an optimal schedule in which a job is completed at CDD. Finally, the lower cost offered by the three procedures is an optimal schedule. All three procedures make use of Properties 2 and 3 (V-shaped structure).Procedures EVS and TVS consider jobs in nonincreasing order. From Property3, job n1 (to be finished on machine 1) either starts at F1 or ends at F1+P1, and job n2 (to be finished on machine 2) either starts at F2 or ends F2+P2. The total processing time of previously scheduled jobs which finish before CDD inEVS and after CDD inTVS procedures is stored.Nosplit procedure considers jobs in nondecreasing order.


### 4.1. Procedure EVS

Letfk(a1) = the minimum cost to schedule jobs n1,n1-1,…,n1-k+1 (similarly n2, n2-1,…,n2-k+1) provided that the latest job scheduled which finished at or before CDD finishes at time CDD-a1, a1≥0 (similarly CDD-a2, a2≥0), and the earliest job scheduled which finishes after CDD starts at time ∑j=1n1-kp1j-a1+CDD (similarly ∑j=1n2-kp2j-a2+CDD). That is, the latest job finishes at F1+P1 (similarly F2+P2).Recurrence relation is as follows:(8)fk+1a1=mina1+fka1+p1n1-k,∑j=1n1-kp1j-a1+fka1,if∑j=1n1-kp1j>a1,a1+p1n1-k≤CDD,a1+fka1+p1n1-k,if∑j=1n1-kp1j≤a1,a1+p1n1-k≤CDD,+∞,otherwise.Boundary condition is as follows:(9)f0a1=0,fora1=CDD,f0a1=+∞,fora1≠CDD.Minimum cost schedule is defined by(10)zσEVS∗=min0≤a1≤CDDfna1.


### 4.2. Procedure TVS

Letgk(m1) = the minimum cost to schedule jobs n1,n1-1,…,n1-k+1 (similarly n2,n2-1,…,n2-k+1) provided that the earliest job scheduled which starts at or after CDD starts at time CDD+m1, m1≥0 (similarly CDD-m2, m2≥0), and the latest job scheduled which starts before CDD finishes at time CDD+m1-∑j=1n1-kp1j (similarly CDD+m2-∑j=1n2-kp2j). That is, the earliest such a job starts is at F1 (similarly F2).Recurrence relation is as follows:(11)gk+1m1=min∑j=1n1-k-1p1j-m1+gkm1,m1+p1n1-k+gkm1+p1n1-k,if∑j=1n1-kp1j>m1,m1+p1n1-k≤P1-CDD,m1+p1n1-k+gkm1+p1n1-k,if∑j=1n1-kp1j≤m1,m1+p1n1-k≤P1-CDD,+∞,otherwise.Boundary condition is as follows:(12)g0m1=0,form1=P1-CDD,g0m1=+∞,form1≠P1-CDD.Minimum cost schedule is defined by(13)zσTVS∗=min0≤m1≤P1-CDDgnm1.


### 4.3. Procedure Nosplit

Lethk(e1) = the minimum cost to schedule jobs 1,2,…,k for either M1 or M2 without the CDD splitting any job, given that the total processing time of jobs scheduled early (or on time) is either e1 or e2.Recurrence relation is as follows:(14)fk+1a1=mine1-p1k+1+hke1+p1k+1,∑j=1k+1p1j-e1+hke1,ife1≥p1k+1,∑j=1k+1p1j-e1+hke1,otherwise.Boundary condition is as follows:(15)h0e1=0,ife1=0,h0e1=+∞,ife1≠0.Minimum cost schedule is defined by(16)zσNosplit∗=min0≤e1≤CDDhne1.In all of the three procedures, the first alternative in the recurrence relation represents the cost of scheduling the next job as early as possible and the second one, similarly, as late as possible. Since in theTVS procedure an early job may finish after the CDD, there is a need for the absolute value in the first equation on its recurrence relation.


### 4.4. JSSPET Algorithm

In order to solve the two-machineE/T JSSP over a CDD, the three cases of the due date must be considered. The JSSPET algorithm decides the type of CDD (restricted, semirestricted, or restricted) and then applies the appropriate procedure. When the CDD is unrestricted, the JSSPET uses the SCHED procedure [1] to find the optimal solution for both machines. When the CDD is semirestricted, JSSPET jointly uses the SCHED procedure to find the optimal solution for one of the machines (the one with min{F1+Δ1,F2+Δ2}), and the EVS, TVS, and Nosplit procedures to find the optimal for the other machine. Finally, when the CDD is restricted, JSSPET usesRestricted Heuristic (explained earlier) to find approximate solutions. This heuristic procedure reduces a restricted problem to the semirestricted version by iteratively removing one job at the time. Once the problem is reduced to its semirestricted version, the SCHED, EVS, TVS, and Nosplit procedures are applied. Since the jobs removed are going to be tardy anyway, the SPT rule is applied in order to minimize their tardiness. Each time a removed job is scheduled, an improvement procedure runs in search for early time slots in the current schedule to decrease the tardiness cost. The pseudocode for JSSPET is given next.Algorithm JSSPET CalculateF1, F2, Δ1, Δ2 Apply SCHED procedure toM1 Apply SCHED procedure toM2 CalculateT1 = Number of tardy jobs in M1C CalculateT2 = Number of tardy jobs in M2C IfCDD≥max{F1+Δ1,F2+Δ2} and T1=0 and T2=0 then
Optimal schedule is given by SCHED procedure on both machines Schedule first operations on machine 1 and machine 2 by using EDD rule. Stop. Else
Apply SCHED to machine wheremin{F1+Δ1,F2+Δ2} holds Apply EVS to the other machine Apply TVS to the other machine Apply Nosplit to the other machine Solution for the other machine ismin{EVS,TVS,Nosplit} CalculateT1 = Number of tardy jobs on M1C CalculateT2 = Number of tardy jobs on M2C IfCDD<max{F1+Δ1,F2+Δ2} and CDD≥min{F1+Δ1,F2+Δ2} and T1=0 and T2=0 then
Optimal schedule is given by SCHED andmin{EVS,TVS,Nosplit} Schedule first operations on machine 1 and machine 2 by using EDD rule. Stop. Else
Apply Restricted Heuristic End If End If End Algorithm


## 4.1. Procedure EVS

Letfk(a1) = the minimum cost to schedule jobs n1,n1-1,…,n1-k+1 (similarly n2, n2-1,…,n2-k+1) provided that the latest job scheduled which finished at or before CDD finishes at time CDD-a1, a1≥0 (similarly CDD-a2, a2≥0), and the earliest job scheduled which finishes after CDD starts at time ∑j=1n1-kp1j-a1+CDD (similarly ∑j=1n2-kp2j-a2+CDD). That is, the latest job finishes at F1+P1 (similarly F2+P2).Recurrence relation is as follows:(8)fk+1a1=mina1+fka1+p1n1-k,∑j=1n1-kp1j-a1+fka1,if∑j=1n1-kp1j>a1,a1+p1n1-k≤CDD,a1+fka1+p1n1-k,if∑j=1n1-kp1j≤a1,a1+p1n1-k≤CDD,+∞,otherwise.Boundary condition is as follows:(9)f0a1=0,fora1=CDD,f0a1=+∞,fora1≠CDD.Minimum cost schedule is defined by(10)zσEVS∗=min0≤a1≤CDDfna1.


## 4.2. Procedure TVS

Letgk(m1) = the minimum cost to schedule jobs n1,n1-1,…,n1-k+1 (similarly n2,n2-1,…,n2-k+1) provided that the earliest job scheduled which starts at or after CDD starts at time CDD+m1, m1≥0 (similarly CDD-m2, m2≥0), and the latest job scheduled which starts before CDD finishes at time CDD+m1-∑j=1n1-kp1j (similarly CDD+m2-∑j=1n2-kp2j). That is, the earliest such a job starts is at F1 (similarly F2).Recurrence relation is as follows:(11)gk+1m1=min∑j=1n1-k-1p1j-m1+gkm1,m1+p1n1-k+gkm1+p1n1-k,if∑j=1n1-kp1j>m1,m1+p1n1-k≤P1-CDD,m1+p1n1-k+gkm1+p1n1-k,if∑j=1n1-kp1j≤m1,m1+p1n1-k≤P1-CDD,+∞,otherwise.Boundary condition is as follows:(12)g0m1=0,form1=P1-CDD,g0m1=+∞,form1≠P1-CDD.Minimum cost schedule is defined by(13)zσTVS∗=min0≤m1≤P1-CDDgnm1.


## 4.3. Procedure Nosplit

Lethk(e1) = the minimum cost to schedule jobs 1,2,…,k for either M1 or M2 without the CDD splitting any job, given that the total processing time of jobs scheduled early (or on time) is either e1 or e2.Recurrence relation is as follows:(14)fk+1a1=mine1-p1k+1+hke1+p1k+1,∑j=1k+1p1j-e1+hke1,ife1≥p1k+1,∑j=1k+1p1j-e1+hke1,otherwise.Boundary condition is as follows:(15)h0e1=0,ife1=0,h0e1=+∞,ife1≠0.Minimum cost schedule is defined by(16)zσNosplit∗=min0≤e1≤CDDhne1.In all of the three procedures, the first alternative in the recurrence relation represents the cost of scheduling the next job as early as possible and the second one, similarly, as late as possible. Since in theTVS procedure an early job may finish after the CDD, there is a need for the absolute value in the first equation on its recurrence relation.


## 4.4. JSSPET Algorithm

In order to solve the two-machineE/T JSSP over a CDD, the three cases of the due date must be considered. The JSSPET algorithm decides the type of CDD (restricted, semirestricted, or restricted) and then applies the appropriate procedure. When the CDD is unrestricted, the JSSPET uses the SCHED procedure [1] to find the optimal solution for both machines. When the CDD is semirestricted, JSSPET jointly uses the SCHED procedure to find the optimal solution for one of the machines (the one with min{F1+Δ1,F2+Δ2}), and the EVS, TVS, and Nosplit procedures to find the optimal for the other machine. Finally, when the CDD is restricted, JSSPET usesRestricted Heuristic (explained earlier) to find approximate solutions. This heuristic procedure reduces a restricted problem to the semirestricted version by iteratively removing one job at the time. Once the problem is reduced to its semirestricted version, the SCHED, EVS, TVS, and Nosplit procedures are applied. Since the jobs removed are going to be tardy anyway, the SPT rule is applied in order to minimize their tardiness. Each time a removed job is scheduled, an improvement procedure runs in search for early time slots in the current schedule to decrease the tardiness cost. The pseudocode for JSSPET is given next.Algorithm JSSPET CalculateF1, F2, Δ1, Δ2 Apply SCHED procedure toM1 Apply SCHED procedure toM2 CalculateT1 = Number of tardy jobs in M1C CalculateT2 = Number of tardy jobs in M2C IfCDD≥max{F1+Δ1,F2+Δ2} and T1=0 and T2=0 then
Optimal schedule is given by SCHED procedure on both machines Schedule first operations on machine 1 and machine 2 by using EDD rule. Stop. Else
Apply SCHED to machine wheremin{F1+Δ1,F2+Δ2} holds Apply EVS to the other machine Apply TVS to the other machine Apply Nosplit to the other machine Solution for the other machine ismin{EVS,TVS,Nosplit} CalculateT1 = Number of tardy jobs on M1C CalculateT2 = Number of tardy jobs on M2C IfCDD<max{F1+Δ1,F2+Δ2} and CDD≥min{F1+Δ1,F2+Δ2} and T1=0 and T2=0 then
Optimal schedule is given by SCHED andmin{EVS,TVS,Nosplit} Schedule first operations on machine 1 and machine 2 by using EDD rule. Stop. Else
Apply Restricted Heuristic End If End If End Algorithm


## 5. Computational Experiments

Sets of problems with 2 machines, 5, 6, 7, 8, 10, 20, 50, 100, and 500 jobs, with 30 problem instances per problem size, were generated. The processing times were generated from a discrete uniform distributionU(1, 100) and the jobs routes were obtained from another discrete uniform distribution U(1,m) wherem is the number of machines (two in our case). Similar to most random numbers generators in use today, the processing times and jobs routes were generated by using random numbers coming from a linear congruential generator [39].The CDD for the unrestricted case is given by(17)CDD=maxF1+Δ1,F2+Δ2.For the semirestricted case, the CDD is chosen to be in the middle of the interval between min⁡F1+Δ1,F2+Δ2 and max⁡F1+Δ1,F2+Δ2 as given by (18)CDD=minF1+Δ1,F2+Δ2+0.5∗maxF1+Δ1,F2+Δ2-minF1+Δ1,F2+Δ2.Finally, for the restricted case, the CDD is given by (19)CDD=h∗minF1+Δ1,F2+Δ2,where h is the tightness factor, h∈[0,1), and it takes four possible values, h=0.7,0.8,0.9,0.95. x is the largest integer less than or equal to x.Considering the four cases of the restricted version, the single case of both the unrestricted and the semirestricted version, a total of9∗30∗6=1620 problem instances were solved.


## 6. Results

The results in Table3 show the average, standard deviation, and maximum computational solution times for each set of instances. The times are in seconds and exclude input and output time. Computational solution times increase approximately linearly with n for the unrestricted case and in proportion to n2 for the semirestricted case. These results confirm thatJSSPET algorithm finds optimal solutions for both the unrestricted and the semirestricted cases for large random instances of the problem within no more than 20 minutes. Such result is made possible by the new optimality conditions extended from the single machine problem provided in this paper and which enable us to prove the optimality of the dynamic programming procedure.Table 3
Computational times for the unrestricted and semirestricted cases.
Jobs Unrestricted Semirestricted Average (sec.) Deviation (sec.) Maximum (sec.) Average (sec.) Deviation (sec.) Maximum (sec.) n = 5 0.004 0.007 0.016 0.6230 1.1485 2.6698 n = 6 0.004 0.007 0.016 0.7674 1.2943 2.8778 n = 7 0.006 0.008 0.016 1.1335 1.5152 3.0914 n = 8 0.006 0.008 0.016 1.2123 1.6205 3.3062 n = 10 0.006 0.008 0.016 1.4929 1.8597 3.7322 n = 20 0.014 0.005 0.016 4.9724 1.9837 5.7373 n = 50 0.029 0.007 0.047 19.9488 5.5026 32.9513 n = 100 0.056 0.008 0.063 67.1799 9.2983 74.6444 n = 500 0.294 0.014 0.359 1299.8607 63.9390 1590.2551For restricted problems with 5, 6, 7, and 8 jobs, finding an optimal solution is not guaranteed, but when compared with optimal solutions obtained through a MILP formulation, it turned out the JSSPET algorithm found optimal solutions for about 30% to 40% of all the instances by applying theRestricted Heuristic.For restricted problems with 10 or more jobs, theJSSPET algorithm is evaluated based on how far its solutions are from a lower bound (LB). The LB used in this case is the optimal solution for the same instances but with a semirestricted CDD. Recall that a problem instance’s solution with a restricted CDD will always be larger than the same instance with unrestricted or semirestricted CDD. The closer the tightness factorh to one, the smaller the deviation from the LB (the semirestricted version). Also, as the number of jobs increases, the deviation from the LB decreases. Since the behavior of the optimal objective function value for the restricted version of the problem is unknown, using the solution of the semirestricted version as a LB for the restricted case tends to underestimate the performance of theJSSPET algorithm. Therefore, this LB needs to be used carefully and a better one needs to be found.


## 7. Conclusions

The earliness and tardiness problem is an important problem in machine scheduling involving nonregular measures of performance. In this work, a dynamic programming (DP) algorithm to deal with the two-machine job shop scheduling problem (JSSP) and a common due date (CDD) were presented. The CDD can be classified as unrestricted, restricted, or semirestricted depending on how large it is. Lauff and Werner [30] conjectured that the definition of the restrictedness of the CDD for a multimachine early/tardy job shop scheduling problem is a NP-hard problem. In this research, a pseudopolynomial procedure to define the class of restrictedness was presented for the two-machine E/T JSSP.Additionally, some properties for this problem as well as optimality conditions for the unrestricted and semirestricted case were extended from the single machine problem. Optimal solutions for the unrestricted and semirestricted case were obtained for problems with up to 500 jobs by using the SCHED algorithm and a dynamic programming algorithm, respectively. Two properties for the restricted case were proved and used to come up with a heuristic algorithm for the two machines problem with restricted CDD.Finally, through experiments, it was shown that theJSSPET algorithm could find optimal solutions for the unrestricted and semirestricted versions of the problem. Also, the proposed algorithm works well as a heuristic for the restricted case with large problems. However, there is room to improve the performance of theJSSPET algorithm through the development of optimality conditions for the restricted case and by introducing better lower bounds to better evaluate the performance of the heuristic.Future research involves extending this work to job shop scheduling problems with more than two machines.



---

*Source: 6591632-2016-11-23.xml*