Adjusting scheduling model with release and due dates in production planning

Abstract

Motivated by the conjecture that an interaction between scheduling and pre-scheduling phases in production planning may give certain benefits, we conduct a detailed study of the optimality conditions and dominance relations for a strongly NP-hard single-machine scheduling model when jobs have release and due-dates and the objective is to minimize maximum job lateness. By exploring the inherent structure of the problem, we establish the optimality conditions when the problem can be efficiently solved. We come to an NP-hard special case of the problem with only two possible job release times, that as we show allows stricter dominance rules and optimality conditions verifiable in polynomial time. The established properties give a potential of a beneficial interaction between scheduling and pre-scheduling phases in production planning, and also provide basic theoretical background for the construction of efficient heuristic and implicit enumerative algorithms.

Keywords:

• production planning
• scheduling model
• scheduling algorithm
• heuristic
• release time
• delivery time
• due-date

View correction statement:

Corrigendum

Public Interest Statement

Scheduling problems are mathematical problems formalized for the solution of diverse practical real-life problems. They deal with a finite set of requests or jobs to be performed (or scheduled) on a finite (and limited) set of resources called machines or processors. The aim is to choose the order of processing the jobs on the machines so as to meet a given objective criterion. In this paper we study a scenario with a single machine when jobs have arrival and due dates: a job cannot be assigned to the machine before its arrival time, whereas it is desirable to complete it by its due date; if this is not possible, we wish to minimize the maximum job deviation from its due date (the so-called lateness). The problem is known to be intractable. Still, we derive conditions that lead to its optimal solution in polynomial time.

1. Introduction

The term scheduling refers to the assignment of a set of requests to the given set of resources over time with the objective to optimize a given objective criterion. The requests are called jobs or tasks and a resources are called machines or processors, whereas the aim is to choose the order of processing the jobs on the machines so as to meet a given objective criteria. Therefore, a scheduling problem is characterized by the three distinct components: the tasks or activities that one wishes to perform, the resources available for their implementation, and the aims or objectives that one wants to achieve (that identify the best solutions). Different characteristics of jobs and machines together with different optimality criteria originate a vast amount of the scheduling problems.

Scheduling is an important phase in production planning, that, in turn, constitutes part of a wider production cycle. Once a product is designated, its production process needs to be determined. Decisions that are taken at the earlier phases of production planning before the scheduling phase (such as allocation and distribution of resources, raw materials, time limits, etc.), determine a particular scheduling model that is to be solved, i.e. this scheduling model essentially depends on the decisions made at the earlier (pre-scheduling) stages of production planning. In practice, there is a little interaction between the scheduling stage and the earlier stages in production planning, in the sense that the earlier made decisions do not normally change depending on the (potential) outcomes at the scheduling stage, i.e. the scheduling model itself doesn’t change. However, such an interaction might be beneficial since two similar scheduling models may have drastically different complexity status and hence admit solution methods of different efficiency. Based on the simulation results for the originally selected scheduling model, the decisions taken at the earlier (pre-scheduling) stages may potentially be adjusted, which, in turn, may adjust the scheduling model itself. This is often difficult since the most of the arisen scheduling models turn out to be computationally intractable (NP-hard in formal terms), and hence the interaction becomes complicated because of a considerable amount of time needed to solve the corresponding scheduling problem for delivering a solution with the desired quality. Whereas a general solution method for the initially selected scheduling model may require inadmissible computational time, the instances of that model that occur in a given application may have specific characteristics or can be adjusted to satisfy some particular conditions and properties. To this end, the study of the inherent structure of the initially selected scheduling model and the optimality conditions for that model, i.e. the conditions when the model can be efficiently solved, is important.

In this paper, we carry out this kind of study for a single-machine scheduling model with n requests or jobs, where every request is released at an integer time moment, has a processing requirement on the machine, and a due-date that specifies a desirable time moment for its completion. A job completed behind its due-date is said to be late. The objective is to minimize the maximum lateness of any job, i.e. the difference between its completion time and due-date.

According to the conventional three-field notation introduced by Graham, Lawler, Lenstra, and Rinnooy Kan (1979) the problem is abbreviated as $1|r_j|L_{max}$: the first field indicates the machine (single-processor) environment, the second field specifies job parameters ($r_j$ stands for the release time of job j), and in the third field the objective criterion is given (here $L_{max}$ stands for the maximum job lateness, in the second field the processing time is omitted since it is an obligatory parameter for any scheduling problem). There is an equivalent formulation of the problem in which job due-dates are replaced by the delivery times, abbreviated $1|r_j,q_j|C_{max}$ ($q_j$ stands for the delivery times): once job completes on the machine, it needs to be delivered to the customer. Since the delivery is accomplished by an independent unit, it requires no machine time. The objective is then to minimize the maximum job full completion time that includes its delivery.

In Section 2 we show why these two versions are equivalent and give their detailed descriptions. Because of the equivalence, we shall refer to any of the two versions interchangeably. The problem is known to be strongly NP-hard (Garey & Johnson, 1979). There are exact implicit enumerative algorithms, see for instance, McMahon and Florian (1975) and Carlier (1982). An efficient heuristic method that is commonly used for problem $1|r_j,q_j|C_{max}$ was proposed long time ago by Jackson (1955) for the version of the problem without release times, and then was extended by Schrage (1971) for taking into account job release times. The extended Jackson’s heuristic (J-heuristic, for short) iteratively, at each scheduling time t (given by job release or completion time), among the jobs released by time t schedules one with the the largest delivery time (or smallest due-date). Since the number of scheduling times is O(n) and at each scheduling time search for a minimal/maximal element in an ordered list is accomplished, the time complexity of the heuristic is $O(nlogn)$. J-heuristic is sometimes referred to as EDD-heuristic (Earliest Due-Date) or alternatively, LDT-heuristic (Largest Delivery Time).

J-heuristic gives the worst-case approximation ratio of 2, i.e. it delivers a solution which is at most twice worse than an optimal one. There are polynomial time algorithms with a better approximation for problem $1|r_j,q_j|C_{max}$. Potts (1980) has proposed a modification of J-heuristic that repeatedly applies J-heuristic O(n) times and obtains an improved approximation ratio of 3/2. Hall and Shmoys (1992) have expanded the later algorithm resulting in an improved approximation ratio of 4/3 by applying J-heuristic to the forward and backward versions of the problem simultaneously, and also proposed two polynomial approximation schemes (their algorithms allow partial order on the set of jobs). The idea of the usefulness of the simultaneous application of J-heuristic in forward and backward fashions was earlier exploited by Nowicki and Smutnicki (1994). In a more recent work (Vakhania Perez, & Carballo, 2013), the magnitude $\mathit{\kappa }$, no-more than the optimal objective value divided by the specially determined job processing time, is used to derive a more accurate worst-case approximation ratio of $1+1/\mathit{\kappa }$ for J-heuristic. The value of parameter $\mathit{\kappa }$ can be brutally determined in time $O(nlogn)$ using an easily calculable lower bound on the optimal objective value instead of using the optimal objective value itself.

As to the special cases of our problem, if all job release times or delivery times are equal, J-heuristic (its original version) gives an optimal solution, and with integer release times and unit processing times, it also delivers an optimal solution. If job release times, processing times and delivery time are restricted in such way that each $r_j$ lies in the interval $[q-q_j-p_j-A,q-q_j-A]$, for some constant A and suitably large q, then the problem can also be solved in time $O(nlogn)$, see Hoogeveen (1995). Garey, Johnson, Simons, and Tarjan (1981) have proposed an $O(nlogn)$ algorithm for the feasibility version with equal-length jobs (in the feasibility version job due-dates are replaced by deadlines and a schedule in which all jobs complete by their deadlines is looked for). Later in Vakhania (2004) was proposed an $O(n^{2}logn)$ algorithm for the minimization version with two possible job processing times.

For other related criteria, in Vakhania (2009) an $O(n^{3}logn)$ algorithm that minimizes the number of late jobs with release times on a single-machine when job preemptions are allowed. Without preemptions, two polynomial-time algorithms for equal-length jobs on single machine and on a group of identical machines were proposed in Vakhania (2013,2012), respectively, with time complexities $O(n^{2}logn)$ and $O(n^{3}lognlog{p}_{max})$, respectively.

Problem $1|r_j,q_j|C_{max}$ has been shown to be useful for the solution of the multiprocessor scheduling problems. For example, for the feasibility version with m identical machines and equal-length jobs, algorithms with the time complexities $O(n^{3}loglogn)$ and $O(n^{2}m)$ were proposed in Simons (1983) and Simons and Warmuth (1989), respectively. In Vakhania (2003) was proposed an $O(q_{max}mnlogn+O(m\mathit{\nu }n))$ algorithm for the minimization version of the latter problem, where $q_{max}$ is the maximal job delivery time and $\mathit{\nu }<n$ is a parameter.

The problem $1|r_j,q_j|C_{max}$ is commonly used for the solution of more complex job-shop scheduling problems as well. A solution of the former problem gives a strong lower bound for job-shop scheduling problems. In the classical job-shop scheduling problem the preemptive version of J-heuristic applied for a specially derived single-machine problem immediately gives a lower bound, see, for example, Carlier (1982), Carlier and Pinson (1989) and Brinkkotter and Brucker (2001) and more recent works of Gharbi and Labidi (2010) and Della Croce and T’kindt (2010). Carlier and Pinson (1998) have used a straightforwardly generalized J-heuristic for the solution of the multiprocessor job-shop problem with identical machines. It can also be adopted for the case when parallel machines are unrelated, see Vakhania and Shchepin (2002). J-heuristic can be useful for parallelizing the computations in scheduling job-shop Perregaard and Clausen (1998), and also for the parallel batch scheduling problems with release times Condotta, Knust, and Shakhlevich (2010).

Besides the above mentioned applications in multiprocessor, shop and batch scheduling problems, our problem has numerous immediate real-life applications in various production chains, CPU time sharing in operating systems (jobs being the processes to be executed by the processor), wireless sensor network transmission range distribution (where jobs are mobile devices with their corresponding ranges that can be modeled as release and due dates).

By exploring the inherent structural properties of the problem, here we derive new optimality conditions when practical special cases of our problem can be solved optimally in a low degree polynomial time. In particular, we provide explicit conditions that lead to an efficient solution of the problem by a mere application of J-heuristic. Then we study further useful structural properties of the J-schedules (ones created by J-heuristic) leading to the optimal solution of other versions of the problem with the same computational cost as that of J-heuristic. Finally, we focus on a special case of our problem with only two allowable job release times $r_1$ and $r_2$ with $r_1<r_2$ (abbreviated $1|\{r_1,r_2\}|L_{max}$ or $1|\{r_1,r_2\},\{q_i\}|C_{max}$). Although the latter problem remains NP-hard, it admits stricter dominance rules and optimality conditions leading to the corresponding polynomial-time verification procedures (and the reduction of the search space).

Employing the presented optimality and dominance conditions, a practitioner may simulate the scheduling phase under these conditions in real time (solving efficiently the scheduling problem under these conditions). Then it is verified whether the obtained solution also solves the original instance, i.e. if it is feasible for that instance. Otherwise, it might be possible to adopt the production process so that the optimality conditions are met. Carrying out this kind of simulation for a variety of arisen in a given production instances, a practitioner may adjust the pre-scheduling decisions and hence convert the initially determined scheduling model to another more restricted one admitting an efficient solution method. In this way, the production process might be adjusted to the optimality and dominance conditions resulting in a useful interaction between pre-scheduling and scheduling phases in production planning.

In the next subsection we give the basic concepts and some other preliminaries. In Section 3 we study efficiently identifiable conditions and cases when our generic problem can be solved in polynomial time. In Section 4 we show that the special case of the problem with only two allowable job due-dates remains NP-hard. Section 5 is devoted to the latter problem. In the first part of this section we give general properties for the polynomial time solution, whereas in Sections 5.1 and 5.2 we derive stricter dominance relations and other particular versions that can be efficiently solved. We give the final remarks in Section 6.

2. Basic concepts and definitions

Now we give a formal definition of our general scheduling problem. We have n jobs $j(j=1,\dots ,n)$ and single machine available at the time 0 . Each job j become available at its release time or head $r_j$, needs continuous processing time $p_j$ on the machine, and needs an additional delivery time or tail $q_j$ after the completion on the machine (note that $q_j$ needs no machine time in our model). The heads and tails are non-negative integral numbers while a processing time is a positive integer. A feasible schedule S assigns to each job j a starting time $t_j(S)$, such that $t_j(S)\ge r_j$ and $t_j(S)\ge t_k(S)+p_k$, for any job k included earlier in S; the first inequality says that a job cannot be started before its release time, and the second one reflects the restriction that the machine can handle only one job at the time. The completion time of job j, $c_j(S)=t_j(S)+p_j$; the full completion time of j in S, $C_j(S)=c_j(S)+q_j$. Our objective is to find an optimal schedule, i.e. a feasible schedule S with the minimal value of the maximal full job completion time $\left|S\right|={max}_j{C}_j$ (called the makespan).

In an equivalent formulation $1|r_j|L_{max}$, the delivery time $q_j$ of every job j is replaced by the due-date $d_j$ which is the desirable time for the completion of job j. Here the maximum job lateness $L_{max}$ (the difference between the job completion time and its due-date) needs to be minimized.

Given an instance of $1|r_j,q_j|C_{max}$, one can obtain an equivalent instance of $1|r_j|L_{max}$ as follows. Take a suitably large constant K (no less than the maximum job delivery time) and define due-date of every job j as $d_j=K-q_j$. Vice-versa, given an instance of $1|r_j|L_{max}$, an equivalent instance of $1|r_j,q_j|C_{max}$ can be obtained by defining job delivery times as $q_j=D-d_j$, where D is a suitably large constant (no less than the maximum job due date). It is straightforward to see that the pair of instances defined in this way are equivalent; i.e. whenever the makespan for the version $1|r_j,q_j|C_{max}$ is minimized, the maximum job lateness in $1|r_j|L_{max}$ is minimized, and vice-versa. We refer the reader to an early paper by Bratley, Florian, and Robillard (1973) for more details.

Next, we give a more detailed description of J-heuristic. It distinguishes n scheduling times, the time moments at which a job is assigned to the machine. Initially, the earliest scheduling time is set to the minimum job release time. Among all jobs released by that time a job with the mini- mum due-date (the maximum delivery time, alternatively) is assigned to the machine (ties being broken by selecting a longest job). Iteratively, the next scheduling time is either the completion time of the latest assigned so far job to the machine or the minimum release time of a yet unassigned job, whichever is more (as no job can be started before the machine gets idle nether before its release time). And again, among all jobs released by this scheduling time a job with the minimum due-date (the maximum delivery time, alternatively) is assigned to the machine. Note that the heuristic creates no gap that can be avoided always scheduling an already released job once the machine becomes idle, whereas among yet unscheduled jobs released by each scheduling time it gives the priority to a most urgent one (i.e. one with the smallest due-date or alternatively the largest delivery time).

We will use $\mathit{\sigma }$ for the initial J-schedule, i.e. one obtained by the application of Jackson’s heuristic (J-heuristic, for short) to the originally given problem instance, and $S_{\text{opt}}$ for an optimal schedule.

A J-schedule has a particular structure that enables us to deduce our conditions. Two basic classes of jobs in a J-schedule might be distinguished: the “urgent” (critical) and “non-urgent” (non-critical) ones. Critical jobs (that we call kernel jobs) are ones which may potentially realize the maximum value of the objective function in an optimal schedule $S_{\text{opt}}$ (we call such jobs overflow jobs). In a J-schedule, the critical jobs form tight sequences that extend to limited time intervals. We call such sequences of critical jobs kernels. Then the non-critical jobs (that we call emerging jobs) are to be distributed within the remained intervals (in between the kernels) in some optimal fashion. Starting from Section 3, we derive conditions when this can be done in polynomial time. We need to introduce some preliminary definitions before we define formally the above mentioned notions.

A J-schedule may contain a gap, which is its maximal consecutive time interval in which the machine is idle. We assume that there occurs a 0-length gap $\left(c_j,t_j\right)$ whenever job i starts at its earliest possible starting time, i.e. its release time, immediately after the completion of job j; here $t_j$ ($c_j$, respectively) denotes the starting (completion, respectively) time of job j.

A block in a J-schedule is its consecutive part consisting of the successively scheduled jobs without any gap in between preceded and succeeded by a (possibly a 0-length) gap. J-schedules have useful structural properties. The following basic definitions, taken from Vakhania (2004), will help us to expose these properties.

Among all jobs in a J-schedule S, we distinguish the ones which full completion time realizes the maximum full completion time in S; the latest scheduled such job is called the overflow job in S. We denote the overflow job in S by o(S). The block critical of S, B(S) is the block containing o(S).

Job e is called an emerging job in schedule S if $e\in B(S)$ and $q_e<q_{o(S)}$. The latest scheduled emerging job before the overflow job o(S) is called live and is denoted by l.

The kernel of S, K(S) is a sequence consisting of the jobs scheduled in schedule S between the live emerging job l(S) and the overflow job o(S), not including l(S) but including o(S) (note that the tail of any job K(S) is no less than of o(S)). Abusing slightly the terminology, we shall also use kernel for the corresponding set of jobs, and denote by r(K) the minimum job release time in kernel K.

It follows that every kernel is contained in some block in S, and the number of kernels in S equals to the number of the overflow jobs in it. Furthermore, since any kernel belongs to a single block, it may contain no gap. Note that if a J-schedule S has no emerging job then it will also have no kernel; then the overflow job in schedule S will not be part of any kernel. In general, we shall use $E\left(S\right)$ for the set of all emerging jobs scheduled before kernel K(S) in schedule S.

Figure 1 illustrates the above introduced notions for an instance with 6 jobs below. Schedule $\mathit{\sigma }$ consists of two blocks $B_1$ y $B_2$. Block $B_2$ is critical containing the overflow job 5 and kernel $K(\mathit{\sigma })=\{6,5\}$. Job 4 is the only emerging job. There is a gap [16, 18] in $\mathit{\sigma }$.

Figure 1. Schedule $\mathit{\sigma }$ (the dashed line represents a gap, and vertical lines represent job delivery times).

If a J-schedule S is not optimal then there must exist an emerging job forcing the delay of the kernel jobs in K(S) and that of the overflow job o(S) which must be restarted earlier (see Lemma 2 a bit later). We denote the amount of this forced delay by ${\mathrm{\Delta }}_l=c_l(S)-r(K(S))$.

Observation 1

In any feasible schedule, the jobs of kernel $K(\mathit{\sigma })$ may be restarted earlier by at most ${\mathrm{\Delta }}_l$ time units.

Proof

Immediately follows from the definition of ${\mathrm{\Delta }}_l$ and from the fact that no job of kernel $K(\mathit{\sigma })$ is released earlier than at time $r(K(\mathit{\sigma }))$. $\square$

In order to reduce the maximum job lateness ($\left|S\right|$) in S, we apply an emerging job e for K(S), that is, we reschedule e after K(S). Technically, we accomplish this into two steps: first we increase artificially the release time of e, assigning to it a magnitude, no less than the latest job release time in K(S); then we apply the J-heuristic to the modified in this way problem instance. Since now the release time of e is no less than that of any job of K(S), and $q_e$ is less than any job tail from K(S), the J-heuristic will give priority to the jobs of K(S) and job e will be scheduled after all these jobs.

If we apply the live emerging job l, then it is easy to see that there will arise a gap before the jobs of kernel K(S) if no other emerging job scheduled in S behind kernel K(S) gets included before kernel K(S) taking the (earlier) position of job l. In general, while we apply any emerging job $e\in E(S)$, we avoid such a scenario by increasing artificially the release time of any such an emerging job which may again push the jobs in kernel K(S) in the newly constructed schedule that we call a complementary to S schedule and denote by $S_e$.

Below we illustrate the construction of schedule ${\mathit{\sigma }}_l$. The table specifies a problem instance with 9 jobs. Schedules $\mathit{\sigma }$ and ${\mathit{\sigma }}_l$ are illustrated in Figures 2 and 3, respectively (the numbers within the circles stand for the full completion times of the corresponding jobs).

Figure 2. Schedule $\mathit{\sigma }$.

Figure 3. Schedule ${\mathit{\sigma }}_l$.

Figure 4. Every job $i_j$ is scheduled in the interval $\left[r_{i_j},r_{i_j}+p_{i_j}\right]$.

Figure 5. A schematic of a feasible schedule provided by a solution to SUBSET SUM.

3. The cases and conditions for polynomial time solution of the problem

In this section we give conditions leading to the efficient solution of our generic problem. These conditions are derived as a consequence of the analysis of J-schedule $\mathit{\sigma }$ immediately and hence provide an $O(nlogn)$ time decision.

Lemma 1

If the overflow job $o(\mathit{\sigma })$ is scheduled at its release time, then $\mathit{\sigma }$ is optimal.

Proof

If $o(\mathit{\sigma })$ is scheduled at its release time $r_{o(\mathit{\sigma })}$ then its starting time $t_{o(\mathit{\sigma })}=r_{o(\mathit{\sigma })}$. Hence job $o(\mathit{\sigma })$ starts at its early starting time in $\mathit{\sigma }$ and ends at its minimum completion time. Therefore, $o(\mathit{\sigma })$ can not be rescheduled earlier in $\mathit{\sigma }$, i.e. there is no scheduling ${\mathit{\sigma }}^{{}^{\prime }}$ such that $\left|{\mathit{\sigma }}^{{}^{\prime }}\right|<\left|\mathit{\sigma }\right|$ and $\mathit{\sigma }$ is optimal. $\square$

If $o(\mathit{\sigma })$ is not scheduled at its release time, then the starting time of $o(\mathit{\sigma })$ must be the completion time of some other job. Another case when schedule $\mathit{\sigma }$ is optimal, is when the tails of all the jobs scheduled in the critical block before $o(\mathit{\sigma })$ are greater than $o(\mathit{\sigma })$:

Lemma 2

If the critical block $B(\mathit{\sigma })$ does not contain an emerging job (equivalently, it has no kernel), then schedule $\mathit{\sigma }$ is optimal.

Proof

Assume that $\mathit{\sigma }$ contains a critical block $B(\mathit{\sigma })$ which does not contain an emerging job, i.e. for all $e\in B(\mathit{\sigma })$ scheduled before job $o(\mathit{\sigma })$, $q_e\ge q_{o(\mathit{\sigma })}$.

Suppose there is a non-empty sequence E of jobs in $B(\mathit{\sigma })$ scheduled before $o(\mathit{\sigma })$. If we reschedule some jobs of E after $o(\mathit{\sigma })$ the in the resultant schedule ${\mathit{\sigma }}^{{}^{\prime }}$ at least one job e will be completed no earlier than at the moment $C_{o(\mathit{\sigma })}(\mathit{\sigma })$. But as e is not an emerging job, $q_e\ge q_{o(\mathit{\sigma })}$ and therefore the full completion time of e, $C_e(\mathit{\sigma })$, will be no less than $C_{o(\mathit{\sigma })}(\mathit{\sigma })$. Then $\left|{\mathit{\sigma }}^{{}^{\prime }}\right|>\left|\mathit{\sigma }\right|$. Therefore, $\mathit{\sigma }$ is optimal.

If set E is empty, then $o(\mathit{\sigma })$ is scheduled in $\mathit{\sigma }$ at its release time, therefore by Lemma 1, $\mathit{\sigma }$ is optimal.

The case when $\mathit{\sigma }$ has no kernel is quite similar. $\square$

The following two lemmas state earlier known results that we have mentioned in the introduction. Their proofs are presented for the sake of completeness of this presentation.

Lemma 3

If all release times $r_i$ ($i=1,\dots ,n$) of jobs in $\mathit{\sigma }$ are equal to a constant r, then $\mathit{\sigma }$ is optimal.

Proof

As all jobs $i(i=1,\dots ,n)$ are released at the time r, then the J-heuristic in each iteration schedules the job j with largest tail. This gives us a schedule $\mathit{\sigma }$, such that jobs are scheduled in non-increasing order. Then $\mathit{\sigma }$ cannot contain an emerging job and by Lemma 2, $\mathit{\sigma }$ is optimal. $\square$

Lemma 4

Let $\mathit{\sigma }$ be a J-schedule with jobs $i(i=1,\dots ,n)$ with integer release times $r_i$ and unit processing times $p_i=1(i=1,\dots ,n)$. Then $\mathit{\sigma }$ is optimal.

Proof

Since the release time $r_i$ each job i is an integer number and its processing time is 1, during the execution of that job no other more urgent job may be released. Hence, at each scheduling time t, J-heuristic, among all the released by that time moment jobs, will include one with the largest tail. In addition, in $\mathit{\sigma }$, every job is scheduled at its release time $r_i$ or at the completion time of another job. If job $o(\mathit{\sigma })$ is scheduled at time $t=r_{o(\mathit{\sigma })}$, then $\mathit{\sigma }$ is optimal by Lemma 1. If $o(\mathit{\sigma })$ is scheduled at the completion time of another job k so that job $o(\mathit{\sigma })$ was released before the completion time of that job, then $q_k\ge q_{o(\mathit{\sigma })}$. Hence, there may exist no emerging job and $\mathit{\sigma }$ is optimal by Lemma 2. $\square$

Lemma 5

Let jobs in $J={\left\{i_j\right\}}_{j=1,\dots ,n}$ be ordered by a non-decreasing sequence of their release times. Then $\mathit{\sigma }$ is optimal if for any neighboring jobs $i_j$ and $i_{j+1}(j=1,\dots ,n-1)$, $r_{i_{j+1}}\ge r_{i_j}+p_{i_j}$.

Proof

By the condition in the lemma, every job $i_j$$(j=1,\dots ,n)$ is scheduled in $\mathit{\sigma }$ in the interval $\left[r_{i_j},r_{i_j}+p_{i_j}\right]$. So, the starting time of each job in $\mathit{\sigma }$ is $t_j=r_{i_j}$, i.e. each job $i_j$ begins at its early starting time in $\mathit{\sigma }$. This is true, in particular, for job $o(\mathit{\sigma })$ and therefore, by Lemma 1, $\mathit{\sigma }$ is optimal.

$\square$

Figure 4 illustrates schedule $\mathit{\sigma }$ for an instance possessing the above indicated property.

For the given k job release times, $r_1\le \cdots \le r_k$, let $J_i\left(i=1,\dots ,k\right)$ be the set of jobs released at the time $r_i$.

Theorem 1

For a given instance of problem $1|r_j,q_j|C_{max}$, the initial J-schedule $\mathit{\sigma }$ is optimal if $o(\mathit{\sigma })\in J_1$.

Proof

By the condition, at any scheduling time behind release times $r_2,\dots r_k$, job $o(\mathit{\sigma })$ was released. Then by J-heuristic, for each job i scheduled in $\mathit{\sigma }$ before job $o(\mathit{\sigma })$, $q_i\ge q_{o(\mathit{\sigma })}$. Hence, $\mathit{\sigma }$ does not contain an emerging job and it is optimal by Lemma 2. $\square$

Assume K is any kernel which forms part of some J-schedule S (K can be a kernel of other J-schedule distinct from S). Then we will say that job $e\in E\left(S\right)$is scheduled within kernel K if there is at least one job from that kernel scheduled before and after job e in schedule S.

Lemma 6

If job e is scheduled within kernel $K(\mathit{\sigma })$ in schedule S then $\left|S\right|>\left|\mathit{\sigma }\right|$.

Proof

First, it is easy to see that no job from kernel $K(\mathit{\sigma })$ scheduled before job e can be the overflow job in schedule S. Neither job e can be the overflow job in S as it is succeeded by at least one kernel job $j\in K(\mathit{\sigma })$ with $q_j\ge q_e$. Furthermore, no job k scheduled after kernel $K(\mathit{\sigma })$ can be the overflow job in schedule S as the right-shift of such a job in schedule S cannot be more than that of a more urgent kernel job.

It follows that only a job from kernel $K(\mathit{\sigma })$ scheduled after job e may be the overflow job in schedule S. But because of the forced right-shift imposed by job e, the job j from kernel $K(\mathit{\sigma })$ scheduled the last in schedule S cannot complete earlier in schedule S than job $o(\mathit{\sigma })$ was completed in schedule $\mathit{\sigma }$, i.e. $c_j(S)\ge c_{o(\mathit{\sigma })}(\mathit{\sigma })$. At the same time, by the definition of kernel $K(\mathit{\sigma })$ job j is no less urgent than job $o(\mathit{\sigma })$, i.e. $q_j\ge q_{o(\mathit{\sigma })}$. Then $C_j(S)\ge C_{o(\mathit{\sigma })}(\mathit{\sigma })$ and hence $\left|S\right|\ge \left|\mathit{\sigma }\right|$. $\square$

As a consequence of Lemmas 2 and 6 we get the following corollary:

Corollary 1

In any schedule better than $\mathit{\sigma }$, an emerging job is rescheduled behind kernel $K(\mathit{\sigma })$.

4. The NP-hardness of $1|\{r_1,r_2\},\{q_1,q_2\}|C_{max}$

From here on, we shall focus our attention on the special case of our problem with only 2 allowable job release times and tails. As we have seen earlier, J-heuristic delivers an optimal schedule whenever we have a single release time or a single tail (or due-date), i.e. the problems $1|q_j|C_{max}$ and $1|r_j|C_{max}$ ($1||L_{max}$ and $1|r_j,d_j=d|L_{max}$) are solvable in an almost linear time $nlogn$ (the general setting $1|r_j,q_j|C_{max}$ being strongly NP-hard). Now we show that we arrive at an NP-hard problem by allowing two distinct release times or tails; i.e. the problem $1|\{r_1,r_2\},\{q_1,q_2\}|C_{max}$ is already NP-hard. For the convenience, let us consider the version with due-dates $1|\{r_1,r_2\},\{d_1,d_2\}|L_{max}$.

Theorem 2

$1|\{r_1,r_2\},\{d_1,d_2\}|L_{max}$ is NP-hard.

Proof

We use the reduction from an NP-hard SUBSET SUM problem for the feasibility version of $1|\{r_1,r_2\},\{d_1,d_2\}|L_{max}$, in which we wish to know if there exists a feasible schedule that meets all job due-dates (i.e. in which all jobs are completed no later than their due-dates). In SUBSET SUM problem we are given a finite set of integer numbers $C=\{c_1,c_2,\dots ,c_n\}$ and an integer number $B\le {\sum }_{i=1}^n{c}_i$.¹ This decision problem gives a “yes” answer iff there exists a subset of C which sums up to B. Given an arbitrary instance of SUBSET SUM, we construct our scheduling instance with $n+1$ jobs with the total length of ${\sum }_{\mathit{\iota }=1}^n{c}_{\mathit{\iota }}+1$ as follows.

We have n partition jobs $1,\dots ,n$ released at time $r_1=0$ with $p_i=c_i$, $r_i=0$ and $d_i={\sum }_{\mathit{\iota }=1}^n{c}_{\mathit{\iota }}+1$, for $i=1,\dots ,n$. Besides these partition jobs, we have another separator job I, released at time $r_2=B$ with $p_I=1$, $r_I=r_2$ and with the due-date $d_I=B+1$. Note that this transformation creating an instance of $1|\{r_1,r_2\},\{d_1,d_2\}|L_{max}$ is polynomial as the number of jobs is bounded by the polynomial in n, and all magnitudes can be represented in binary encoding in O(n) bits.

Now we prove that there exists a feasible schedule in which all jobs meet their due-dates iff there exists a solution to our SUBSET SUM problem. In one direction, suppose there is a solution to SUBSET SUM formed by the numbers in set $C^{\prime }\subseteq C$. Let $J^{\prime }$ be the set of the corresponding partition jobs in our scheduling instance. Then we construct a feasible schedule in which all jobs meet their due-dates as follows (see Figure 5). We first schedule the partition jobs from set $J^{\prime }$ in the interval $[0,B]$ in a non-delay fashion (using for instance, Jackson’s heuristic). Then we schedule the separator job at time B completing it by its due-date $B+1$ and then the rest of the partition jobs starting from time $B+1$ again in a non-delay fashion by Jackson’s heuristic. Observe then that the latest scheduled job will be completed exactly at time ${\sum }_{\mathit{\iota }=1}^n{c}_{\mathit{\iota }}+1$ and all the jobs will meet their due-dates. Therefore, there exists a feasible schedule in which all jobs meet their due-dates whenever SUBSET SUM has a solution.

In the other direction, suppose there exists a feasible schedule S in which all jobs meet their due-dates. Then in that schedule, the separator job mist be scheduled in the interval $[B,B+1)$, whereas the latest scheduled partition job must be completed by time ${\sum }_{\mathit{\iota }=1}^n{c}_{\mathit{\iota }}+1$. But this may only be possible if the interval $[0,B]$ in schedule S is completely filled in by the partition jobs, i.e. there must be a corresponding subset $J^{\prime }$ of the partition jobs that fill in completely the interval $[0,B]$ in schedule S (if this interval were not completely filled out in schedule S then the completion time of the latest scheduled partition job would be ${\sum }_{\mathit{\iota }=1}^n{c}_{\mathit{\iota }}+1$ plus the total length of the gap within the interval $[0,B]$ and hence that job would not meet its due-date (seeas illustrated in Figure 6). Now clearly, the processing times of the jobs in set $J^{\prime }$ form the corresponding solution to SUBSET SUM.

$\square$

5. Tractable special cases of problem $1|\{r_1,r_2\},\{q_i\}|C_{max}$

In Section 4 we have shown that the version of our general problem with two job release times, i.e., the problem $1|\{r_1,r_2\},\{q_i\}|C_{max}$, is NP-hard. In this section we establish some useful properties of an optimal solution to this problem that can be verified in time $O(nlogn)$.

Figure 6. A non-feasible schedule (g is the gap and $l_g$ is the total length of that gap).

Figure 7. Schedule $\mathit{\sigma }$.

Assume that the sequence of jobs $\{i_j\}|j=1,\dots ,m)$ is enumerated so that the first m jobs of the sequence are ones released at time $r_1$ and the next $n-m$ jobs are ones released at time $r_2$ ($m<n$). We let $J_1$ and $J_2$ stand for the set of jobs released at the time $r_1$ and $r_2$, respectively.

Lemma 7

If ${\sum }_{j=1}^m{p}_{i_j}+r_1\le r_2$ then $\mathit{\sigma }$ is optimal.

Proof

Since ${\sum }_{j=1}^m{p}_{i_j}+r_1\le r_2$, J-heuristic in the first m iterations will schedule all the jobs released at time $r_1$. As the jobs $i_j$, $j=1,\dots ,m)$ are released simultaneously at the time $r_1$, they are scheduled optimally by Lemma 3.

By the condition in the Lemma, all jobs released at the time $r_1$ are completed by time $r_2$, and hence all the jobs in set $J_2$ are available for scheduling at time $r_2$. Then again J-heuristic will schedule all these jobs optimally (Lemma 3).

Now clearly, by pasting together the two above partial schedules, we obtain a complete optimal schedule (as if there arises a gap between the two portions of that schedule then it is unavoidable). $\square$

Lemma 8

Let $k<m$ be such that for the first k jobs with the largest tails in schedule $\mathit{\sigma }$ the equality ${\sum }_{l=1}^k{p}_{i_{j_l}}=r_2-r_1$ holds. Then $\mathit{\sigma }$ is optimal.

Proof

We distinguish the following two cases based on the fact that for the first k jobs with the largest tails released at time $r_1$, ${\sum }_{l=1}^k{p}_{i_{j_l}}=r_2-r_1$ is satisfied:

Case 1: $k=m$. In this case ${\sum }_{l=1}^m{p}_{i_{j_l}}=r_2-r_1$ and by Lemma 7, schedule $\mathit{\sigma }$ is optimal (with the equality being hold for any tow neighboring jobs).

Case 2: $k<m$. Let ${\mathit{\sigma }}^{{}^{\prime }}$ be the J-schedule for the first k jobs. Since all these jobs are released at the time $r_1$, they are scheduled optimally by Lemma 3. Further, since ${\sum }_{l=1}^k{p}_{i_{j_l}}\le r_2-r_1$, the earliest stating time of the jobs $i_{j_{k+1}},\dots ,i_{j_m}$ is $r_2$. Hence by time $r_2$, all the remaining yet unscheduled $n-k$ jobs become simultaneously available. Let ${\mathit{\sigma }}^{{}^{″}}$ be the J-schedule for these jobs. Since all yet unscheduled jobs are available by time $r_2$, ${\mathit{\sigma }}^{{}^{″}}$ is optimal by Lemma 3.

Now let $\mathit{\sigma }$ be the J-schedule obtained joining the J-schedules ${\mathit{\sigma }}^{{}^{\prime }}$ and ${\mathit{\sigma }}^{{}^{″}}$. Note that schedule $\mathit{\sigma }$ has no gap, hence it consists of a single block. By our construction, there exists no emerging job in schedule $\mathit{\sigma }$, and it is optimal by Lemma 2. $\square$

Below we let i, $i\le k$, be the earliest arisen job from $J_1$ during the construction of schedule $\mathit{\sigma }$, such that $t_i+p_i>r_2$, and we let $q^{{}^{\prime }}$ be the largest tail among the tails of the jobs released at time $r_2$.

Lemma 9

If $q_i\ge q^{{}^{\prime }}$, then $\mathit{\sigma }$ is optimal.

Proof

As it is easily seen, because $q_i\ge q^{{}^{\prime }}$, schedule $\mathit{\sigma }$ contains no emerging job and hence is optimal by Lemma 2. $\square$

Due to Theorem 1, from now on, let us assume that $o(\mathit{\sigma })\in J_2$ and that $B(\mathit{\sigma })$ contains at least one emerging job (otherwise, schedule $\mathit{\sigma }$ is optimal by Lemma 2.

Observation 2

$K(\mathit{\sigma })\subset J_2$

Proof

By the contradiction, suppose that kernel $K(\mathit{\sigma })$ contains at least one job $j\in J_1$. Then for all $i\in J_1$ scheduled before kernel $K(\mathit{\sigma })$, $q_i\ge q_j$ (by J-heuristic). As $o(\mathit{\sigma })$ is the job with smallest tail of kernel $K(\mathit{\sigma })$ (by the J-heuristic and the definition of kernel $K(\mathit{\sigma })$), $q_j\ge q_{o(\mathit{\sigma })}$ and hence, $q_i\ge q_{o(\mathit{\sigma })}$. Then schedule $\mathit{\sigma }$ may have no emerging job. We came to a contradiction proving our claim.$\square$

Observation 3

For problem $1|\{r_1,r_2\},\{q_i\}|C_{max}$, $E\left(\mathit{\sigma }\right)\subset J_1$ and for any emerging job $e\ne l$, $q_e\ge q_l$.

Proof

The first statement follows from the fact that the earliest scheduled job of kernel $K(\mathit{\sigma })$ in schedule $\mathit{\sigma }$ belongs to set $J_2$ which, in turn, follows from the J-heuristic. The second claim also follows from J-heuristic which schedules all jobs released at time $r_1$ (in particular, the jobs from $E(\mathit{\sigma })$) in the non-increasing order of their tails (in particular, up to time $r_2$ before the jobs of kernel $K(\mathit{\sigma })$), whereas job l is the latest scheduled one from set $E(\mathit{\sigma })$ in schedule $\mathit{\sigma }$. $\square$

Observation 4

The kernel $K(\mathit{\sigma })$ contains jobs with the largest tails from set $J_2$ scheduled in the non-increasing order of their tails.

Proof

By Observation 3, $E\left(\mathit{\sigma }\right)\subset J_1$. By definition the live emerging job, l is the last job scheduled before kernel $K(\mathit{\sigma })$ released at time $r_1$ and the first job with completion time greater than or equal to $r_2$. There may exist no job of set $J_2$ scheduled before job l in schedule $\mathit{\sigma }$ (job l starts strictly before time $r_2$). Then by J-heuristic, the first job of kernel $K(\mathit{\sigma })$ must be one with the largest tail from set $J_2$ and the following jobs must be scheduled in the non-increasing order of their tails. Moreover, all these jobs pertain to set $J_2$ by Observation 2. $\square$

Recall that, for a given J-schedule S, the complementary schedule $S_l$ always contains a gap before jobs of kernel K(S), i.e. the earliest scheduled job of K(S) starts at its release time in schedule $S_l$. In general, for any emerging job $e\in E(S)$, the complementary schedule $S_e$ may contain a gap or not, depending on the length of that job (compared to that of job l). We will see this in more details later.

Observation 5

The order of the jobs scheduled after time $r_2$, and before and after job e (particularly that of the jobs of $K(\mathit{\sigma })$) is the same in both schedules $\mathit{\sigma }$ and ${\mathit{\sigma }}_e$.

Proof

Note that since all jobs of kernel $K(\mathit{\sigma })$ and the jobs scheduled after this kernel in $\mathit{\sigma }$ were released by time $r_2$, J-heuristic should have been scheduled these jobs in the non-increasing order of their tails in schedule $\mathit{\sigma }$. Then J-heuristic will also schedule all the former jobs in the same order in schedule ${\mathit{\sigma }}_e$, i.e. the jobs before job e and after that job (also released by time $r_2$), in particular, ones of kernel $K(\mathit{\sigma })$ will be included in the same order in both schedules. $\square$

Let now J[e] be the set of all jobs j scheduled after $r_2$ in $\mathit{\sigma }$ such that $q_e<q_j<q_{o\left(\mathit{\sigma }\right)}$. It follows that all jobs from set J[e] are scheduled immediately after kernel $K(\mathit{\sigma })$ and before job e in ${\mathit{\sigma }}_e$.

Observation 6

$J[e]\subset J_2$.

Proof

First note that set J[e] has no job with the tail equal to $q_e$. Besides, $K(\mathit{\sigma })\subset J_2$ and $q_k>q_l$, for every job $k\in K(\mathit{\sigma })$. Furthermore, by J-heuristic, for every job $j\in J_1$ scheduled in $\mathit{\sigma }$ before $K(\mathit{\sigma })$, $q_j\ge q_l$, and for every job $i\in J_1$ scheduled after $K(\mathit{\sigma })$, $q_i\le q_l$, hence $q_i\le q_e$ as $q_e\ge q_l$ and the Observation follows from the definition of set J[e]. $\square$

Proposition 1

Without loss of generality, it might be assumed that all the jobs j with $q_j=q_e$ scheduled after kernel $K(\mathit{\sigma })$ in $\mathit{\sigma }$ are included behind job e in complementary schedule ${\mathit{\sigma }}_e$.

Observation 7

In schedule ${\mathit{\sigma }}_e$, the jobs of kernel $K(\mathit{\sigma })$ and those of set J[e] are left-shifted by the same amount, whereas all jobs j with $q_j\le q_e$ are right-shifted also by the same amount.

Proof

Note that while constructing schedule $\mathit{\sigma }$, J-heuristic schedules all the jobs in the non-increasing order of their tails behind time $r_2$ (as all of them are released by that time moment). While constructing schedule ${\mathit{\sigma }}_e$, the same set of jobs plus job e are available behind time $r_2$. In particular, it is easy to see that if $p_e\ge {\mathrm{\Delta }}_l$, all jobs of kernel $K(\mathit{\sigma })$ and those from set J[e] will be left-shifted by ${\mathrm{\Delta }}_l$, and if $p_e<{\mathrm{\Delta }}_l$ this left-shift will equal to $p_e$, whereas any j with $q_j\le q_e$ will be scheduled behind job e and will be right-shifted correspondingly. $\square$

Lemma 10

 

(1)	If $p_e>{\mathrm{\Delta }}_l$, then ${\mathit{\sigma }}_e$ has a gap of length $p_e-{\mathrm{\Delta }}_l$.
(2)	If $p_e\le {\mathrm{\Delta }}_l$, then ${\mathit{\sigma }}_e$ has no gap.

Proof

First note that ${\mathrm{\Delta }}_l$ is now $c_l(\mathit{\sigma })-r_2$. By the definition of ${\mathit{\sigma }}_e$, no job $j\in J_1$ with $q_j<q_e$ scheduled after $K(\mathit{\sigma })$ in $\mathit{\sigma }$ will be scheduled before $K(\mathit{\sigma })$ in ${\mathit{\sigma }}_e$. If $p_e\ge {\mathrm{\Delta }}_l$, in schedule ${\mathit{\sigma }}_e$, the jobs of kernel $K(\mathit{\sigma })$ and of set J[e] will have the left-shift of length ${\mathrm{\Delta }}_l$ (which is the maximum possible by Observation 1). Then ${\mathit{\sigma }}_e$ will have a gap of length $p_e-{\mathrm{\Delta }}_l$. If $p_e<{\mathrm{\Delta }}_l$, the jobs of kernel $K(\mathit{\sigma })$ and those of set J[e] will have a left-shift of length $p_e$, hence ${\mathit{\sigma }}_e$ will have no gap. $\square$

Due to Lemma 10 we define the gap ${\mathit{\delta }}_e$ in schedule ${\mathit{\sigma }}_e$ as follows:$$\begin{array}{c}\hfill {\mathit{\delta }}_e=\left\{\begin{array}{cc}0\hfill & \text{if}{p}_e\le {\mathrm{\Delta }}_l\hfill \\ p_e-{\mathrm{\Delta }}_l\hfill & \text{if}{p}_e>{\mathrm{\Delta }}_l\hfill \end{array}\right.\end{array}$$

for all $e\in E\left(\mathit{\sigma }\right)$.

Lemma 11

The full completion time of job e in ${\mathit{\sigma }}_e$,$$\begin{array}{c}\hfill C_e({\mathit{\sigma }}_e)=c_{o(\mathit{\sigma })}(\mathit{\sigma })+\sum _{j\in J[e]}{p}_j+{\mathit{\delta }}_e+q_e,\end{array}$$

Proof

By the definition of the set J[e], job e will be scheduled in ${\mathit{\sigma }}_e$ after all jobs of J[e] and before of all jobs i with $q_i=q_e$ (see Proposition 1). By the Observation 1, ${\mathrm{\Delta }}_l$ is the maximum possible left-shift for the jobs of $K(\mathit{\sigma })$ in ${\mathit{\sigma }}_e$. The full completion time of job e in ${\mathit{\sigma }}_e$ will depend on the amount of this left-shift. Consider the following two cases. If $p_e>{\mathrm{\Delta }}_l$, then the jobs of $K(\mathit{\sigma })$ and those of set J[e] will be left-shifted by the amount ${\mathrm{\Delta }}_l$ in schedule ${\mathit{\sigma }}_e$. Recall that the last job of kernel $K(\mathit{\sigma })$ scheduled in $\mathit{\sigma }$ is $o(\mathit{\sigma })$. Then,$$\begin{array}{c}\hfill C_e({\mathit{\sigma }}_e)=(c_{o(\mathit{\sigma })}(\mathit{\sigma })+\sum _{j\in J[e]}{p}_j)-{\mathrm{\Delta }}_l+p_e+q_e.\end{array}$$

Let ${\mathit{\delta }}_e=p_e-{\mathrm{\Delta }}_l$, then $p_e={\mathit{\delta }}_e+{\mathrm{\Delta }}_l$. Therefore$$\begin{array}{cc}\hfill C_e({\mathit{\sigma }}_e)& =c_{o(\mathit{\sigma })}(\mathit{\sigma })+\sum _{j\in J[e]}{p}_j-{\mathrm{\Delta }}_l+{\mathit{\delta }}_e+{\mathrm{\Delta }}_l+q_e\hfill \\ \hfill & =c_{o(\mathit{\sigma })}(\mathit{\sigma })+\sum _{j\in J[e]}{p}_j+{\mathit{\delta }}_e+q_e.\hfill \end{array}$$

In this case, ${\mathit{\sigma }}_e$ has a gap of length ${\mathit{\delta }}_e$.

If $p_e\le {\mathrm{\Delta }}_l$, then by the definition of set J[e] and the construction of schedule ${\mathit{\sigma }}_e$, the jobs of kernel $K(\mathit{\sigma })$ and those of set J[e] will be left-shifted by amount $p_e$ in schedule ${\mathit{\sigma }}_e$. Therefore,$$\begin{array}{cc}\hfill C_e({\mathit{\sigma }}_e)& =\left(c_{o(\mathit{\sigma })}(\mathit{\sigma })+\sum _{j\in J[e]}{p}_j\right)-p_e+p_e+q_e\hfill \\ \hfill & =c_{o(\mathit{\sigma })}(\mathit{\sigma })+\sum _{j\in J[e]}{p}_j+q_e.\hfill \end{array}$$

Note that in this case ${\mathit{\sigma }}_e$ has no gap. $\square$

Consider the following inequality:(1) $$\begin{array}{c}\hfill c_{o(\mathit{\sigma })}(\mathit{\sigma })+\sum _{j\in J[e]}{p}_j+{\mathit{\delta }}_e+q_e\ge C_{o(\mathit{\sigma })}(\mathit{\sigma }),\end{array}$$(1)

Lemma 12

If $p_e\ge {\mathrm{\Delta }}_l$ and the inequality (1) for job $e\in E\left(\mathit{\sigma }\right)$ holds, then in $S_{\text{opt}}$ job e is scheduled before kernel $K(\mathit{\sigma })$.

Proof

As $p_e\ge {\mathrm{\Delta }}_l$, ${\mathit{\sigma }}_e$ has a gap by Lemma 10 and kernel $K(\mathit{\sigma })$ starts at its early starting time $r(K(\mathit{\sigma }))=r_2$ in schedule ${\mathit{\sigma }}_e$. By inequality (1), $C_e({\mathit{\sigma }}_e)\ge C_{o(\mathit{\sigma })}(\mathit{\sigma })$; hence, $\left|{\mathit{\sigma }}_e\right|\ge \left|\mathit{\sigma }\right|$. Then it follows that job e cannot be scheduled after kernel $K(\mathit{\sigma })$ in schedule $S_{\text{opt}}$ and the lemma is proved. $\square$

Theorem 3

If $p_e\ge {\mathrm{\Delta }}_l$ for every $e\in E\left(\mathit{\sigma }\right)$ and the inequality (1) is satisfied for job e, then $\mathit{\sigma }$ is optimal.

Proof

Recall that if schedule $\mathit{\sigma }$ is not optimal, kernel $K(\mathit{\sigma })$ must be restarted earlier. This will be possible only if at least one job $e\in E\left(\mathit{\sigma }\right)$ is rescheduled after kernel $K(\mathit{\sigma })$. Suppose ${\mathit{\sigma }}_e$ is a schedule with a better (smaller) makespan than schedule $\mathit{\sigma }$. Then similarly, it is straightforward to verify that, by the condition of the Theorem, inequality (1) yields $C_e({\mathit{\sigma }}_e)\ge C_{o(\mathit{\sigma })}(\mathit{\sigma })$ for every $e\in E\left(\mathit{\sigma }\right)$. Then by Lemma 12, schedule $\mathit{\sigma }$ must be optimal. $\square$

Let $E\left(S,l\right)=\left\{e\in E\left(S\right)\backslash \left\{l\right\}\mid p_e\ge p_l\right\}$.

Lemma 13

If the inequality (1) is satisfied for job l, then in $S_{\text{opt}}$ any job $e\in E\left(\mathit{\sigma },l\right)$ is scheduled before kernel $K(\mathit{\sigma })$.

Proof

. By Lemma 12, l is scheduled in $S_{\text{opt}}$ before $K(S_{\text{opt}})$. Let k be the last job scheduled of J[l] in $\mathit{\sigma }$ (recall that J[l] is the set of all jobs j scheduled after $r_2$ in $\mathit{\sigma }$ such that $q_l<q_j<q_{o\left(\mathit{\sigma }\right)}$). By J-heuristic, job k has the tail less than the jobs of set J[l]. By the definition of the set J[l], without loss of generality we assume that the J-heuristic schedules job l after job k in ${\mathit{\sigma }}_l$. In addition, the starting time of job l must be the completion time of job k in ${\mathit{\sigma }}_l$, i.e. $t_l({\mathit{\sigma }}_l)=c_k({\mathit{\sigma }}_l)$ (by Proposition 1 and because by J-heuristic, for any job i scheduled after of k in $\mathit{\sigma }$, $q_i<q_k$ and therefore $q_i\le q_l$, by the definition of set J[l]).

It is easy to see that for all $e\in E\left(\mathit{\sigma },l\right)$, ${\mathit{\delta }}_e\ge {\mathit{\delta }}_l$ (because $p_e\ge p_l$ and by the definition of ${\mathit{\delta }}_e$). Besides, job k is scheduled after jobs of kernel $K(\mathit{\sigma })$ in ${\mathit{\sigma }}_e$ and job e can be scheduled before or after job k in ${\mathit{\sigma }}_e$. We respectively distinguish the following two cases. If job e is scheduled in ${\mathit{\sigma }}_e$ after of job k, the starting time of job e in schedule ${\mathit{\sigma }}_e$ is equal to the starting time of job l in schedule ${\mathit{\sigma }}_l$, i.e. $t_e({\mathit{\sigma }}_e)=t_l({\mathit{\sigma }}_l)$ since for any job i scheduled after job l in ${\mathit{\sigma }}_l$, $q_i\le q_l$ and $q_i<q_e$ since $q_e\ge q_l$. As the inequality (1) is satisfied for l, it is also satisfied for job e because ${\mathit{\delta }}_e\ge {\mathit{\delta }}_l$ and $q_e\ge q_l$. By Lemma 12, e is scheduled before $K(\mathit{\sigma })$ in $S_{\text{opt}}$.

If job e is scheduled in ${\mathit{\sigma }}_e$ before job k, the jobs scheduled after job e in schedule ${\mathit{\sigma }}_e$ (in particular the jobs of set J[l]) are right-shifted, therefore, the completion time of job k in ${\mathit{\sigma }}_e$ is greater than the completion time of job k in ${\mathit{\sigma }}_l$. Also, because ${\mathit{\delta }}_e\ge {\mathit{\delta }}_l$, the completion time of job k in ${\mathit{\sigma }}_e$ is greater than or equal to the completion time of job l in ${\mathit{\sigma }}_l$. $(c_k({\mathit{\sigma }}_e)\ge c_l({\mathit{\sigma }}_l))$. As $q_k>q_l$, $C_k({\mathit{\sigma }}_e)>C_l({\mathit{\sigma }}_l)$ and therefore $\left|{\mathit{\sigma }}_e\right|>\left|{\mathit{\sigma }}_l\right|$. Then job e cannot be scheduled after kernel $K(\mathit{\sigma })$ in schedule $S_{\text{opt}}$ since job l satisfies the inequality (1), hence $\left|{\mathit{\sigma }}_e\right|>\left|\mathit{\sigma }\right|$.

We have shown that job e cannot be scheduled after kernel $K(\mathit{\sigma })$ in schedule $S_{\text{opt}}$ and Lemma is proved. $\square$

From here on, we denote by k be the job with the greatest full time completion in schedule $\mathit{\sigma }$ among all the jobs scheduled after the jobs of set J[e]. As it can be easily seen, job k can be either from set $J_1$ or $J_2$.

Observation 8

If the overflow job of schedule ${\mathit{\sigma }}_e$ is scheduled after $r_2$, then it belongs to set $\{o(\mathit{\sigma }),e,k\}$.

Proof

From Observation 5 the jobs scheduled behind time $r_2$ and before job e in schedule ${\mathit{\sigma }}_e$ have the same processing order as in schedule $\mathit{\sigma }$. At the same time, by Observation 7 the jobs of kernel $K(\mathit{\sigma })$ and those from set J[e] have the same left-shift $p_e$ in schedule ${\mathit{\sigma }}_e$. Right after the latter jobs job e is included in schedule ${\mathit{\sigma }}_e$ (Proposition 1) and hence both, the processing order and the starting/completion times of the following jobs will remain unchanged. Now our claim follows from the definition of jobs $o(\mathit{\sigma })$, e and k. $\square$

Lemma 14

Schedule ${\mathit{\sigma }}_e$ is optimal if $p_e\ge {\mathrm{\Delta }}_l$ and $o(\mathit{\sigma })=o({\mathit{\sigma }}_e)$.

Proof

Since $p_e>{\mathrm{\Delta }}_l$, the jobs of kernel $K(\mathit{\sigma })$ are left-shifted in schedule ${\mathit{\sigma }}_e$ by the amount ${\mathrm{\Delta }}_l$. By definition of ${\mathrm{\Delta }}_l$ and from the fact that all jobs of kernel $K(\mathit{\sigma })$ are released by time $r_2$, the earliest job from that kernel starts at its early starting time in ${\mathit{\sigma }}_e$, i.e. $t_{K(\mathit{\sigma })}({\mathit{\sigma }}_e)=r_2$. By J-heuristic, for any job $i\in K(\mathit{\sigma })\backslash \{o(\mathit{\sigma })\}$, $q_i\ge q_{o(\mathit{\sigma })}$. It follows that the completion time of job $o(\mathit{\sigma })$ in schedule ${\mathit{\sigma }}_e$ is the least possible and schedule ${\mathit{\sigma }}_e$ optimal. $\square$

Theorem 4

If job $o({\mathit{\sigma }}_e)$ is scheduled before kernel $K(\mathit{\sigma })$, then schedule ${\mathit{\sigma }}_e$ is optimal.

Proof

Since $K(\mathit{\sigma })\subset J_2$ (Observation 2) and first job of $K(\mathit{\sigma })$ is the job with the largest tail in set $J_2$, all jobs scheduled before kernel $K(\mathit{\sigma })$ are in set $J_1$. Hence the overflow job $o({\mathit{\sigma }}_e)$ is in set $J_1$. By J-heuristic, all jobs scheduled before kernel $K(\mathit{\sigma })$ are scheduled in the non-increasing order of their tails (see also Lemma 3). Then there may exist no schedule ${\mathit{\sigma }}_e^{{}^{\prime }}$ such that $\left|{\mathit{\sigma }}_e^{{}^{\prime }}\right|<\left|{\mathit{\sigma }}_e\right|$ and ${\mathit{\sigma }}_e$ is optimal. $\square$

Below we illustrate the above Theorem using a problem instance of our problem with 5 jobs. Schedules $\mathit{\sigma }$ and ${\mathit{\sigma }}_l$ are illustrated in Figures 7 and 8, respectively (the numbers within the circles stand for the full completion times of the corresponding jobs).

Observation 9

If in schedule ${\mathit{\sigma }}_e$ the overflow job $o({\mathit{\sigma }}_e)$ is scheduled before kernel $K(\mathit{\sigma })$, then $o({\mathit{\sigma }}_e)\notin E(\mathit{\sigma })\backslash \left\{e\right\}$.

Proof

Indeed, by the definition of an emerging job, all jobs from set $E(\mathit{\sigma })$ have the tail smaller than that of the jobs in kernel $K(\mathit{\sigma })$, whereas these jobs, except job e, are scheduled before the jobs of that kernel in schedule ${\mathit{\sigma }}_e$. Then clearly, none of them (excluding job e) may be the overflow job in schedule ${\mathit{\sigma }}_e$. $\square$

5.1. A few more properties for equal-length jobs in set $J_1$

In this section we consider another special case of our problem when all jobs released at time $r_1$ have the same processing time p. We abbreviate this problem as $1\left|\{r_1,r_2\},q_j,p_{r_1,j}=p\right|C_{max}$ ($p_{r_1,j}=p$ denotes that all jobs released at the time $r_1$ have processing time p).

Recall that the left-hand side in inequality (1) is the full completion time of job e in schedule ${\mathit{\sigma }}_e$ (job k is defined as earlier). We define set $J(e,k)=\left\{i|q_k\le q_i\le q_e\right\}$.

Lemma 15

The full completion time of job k in the schedule ${\mathit{\sigma }}_e$ is:$$\begin{array}{c}\hfill C_k({\mathit{\sigma }}_e)=c_{o\left(\mathit{\sigma }\right)}(\mathit{\sigma })+\sum _{j\in J[e]}{p}_j+{\mathit{\delta }}_e+\sum _{i\in J(e,k)}{p}_i+p_k+q_k.\end{array}$$

Proof

Is analogous to that of Lemma 11. $\square$

Consider the following inequality:(2) $$\begin{array}{c}\hfill c_{o\left(\mathit{\sigma }\right)}(\mathit{\sigma })+\sum _{j\in J[e]}{p}_j+{\mathit{\delta }}_e+\sum _{i\in J(e,k)}{p}_i+p_k+q_k\ge C_{o\left(\mathit{\sigma }\right)}(\mathit{\sigma })\end{array}$$(2)

Lemma 16

For problem $1\left|\{r_1,r_2\},q_j,p_{r_1,j}=p\right|C_{max}$, in any schedule ${\mathit{\sigma }}_e$ there occurs a gap before kernel $K(\mathit{\sigma })$. Moreover, ${\mathit{\delta }}_e={\mathit{\delta }}_l$ for every job $e\in E\left(\mathit{\sigma }\right)\backslash \{l\}$.

Proof

We have $p_e>{\mathrm{\Delta }}_l$ since $p_e=p_l=p$ for all $e\in E\left(\mathit{\sigma }\right)\backslash \{l\}$. By Lemma 10, schedule ${\mathit{\sigma }}_e$ has a gap of length $p_e-{\mathrm{\Delta }}_l$ and ${\mathit{\delta }}_e={\mathit{\delta }}_l$ for all $e\in E\left(\mathit{\sigma }\right)\backslash \{l\}$. $\square$

Lemma 17

If the full completion time of job k satisfies the inequality (2), then each job $e\in E\left(\mathit{\sigma }\right)$ is scheduled before kernel $K(\mathit{\sigma })$ in $S_{\text{opt}}$.

Proof

The inequality (2) implies that $C_k({\mathit{\sigma }}_l)\ge C_{o(\mathit{\sigma })}(\mathit{\sigma })$; hence, $\left|{\mathit{\sigma }}_l\right|\ge \left|\mathit{\sigma }\right|$. As the full completion time of k in $\mathit{\sigma }$ is less than the full completion time of the overflow job $o(\mathit{\sigma })$ (otherwise, job k would be the overflow job in $\mathit{\sigma }$) and $C_k({\mathit{\sigma }}_l)\ge C_{o(\mathit{\sigma })}(\mathit{\sigma })$, job l cannot be scheduled after kernel $K(\mathit{\sigma })$ in schedule $S_{\text{opt}}$. By Lemma 16, ${\mathit{\delta }}_e={\mathit{\delta }}_l$ for every emerging job e. Then the starting time of job k in schedule ${\mathit{\sigma }}_e$ is the same as that in ${\mathit{\sigma }}_l$. Therefore $C_k({\mathit{\sigma }}_e)\ge C_{o(\mathit{\sigma })}(\mathit{\sigma })$ and $\left|{\mathit{\sigma }}_e\right|\ge \left|\mathit{\sigma }\right|$ for each job $e\in E\left(\mathit{\sigma }\right)$. It follows that no job $e\in E\left(\mathit{\sigma }\right)$ can be scheduled after kernel $K(\mathit{\sigma })$ in schedule $S_{\text{opt}}$. $\square$

Theorem 5

For problem $1\left|\{r_1,r_2\},q_j,p_{r_1,j}=p\right|C_{max}$, schedule $\mathit{\sigma }$ is optimal, if:

(1)	The inequality (1) is satisfied for job l in schedule ${\mathit{\sigma }}_l$.
(2)	The inequality (2) is satisfied for job k in schedule ${\mathit{\sigma }}_l$.

Proof

For the first claim, by Lemma 13, any job $e\in E\left(\mathit{\sigma }\right)$ is scheduled in $S_{\text{opt}}$ after kernel $K(\mathit{\sigma })$. This implies that every job $e\in E\left(\mathit{\sigma }\right)\backslash \{l\}$ satisfies the inequality (1) and by Theorem 3, $\mathit{\sigma }$ is optimal.

As to the second claim, by Lemma 17 every job $e\in E\left(\mathit{\sigma }\right)\backslash \{l\}$ must be scheduled before kernel $K(\mathit{\sigma })$ in $S_{\text{opt}}$, hence $\mathit{\sigma }$ is optimal. $\square$

5.2. Short emerging jobs

In this subsection we study the case when the use of a short emerging job, i.e. one with processing time less than ${\mathrm{\Delta }}_l$, leads us to useful optimality properties. Recall from Lemma 10 that for such a short job e schedule ${\mathit{\sigma }}_e$ has no gap. Throughout this subsection we let j be the job from set J[e] scheduled the last in schedule $\mathit{\sigma }$, and, as earlier, k stands for the job with the maximum full completion time among the jobs scheduled behind the jobs of J[e] in schedule $\mathit{\sigma }$.

Property 1

Let $p_e\le {\mathrm{\Delta }}_l$. If $J[e]\ne \mathrm{\varnothing }$ then $c_e({\mathit{\sigma }}_e)=c_j(\mathit{\sigma })$, otherwise ($J[e]=\mathrm{\varnothing }$) $c_e({\mathit{\sigma }}_e)=c_{o(\mathit{\sigma })}(\mathit{\sigma })$.

Proof

Suppose first $J[e]\ne \mathrm{\varnothing }$. Consider the set of the emerging jobs from schedule $\mathit{\sigma }$ included in between job e and kernel $K(\mathit{\sigma })$, the jobs of kernel $K(\mathit{\sigma })$ and ones from set J[e]. Note that these are the jobs which will be included before job e in schedule ${\mathit{\sigma }}_e$. These jobs will be left-shifted by $p_e$ time units in the latter schedule ( see Lemma 10). Since job j is one of these jobs, it will also be left-shifted by the same amount and job e will start immediately after after job j in schedule ${\mathit{\sigma }}_e$ (if there are jobs scheduled after kernel $\mathit{\sigma }$ with the tail equal to $q_e$, they will be included behind job e by Proposition 1). It follows that the completion time of job e in schedule ${\mathit{\sigma }}_e$ is equal to that of job j in schedule $\mathit{\sigma }$. This completes the case $J[e]\ne \mathrm{\varnothing }$, and the other case $J[e]=\mathrm{\varnothing }$ can be similarly seen. $\square$

Lemma 18

If $p_e<{\mathrm{\Delta }}_l$, then $C_e({\mathit{\sigma }}_e)<C_{o(\mathit{\sigma })}(\mathit{\sigma })$.

Proof

By Property 1, $c_e({\mathit{\sigma }}_e)=c_j(\mathit{\sigma })$ if $J[e]\ne \mathrm{\varnothing }$ and $q_e<q_j$ (by definition of set J[e]). Hence, $C_e({\mathit{\sigma }}_e)<C_j(\mathit{\sigma })$. But $C_j(\mathit{\sigma })<C_{o(\mathit{\sigma })}(\mathit{\sigma })$ and our claim follows. If now $J[e]=\mathrm{\varnothing }$, by Property 1, $c_e({\mathit{\sigma }}_e)=c_{o(\mathit{\sigma })}(\mathit{\sigma })$ and $q_e<q_{o(\mathit{\sigma })}$ (by definition of overflow job). Hence, $C_e({\mathit{\sigma }}_e)<C_{o(\mathit{\sigma })}(\mathit{\sigma })$.$\square$

Observation 10

If $p_e<{\mathrm{\Delta }}_l$, then $C_k({\mathit{\sigma }}_e)=C_k(\mathit{\sigma })$.

Proof

Since schedule ${\mathit{\sigma }}_e$ has no gap (Lemma 10) all the emerging jobs scheduled between e and kernel $K(\mathit{\sigma })$, the jobs of kernel $K(\mathit{\sigma })$ and ones from set J[e] will have the same left-shift of length $p_e$ in schedule ${\mathit{\sigma }}_e$. At the same time, all jobs scheduled after jobs of set J[e] in schedule $\mathit{\sigma }$ will have no shift in schedule ${\mathit{\sigma }}_e$ as job e will be included before them. Then the starting time of job k in both schedules ${\mathit{\sigma }}_e$ and $\mathit{\sigma }$ is the same and our claim follows. $\square$

Theorem 6

If $p_e<{\mathrm{\Delta }}_l$, then $\left|{\mathit{\sigma }}_e\right|\le \left|\mathit{\sigma }\right|$.

Proof

In schedule ${\mathit{\sigma }}_e$, either the overflow job $o({\mathit{\sigma }}_e)$ is scheduled before or behind kernel $K(\mathit{\sigma })$. For the latter case, by Observation 8, the only potential overflow jobs in schedule ${\mathit{\sigma }}_e$ are jobs $o(\mathit{\sigma })$, e and k. Since the jobs of kernel $K(\mathit{\sigma })$ have the left-shift of length $p_e$ in schedule ${\mathit{\sigma }}_e$, $C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)=C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e$ and hence $C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)<C_{o(\mathit{\sigma })}(\mathit{\sigma })$. By Lemma 18, $C_e({\mathit{\sigma }}_e)<C_{o(\mathit{\sigma })}$ and by Observation 10, $C_k({\mathit{\sigma }}_e)=C_k(\mathit{\sigma })$. But $C_k(\mathit{\sigma })\le C_{o(\mathit{\sigma })}(\mathit{\sigma })$ and hence $C_k({\mathit{\sigma }}_e)\le C_{o(\mathit{\sigma })}(\mathit{\sigma })$. Thus the full completion time of jobs $o(\mathit{\sigma })$, e and k in schedule ${\mathit{\sigma }}_e$ is no more than that in schedule $\mathit{\sigma }$ and the theorem holds for first second case above.

For the first case above (the overflow job $o({\mathit{\sigma }}_e)$ is scheduled before kernel $K(\mathit{\sigma })$), again $\left|{\mathit{\sigma }}_e\right|\le \left|\mathit{\sigma }\right|$. Indeed, any job scheduled before kernel $K(\mathit{\sigma })$ in schedule $\mathit{\sigma }$ must have the full completion time no more than job $o(\mathit{\sigma })$ (by the definition of the overflow job) whereas the set of all jobs scheduled before kernel $K(\mathit{\sigma })$ in schedule $\mathit{\sigma }$ is the same as that in schedule ${\mathit{\sigma }}_e$ except that job e is rescheduled behind kernel $K(\mathit{\sigma })$ in schedule ${\mathit{\sigma }}_e$.$\square$

Observation 11

If $p_e\le {\mathrm{\Delta }}_l$ and $J[e]\ne \mathrm{\varnothing }$, then the overflow job in schedule ${\mathit{\sigma }}_e$ is:

(1)	Job k if $C_k(\mathit{\sigma })>C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e$ and $C_k(\mathit{\sigma })>c_j(\mathit{\sigma })+q_e$.
(2)	Job e if $c_j(\mathit{\sigma })+q_e>C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e$ and $c_j(\mathit{\sigma })+q_e>C_k(\mathit{\sigma })$.
(3)	Job $o(\mathit{\sigma })$ if $C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e>C_k(\mathit{\sigma })$ and $C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e>c_j(\mathit{\sigma })+q_e$.

Proof

Below we prove each of these cases using the fact that the overflow job in schedule ${\mathit{\sigma }}_e$ is in set $\{o(\mathit{\sigma }),e,k\}$ (Observation 8).

(1)	By the definition of the overflow job in $\mathit{\sigma }$, $C_{o(\mathit{\sigma })}(\mathit{\sigma })\ge C_k(\mathit{\sigma })$. Since $p_e\le {\mathrm{\Delta }}_l$, job $o(\mathit{\sigma })$ will have the left-shift of length $p_e$ in ${\mathit{\sigma }}_e$, i.e. $C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)=C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e$ (By Observation 7 and Lemma 10). By Observation 10, $C_k({\mathit{\sigma }}_e)=C_k(\mathit{\sigma })$, and the inequality $C_k(\mathit{\sigma })>C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e$ implies that $C_k({\mathit{\sigma }}_e)>C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)$. By Property 1, $c_e({\mathit{\sigma }}_e)=c_j(\mathit{\sigma })$. Hence, the full completion time of job e in ${\mathit{\sigma }}_e$, $C_e({\mathit{\sigma }}_e)=c_j(\mathit{\sigma })+q_e$ and since $C_k(\mathit{\sigma })>c_j(\mathit{\sigma })+q_e$, $C_k({\mathit{\sigma }}_e)>C_e({\mathit{\sigma }}_e)$. Then $C_k({\mathit{\sigma }}_e)>C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)$ and $C_k({\mathit{\sigma }}_e)>C_e({\mathit{\sigma }}_e)$, yields that k is the overflow job in ${\mathit{\sigma }}_e$.
(2)	From $C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)=C_{o(\mathit{\sigma })}-p_e$ and $C_e({\mathit{\sigma }}_e)=c_j(\mathit{\sigma })+q_e$ (see the proof of the above claim 1), and from $c_j(\mathit{\sigma })+q_e>C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e$, we get that $C_e({\mathit{\sigma }}_e)>C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)$. From $C_k({\mathit{\sigma }}_e)=C_k(\mathit{\sigma })$ (Observation 10) and $c_j(\mathit{\sigma })+q_e>C_k(\mathit{\sigma })$, $C_e({\mathit{\sigma }}_e)>C_k({\mathit{\sigma }}_e)$. Then $C_e({\mathit{\sigma }}_e)>C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)$ and $C_e({\mathit{\sigma }}_e)>C_k({\mathit{\sigma }}_e)$ yields that e is the overflow job in ${\mathit{\sigma }}_e$.
(3)	By the definition of the overflow job in $\mathit{\sigma }$, $C_{o(\mathit{\sigma })}(\mathit{\sigma })\ge C_k(\mathit{\sigma })$, and we have seen that $C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)=C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e$. By Observation 10, $C_k({\mathit{\sigma }}_e)=C_k(\mathit{\sigma })$. Then from the inequality $C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e>C_k(\mathit{\sigma })$, $C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)>C_k({\mathit{\sigma }}_e)$. We also know that $C_e({\mathit{\sigma }}_e)=c_j(\mathit{\sigma })+q_e$. Then inequality $C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e>c_j(\mathit{\sigma })+q_e$ implies that $C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)>C_e({\mathit{\sigma }}_e)$. Thus similarly to the above two cases, $C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)>C_k({\mathit{\sigma }}_e)$ and $C_{o(\mathit{\sigma })}({\mathit{\sigma }}_e)>C_e({\mathit{\sigma }}_e)$ yields that job $o(\mathit{\sigma })$ is the overflow job in ${\mathit{\sigma }}_e$.

$\square$

Observation 12

If $p_e\le {\mathrm{\Delta }}_l$ and set $J[e]=\mathrm{\varnothing }$, then the overflow job in schedule ${\mathit{\sigma }}_e$ is:

(1)	Job k if $C_k(\mathit{\sigma })>C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e$ and $C_k(\mathit{\sigma })>c_{o(\mathit{\sigma })}(\mathit{\sigma })+q_e$.
(2)	Job e if $c_{o(\mathit{\sigma })}(\mathit{\sigma })+q_e>C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e$ and $c_{o(\mathit{\sigma })}(\mathit{\sigma })+q_e>C_k(\mathit{\sigma })$.
(3)	Job $o(\mathit{\sigma })$ if $C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e>C_k(\mathit{\sigma })$ and $C_{o(\mathit{\sigma })}(\mathit{\sigma })-p_e>c_{o(\mathit{\sigma })}(\mathit{\sigma })+q_e$.

Proof

Is analogous to that of Lemma 11. $\square$

Theorem 7

Schedule ${\mathit{\sigma }}_e$ is optimal if $p_e<{\mathrm{\Delta }}_l$, $k\in J_1$ and $k=o({\mathit{\sigma }}_e)$.

Proof

Schedule ${\mathit{\sigma }}_e$ is better than schedule $\mathit{\sigma }$ due to Theorem 6. Moreover, we show that there may exist no better schedule than ${\mathit{\sigma }}_e$. It suffices to consider potential rearrangements in which only the emerging jobs are involved (see Lemma 2). To this end, note first that $C_{o(\mathit{\sigma })}(\mathit{\sigma })\ge C_k(\mathit{\sigma })$. In other words, the former kernel $K(\mathit{\sigma })$ need not be further left-shifted, whereas we show that job k cannot be further left-shifted. Indeed, let S be a schedule in which some emerging job(s) are rescheduled behind kernel $K(\mathit{\sigma })$. Since $k\in J_1$, $q_e\ge q_k$ for any emerging job $e\in E(\mathit{\sigma })$ (due to J-heuristic). Hence the J-heuristic will include any such emerging job before job k in schedule S. Let us consider the following two possibilities.

(1)	If schedule S has no gap, then because of the above observations and due to the fact that the set of jobs scheduled before job k in both schedules ${\mathit{\sigma }}_e$ and S is the same, job k is started and completed in schedule S at the same time as in schedule ${\mathit{\sigma }}_e$. Hence, $|S|=|{\mathit{\sigma }}_e|$.
(2)	If schedule S has a gap, then since in schedule S all the rescheduled emerging jobs are included before job k, the latter job will be right-shifted by the length of that gap. Then $C_k(S)>C_k({\mathit{\sigma }}_e)$ and hence $|S|>|{\mathit{\sigma }}_e|$.

We have showed that there may exist no schedule better than ${\mathit{\sigma }}_e$ and the proof is complete (Figure 9). $\square$

 

Figure 8. Schedule ${\mathit{\sigma }}_l$, in this schedule the overflow job $o({\mathit{\sigma }}_l)$ is scheduled before kernel $K(\mathit{\sigma })$.

Figure 9. Schedule $\mathit{\sigma }$, $\left|\mathit{\sigma }\right|=57$, with the live emerging job $l=4$ and $o(\mathit{\sigma })=9$; $J[l]=5,6$ and $k=7$.

Figure 10. Schedule ${\mathit{\sigma }}_l$ has the makespan 59 and it is not optimal as $|{\mathit{\sigma }}_l|>|\mathit{\sigma }|$. Here inequality (1) is not satisfied for job l, job $k=7$ is the overflow job in ${\mathit{\sigma }}_l$.

Figure 11. An optimal schedule $S_{opt}$ with the makespan 56.

As we illustrate below with an instance of our problem, the above theorem cannot be extended to the case when $k=o({\mathit{\sigma }}_e)$ and $p_e\ge {\mathrm{\Delta }}_l$, as then we are forced to solve the subset sum problem (see Section 4). Thus the problem bottleneck is reached when these conditions hold. The table below specifies our problem instance. In Figures 10 and 11, illustrating schedule ${\mathit{\sigma }}_l$ and an optimal schedule, respectively, for that instance, the numbers within the circles are the full completion times of the corresponding jobs.

6. Conclusion

Based on the analysis of the J-schedules, we have established formal conditions when an optimal solution can be efficiently obtained. Our analysis yielded strict explicit relationships and polynomial time solution of these particular cases. We have conducted a similar study for an NP-hard spacial case of our generic problem with only two allowable job release times. Due to our conjecture of adaptive production planning, these results may stimulate the development of more efficient production planning allowing a beneficial interaction between scheduling and pre-scheduling phases for the scheduling models with release and delivery times, in particular.

Our study essentially relied on the partition of the whole scheduling horizon into two basic types of intervals containing urgent (kernel) and non-urgent (emerging) jobs, and extracting and treating the conflicts occurring between these two types of intervals. Such an analysis give some practical intuition on the general perspectives and potential conflicts that may occur while using simple heuristic rules for the solution of the problem at scheduling phase. Based on the derived dominance rules, one may assert when such conflicts may be efficiently resolved, and how. A practitioner may either choose to follow these rules for particular real-life instances or even modify some data that might be altered to avoid these conflicts and obtain an optimal solution for a modified instance, adjusting the production to the conditions and dominance rules. A practitioner may also choose to go deeper and expand the given optimality conditions and dominance relations into more complex heuristic methods depending on the nature of the problem instances that arise in his/her particular application.

For future work, it would be interesting to extend the presented results (limited to a single-machine environment) to more general scheduling models such as multiprocessor and shop scheduling.

Corrigendum

This article was originally published with errors. This version has been corrected. Please see Corrigendum (http://dx.doi.org/10.1080/23311916.2017.1336199).

Cover image

Source: Nodari Vakhania.

Additional information

Funding

This work was supported by PRODEP.direct funding for this research.

Notes on contributors

Nodari Vakhania

Nodari Vakhania is a titular professor at the Centro de Investigacion en Ciencias, the State University of Morelos, Mexico and at the Institute of Computational Mathematics of the Georgian Academy of Sciences. He has received his PhD degree in mathematical cybernetics at the Russian Academy of Sciences in 1991, and the doctoral degree (habilitation) in mathematical cybernetics at the Georgian Academy of Sciences in 2004. His main research interests include design and analysis of algorithms, discrete optimization, computational complexity and scheduling theory. He has been interested in scheduling problems with job release times and due dates, and has developed novel efficient methods for their solution (so-called Blesscmore methods). The current work, carried our in collaboration with his PhD student Elisa Chinos, is part of this project.

Notes

Part of this work, in a preliminary form, was presented at the 4th Int. Conference on Mathematical, Computational and Statistical Sciences (MCSS 2016) and Int. Conference on Abstract and Applied Analysis (ABAPAN 2016)).

1 In this section n stands exclusively for the number of elements in SUBSET SUM; in the remained part, n denotes the number of jobs