An EPTAS for Minimizing the Total Weighted Completion Time of Jobs with Release Dates on Uniformly Related Machines

The equivalence for identical machines noted in [30] (which holds also for the case with release dates) follows from the next property. An optimal solution to one problem is also an optimal solution to the other problem, since the two values of the objective functions differ by an additive constant which is common to all feasible solutions, where this constant depends on the input. Using this idea, they proved that in the case where the ratio between the maximum density and the minimum density of input jobs is not larger than a constant, it is possible to convert methods of Alon et al. [3, 4] to obtain an EPTAS for this restricted setting. In [13], we have used the approach of [30] and we developed new approaches (used later by [24] for the ${\mathrm{\ell }}_p$ norm minimization problem on uniformly related machines) in order to present an EPTAS for the problem without release dates. These ideas fail to work when release dates are present. Afrati et al. [1] were successful in overcoming difficulties in the design of approximation schemes by rounding the input parameters and then structuring the input in a way that a job is processed promptly after its release date. Using this structure, each machine has a constant number of states (where a state of a machine is the next time in which it becomes available for processing another job), and one can apply dynamic programming on the time-horizon to schedule the jobs while keeping track of the number of machines in each state, and the number of unscheduled jobs of each large size that were released at any given time in the last few release dates (and similarly, for the total volume of unscheduled jobs seen as small that were released in those last few release dates). Chekuri and Khanna [8] extended these techniques of [1] to the setting of uniformly related machines (with release dates). The time complexity of the time-horizon dynamic programming is too large if one seeks for an EPTAS due to the following. The number of possible states of machines is clearly a constant dependent on $\epsilon$, and we need to recall the number of machines in each state, and thus the degree of $m$ in the polynomial of the running time depends on $\epsilon$, which violates the conditions on the running time of an EPTAS. Thus, the methods of [1, 8] fail completely when one tries to obtain an EPTAS for these problems with release dates (even for identical machines).

In the main part of the paper we prove our result which is an EPTAS for the non-preemptive scheduling problem with release dates on uniformly related machines so as to minimize the total weighted completion time of the jobs. Before presenting the detailed description of the scheme, we present an overview. Omitted proofs can be found in the full version of this work.

We apply two different shifting steps. The first shifting step is on the release dates. In this step we increase release dates of a small portion of the jobs (the amount of jobs is selected based on contribution to cost), but the increase is by a very large (constant) multiplicative factor. The goal of this increase of some release dates is to create large time differences between groups of release dates, so that sub-inputs of very different release dates could be solved almost independently, though they are not really independent instances. Our bound on the total size of jobs with a common release date is per density, and it is often not really possible to schedule all jobs quickly after their release dates. Thus, it can happen that jobs of much smaller release dates should be combined into a solution for later release dates. In these cases, the assignment of such jobs can be restricted to gaps of the schedule (a specific type of idle time), rather than treating these jobs similarly to jobs whose release dates are recent. By slightly stretching time [1], there are suitable gaps with sufficient frequency in any schedule. Since we have an upper bound on the total size of jobs with a common density, and because we will solve each sub-input (of all jobs with similar release dates after this shifting step) by solving a series of bounded instances (with bounded ratios of densities), we will maintain a property that after the last release date of a sub-input, the density of jobs assigned to a common machine deteriorates geometrically (along time). Thus, postponing jobs by some constant multiplicative factor can be charged to the total cost of the earlier jobs on that machine (in the solution to the sub-input) that have much higher densities than the postponed jobs, and it does not increase the cost significantly. Therefore, in time intervals where the solutions to different sub-inputs contradict (i.e., two or more solutions try to schedule jobs at the same time) the jobs corresponding to earlier sub-inputs will be delayed to the gaps of the latest sub-input (among the gaps of the sub-inputs with the contradicting solutions) and this delay is charged to the jobs of these earlier sub-inputs that are not delayed.

Later, we will apply shifting on densities. The goal is to create inputs with small numbers of possible parameters, such that there is a major difference between parameters of subproblems. Unlike the variant without release dates where solutions of different densities were concatenated, which was possible due to large differences between the sets of densities for subproblems (see [11, 13]), combining solutions of very different densities is extremely challenging in the case with release dates that we study here. Jobs cannot run before their release dates, and if one solution is sparse in some time interval (a large part of this interval consists of idle time), we would like another solution to take over, in order to exploit that time, and to avoid postponing all jobs (which could result in increasing their costs significantly). Yet, that solution is still not sufficiently good in some cases, as the schedule of jobs with very high densities must be done carefully, and they cannot be delayed (compared to their schedule in optimal solutions) in any solution (as such a delay may cause a major increase in the total cost). On the other hand, it harms the solution to delay multiple jobs (even if their densities are not very large) due to a sparse time slot (with high density jobs). Thus, the schedule of different subproblems needs to be coordinated, and these subproblems must be taken care of delicately. To overcome this notoriously difficult task, we apply a series of guessing steps and transformations on the solutions to ensure that these bad cases simply do not happen. Intuitively, we will ensure that for every pair of solutions, every relatively fast machine, and every time interval, the following will hold. If one solution is a sparse solution during a given time interval (in which case the solution cannot be charged for postponing starting times of other solutions till later), the second solution will be such that no job occupies (at least) the entire time interval. We employ gaps in schedules to combine unassigned jobs, and to allow the application of modifications of solutions.

More precisely, given a solution to a sub-input (resulting from the step of release dates shifting) we define a color of a machine to be the subset of intervals between consecutive times of release dates (of jobs of that sub-input) in which the machine has either some idle time or a starting time of at least one job. Using time stretching, we have small gaps in this time interval in each one of the two cases. A machine is a pink machine if its color is the set of all intervals between consecutive times that are release dates. A palette of a schedule is the vector of colors of its (constant number of) its fastest machines. We show that we can restrict ourselves to solutions that have (at least one) pink machine among their fastest machines, and we guess the palette of a near optimal solution with the property that it has a pink machine (observe that the number of possible palettes is a constant and thus we can emulate this guessing step via exhaustive enumeration). In what follows we will restrict ourselves to solutions corresponding to this guessed palette. This guessed palette will allow us to coordinate the different subproblems resulting from the shifting on the densities step as we discuss next.

After the step of guessing of the palette, we apply the shifting method on the densities, in order to partition the sub-input of similar release dates into several subproblems with the property that in each such subproblem the ratio between the maximum density of a job and the minimum density of a job is bounded from above by a constant (and by the rounding step, this means that the number of distinct densities in such subproblem is a constant), and for two jobs belonging to distinct subproblems, the two densities are not close. Using the existence of a pink machine, we show that we can restrict ourselves further to solutions satisfying that for every machine (which is not one of the constant number of fastest machines) and every time interval between consecutive release dates, either the machine is completely idle, or it is busy for a large portion of the time interval (and thus can be charged for postponing jobs of subproblems with much lower density after the last release date of this sub-input), and we say that this machine has no sparse interval. Therefore, in such solutions for every machine and every time interval, either no solution of a subproblem has a sparse interval, or all of them have either gaps or starting times in this time interval (this can happen only on a constant number of fast machines). In this way, we solve the issue of sparse versus fully occupied time intervals.

Then, we can build a solution for a sub-input from the solutions to its subproblems by processing one machine at a time, and this is carried out by processing the solutions from higher densities subproblems to lower densities subproblems. The embedding of one solution in another solution is done by uniting the set of jobs starting at a given time interval greedily until there is no space for additional jobs (the remaining jobs are postponed to later time intervals). When a time interval has no space for additional jobs, it is not a sparse time interval, and it can be charged for postponing the jobs of lower densities to later starting time (due to the large difference in densities between subproblems, which was achieved by shifting).

The next step processes the job set of each such subproblem, and in cases where there is a release date for which the set of jobs with this release date can be processed on one of the (constant number of) fastest machines without consuming too much of its processing time (and without violating its color), then we do that and remove this set of scheduled jobs from the subproblem. This step has a minor impact on the cost of the resulting solution, and it will help us to bound the additional cost due to rounding of the solution for the MILP in the last step. Finally, we use the mixed-integer linear program (MILP) paradigm to approximate each subproblem. Here, we use time-dependent configurations. Each such time-dependent configuration encodes the speed of the machine (and its index if it is one of the machines whose color is encoded in the palette), and defines the set of large jobs (or an approximated total size of small jobs) of every given density that starts running in every time interval. Since we consider instances with a constant number of release dates and a constant number of densities, we get that for every speed, the number of configurations with this encoded speed is a constant. In the MILP, we will require the variables of configurations of the (constant number of) fastest machines to be integral as well as configurations with a constant number of speeds (of speeds close to those of the fastest machines). All other variables are fractional, and thus the number of integral variables will be a constant.

The rounding of the solution for the MILP (to obtain an actual schedule) is carried out in several steps. The first one is similar to the case without release dates [11, 13] (in which every machine is slightly overused by increasing the total length of small jobs assigned to it), and schedule all the remaining jobs (there are such jobs due to rounding down the variables of machine configurations corresponding to slow machines) to start in the same time interval on the pink machine. This will be possible by time stretching of the schedule on that machine using the large ratio between the speed of the pink machine and the machines whose configuration variables are allowed to be fractional.

We argue that the rounded solution of the MILP satisfies the property that the maximum load of any machine is bounded from above by a constant multiplied by the maximum release date. In turn, this means that the solution obtained for each sub-input (with a bounded number of release dates but with an unbounded number of densities) satisfies that the densities of jobs deteriorate geometrically. This is exactly the property that we use to bound the impact of uniting the solutions to the sub-inputs into one solution.

We provide further details regarding the approximation scheme in what follows. A complete version of the description of the approximation scheme explained here is given in the full version of this work.

As a first step, we convert input $A$ (which consists of $m$ machines with their speeds and $n$ jobs with their attributes) into a rounded instance $A^{\prime }$. Let $a_{\min }={\min }_{1\le j\le n}{a}_j$. Let $\beta ={\delta }^2\cdot a_{\min }$. The sets of jobs and machines are the same as in $A$ (possibly with different attributes). Let $r_j^{\prime }={(1+\delta )}^{\lceil {\log }_{1+\delta }({\rho }_j+\beta )\rceil }$ be the release date of job $j$. Note that ${\rho }_j+\beta >0$, so $r_j^{\prime }$ is well-defined for any $j$ (even if ${\rho }_j=0$) and $r_j^{\prime }\ge {\rho }_j+\beta >{\rho }_j$. Let $s_i={(1+\delta )}^{\lfloor {\log }_{1+\delta }{v}_i\rfloor }\le v_i$ be the speed of machine $i$ in instance $A^{\prime }$, where $s_i>0$ since $v_i>0$. Let $w_j={(1+\delta )}^{\lceil {\log }_{1+\delta }{\omega }_j\rceil }\ge {\omega }_j$ and $p_j={(1+\delta )}^{\lceil {\log }_{1+\delta }{a}_j\rceil }\ge a_j$ be the weight and size (respectively) of job $j$ in instance $A^{\prime }$. It will also hold that $r_j^{\prime }\le (1+\delta )\cdot ({\rho }_j+\beta )$, $s_i\ge \frac{v_i}{1+\delta }$, $w_j\le (1+\delta )\cdot {\omega }_j$, and $p_j\le (1+\delta )\cdot a_j$. Using the new notation, for a given schedule, the completion time of $j$ is still denoted by $C_j$, and its weighted completion time is $w_j\cdot C_j$. Note that $1=s_1\ge s_2>\mathrm{\cdots }\ge s_m>0$ (the sorted order of machines is preserved and the largest speed is unchanged). Let $𝒪$ and ${𝒪}^{\prime }$ denote optimal solutions for $A$ and $A^{\prime }$ respectively.

Given a schedule (a solution) $SOL$ defined for a given input, let the time-augmented solution $TA(SOL,\upsilon )$ for some $\upsilon >1$ and the same input (the same set of jobs and the same set of machines) be the solution where each job is assigned to the same machine as in $SOL$, and the completion time of each job is $\upsilon$ times its completion time in $SOL$. In the next lemma we show that if $SOL$ is a solution for $A$, then $TA(SOL,\upsilon )$ is a solution for $A$ as well.

A schedule $SO{L}^{\prime \prime }$ for $A^{\prime }$ is called timely if for every job $j$, the starting time of $j$ is at least ${(1+\delta )}^{\lceil {\log }_{1+\delta }(\delta \cdot \frac{p_j}{s_i})\rceil }$, where $i$ is the machine that runs $j$ in $SO{L}^{\prime \prime }$. In particular, the starting time of $j$ in a timely schedule is at least $\delta \cdot \frac{p_j}{s_i}$. To prove that $SO{L}^{\prime \prime }$ is timely, it is sufficient to prove that for every job $j$, the starting time of $j$ in $SO{L}^{\prime \prime }$ is at least $\delta \cdot (1+\delta )\cdot \frac{p_j}{s_i}$.

Given a solution $SOL$ for $A$, we will be able to use $TA(SOL,\upsilon )$ as a solution for the rounded instance $A^{\prime }$ for certain values of $\upsilon$. The next lemma specifies cases such that this is indeed a valid schedule for $A^{\prime }$, and moreover it is a timely schedule. This condition on $\upsilon$ will be a sufficient one.

In what follows, when we are given a solution $SOL$ for $A$, we let $\overline{SOL}=TA(SOL,{(1+\delta )}^4)$. We use $\overline{SOL}$ as a solution for $A^{\prime }$ and not only for $A$.

In what follows, we will only consider timely (and valid) schedules for $A^{\prime }$. Let ${𝒪}^{\prime \prime }$ denote an optimal timely schedule for $A^{\prime }$.

In the analysis of algorithms for $A^{\prime }$, we will use pseudo-costs which we will define now, rather than actual costs. The completion time of any job is strictly positive, and we use this property in the definition. The pseudo-cost of job $j$ whose completion time $C_j$ satisfies $C_j\in [{(1+\delta )}^i,{(1+\delta )}^{i+1})$ is defined as $w_j{(1+\delta )}^{i+1}$ (that is, we round its completion time up to the next power of $1+\delta$ for the calculation of its pseudo-cost such that the completion time is increased even if it is already an integer power of $1+\delta$). Let ${𝒪}_{PC}$ denote an optimal timely solution for $A^{\prime }$ with respect to pseudo-cost (that is, the total pseudo-cost of all jobs is minimized). Let $PC(SOL(A^{\prime }))$ denote the pseudo-cost of $SOL$ for input $A^{\prime }$.

Given the last lemma we find that in order to obtain an approximate (within a factor of $1+O(\epsilon )$) schedule for $A$ with respect to the total weighted completion time, it is sufficient to consider timely schedules and pseudo-costs, and find an approximate schedule (within a factor of $1+O(\epsilon )$) for the latter problem.

Before presenting the next steps of our scheme, we define some procedures for modifying a solution. These procedures that we develop here will be invoked throughout the further steps of our algorithm.

We consider input $A^{\prime }$ and timely schedules. In what follows we only discuss pseudo-costs. As we saw, a resulting approximate solution can be used as an approximate solution for $A$.

We slightly abuse notation and use $SOL(A^{\prime })$ to denote the pseudo-cost of $SOL$ for $A^{\prime }$. Let ${𝒥}_{i,\mathrm{\ell }}$ denote the time interval $[{(1+\delta )}^i,{(1+\delta )}^{i+1})$ on machine $\mathrm{\ell }$. The total size of jobs for which both the starting time and completion time are within this interval (on machine $\mathrm{\ell }$) is at most $s_{\mathrm{\ell }}\cdot \delta \cdot {(1+\delta )}^i$, which is called the length of this interval. In what follows we let $\theta$ denote the smallest value of $i$ such that ${(1+\delta )}^{\theta }$ is a release date of some job of $A^{\prime }$.

Since we use pseudo-costs, we will represent schedules by specifying for each job $j$ the machine that runs it, the interval where $j$ starts, and the interval that contains the completion time of the job (both being time intervals of the same machine where for a time interval, both the start point and the endpoint are integer powers of $1+\delta$). Note that if the completion time of $j$ is ${(1+\delta )}^i$ (on some machine $\mathrm{\ell }$), which is the right endpoint of the previous interval and the start endpoint of ${𝒥}_{i,\mathrm{\ell }}$, then we say that the completion time of $j$ belongs to $J_{i,\mathrm{\ell }}$ even though the time slot that $j$ runs in is $[{(1+\delta )}^i-\frac{p_j}{s_i},{(1+\delta )}^i)$ (so $j$ is completed just before ${𝒥}_{i,\mathrm{\ell }}$ starts, but the completion time of $j$ is ${(1+\delta )}^i$, and this is a point of ${𝒥}_{i,\mathrm{\ell }}$). Alternatively, it is possible to state, for each interval, the list of jobs whose starting times are in this interval, and the list of jobs whose completion times are in this interval. The cost of the schedule can be computed by computing the total cost of all intervals. The cost of ${𝒥}_{i,\mathrm{\ell }}$ is ${(1+\delta )}^{i+1}$ times the total weight of jobs whose completion times are in ${𝒥}_{i,\mathrm{\ell }}$. Obviously, additional conditions are required for such lists to ensure that a list originates in a valid schedule (where an exact completion time is assigned to each job), and a complete schedule of the same cost (i.e., pseudo-cost) can be constructed. For example, if job $j$ has a starting time in ${𝒥}_{i_1,\mathrm{\ell }}$ and completion time in ${𝒥}_{i_2,\mathrm{\ell }}$, where $i_2-i_1\ge 2$, then for any , no job can have a starting time or a completion time in ${𝒥}_{i^{\prime },\mathrm{\ell }}$. Moreover, the total size of jobs that have to run in a sequence of consecutive intervals cannot exceed the total length of the intervals. We say that a schedule defined by such a list is timely if for every job $j$ with starting time in ${𝒥}_{i,\mathrm{\ell }}$ it holds that $\delta \cdot \frac{p_j}{s_{\mathrm{\ell }}}\le {(1+\delta )}^i$, that is, if the minimum starting time that it may receive satisfies the condition for timely schedules for this job. This is equivalent to the original definition, since the thresholds for starting times in that definition are integer powers of $1+\delta$. In the next lemma we formulate necessary and sufficient conditions for a list to represent a valid timely schedule.

We will have that for every timely schedule that is given as a list, every schedule that is created from the list (i.e., choosing a permutation of the jobs that start and complete in a common interval) results in a timely schedule.

For a job $j$ of size ${(1+\delta )}^i$, let its stretched size be ${(1+\delta )}^{i+1}$. We define a stretched input $\overline{A^{\prime }}$ where the size of each job is stretched and its processing time is exactly $1+\delta$ times larger. The other properties of the stretched input are unchanged compared to the original input in the sense that it consists of the same machines and jobs as $A^{\prime }$, each machine has the same speed in both inputs, and each job has the same release date in both inputs.

Given a schedule $SOL$ for $A^{\prime }$, we define a schedule $S(SOL)$, called the shifted schedule of the schedule $SOL$, which is defined for $\overline{A^{\prime }}$. If job $j$ has a starting time in ${𝒥}_{i_1,\mathrm{\ell }}$ and completion time in ${𝒥}_{i_2,\mathrm{\ell }}$ (where $i_2\ge i_1$) in $SOL$, we define its starting time and its completion time in $S(SOL)$ to be in the intervals ${𝒥}_{i_1+1,\mathrm{\ell }}$ and ${𝒥}_{i_2+1,\mathrm{\ell }}$, respectively.

Schedule $S(SOL)$ can obviously be used also as a schedule for an input where the size of each job in $A^{\prime }$ is stretched by some factor in $[1,1+\delta ]$ (the need to use this property is one of the reasons that we consider $S(SOL)$ as an assignment of a machine and completion time for each job), and it remains timely since jobs can only start later while their sizes can only decrease. This argument is valid even if the stretch factors of different jobs may be different, and also if all stretch factors are equal to $1$ (that is, the input is simply $A^{\prime }$).

Given a timely schedule $\widehat{S}$ for an input $\overline{A^{\prime }}$, we do not modify the input, but we define a new schedule called the schedule obtained from $\widehat{S}$ by time stretching by a factor of $1+\delta$, as follows. If $j$ is assigned to run (in $\widehat{S}$) on machine $\mathrm{\ell }$ during $[t,t^{\prime })$, we obviously have $p_j=s_{\mathrm{\ell }}(t^{\prime }-t)$. We reserve the time period $[(1+\delta )t,(1+\delta )t^{\prime })$ on machine $\mathrm{\ell }$ for job $j$ (where $(1+\delta )t$ is the reserved starting time of $j$, and $(1+\delta )t^{\prime }$ is the reserved completion time of $j$). This interval is too long for the job, and we place the job in the middle. Specifically, we assign $j$ to start at time $(1+\delta )\cdot t+\frac{\delta \cdot p_j}{2s_{\mathrm{\ell }}}$, where this time will be called the basic starting time of $j$. Scheduling the job in the middle of the interval allows us to keep the time where exactly half of the job is completed unchanged (but stretched together with the schedule). Obviously, no job will start running before its release date, and the schedule remains timely. The basic completion time of $j$ will be $(1+\delta )\cdot t+\frac{\delta \cdot p_j}{2s_{\mathrm{\ell }}}+\frac{p_j}{s_{\mathrm{\ell }}}$, that is,

If $j$ originally completed during ${𝒥}_{i,\mathrm{\ell }}$ in $\widehat{S}(\overline{A^{\prime }})$, then both its reserved and basic completion times will be no later than in the interval ${𝒥}_{i+1,\mathrm{\ell }}$, so the cost increases by at most a multiplicative factor of $1+\delta$.

Next, for any interval ${𝒥}_{i,\mathrm{\ell }}$, such that there is no job whose reserved time interval contains ${𝒥}_{i,\mathrm{\ell }}$, shift all jobs that start and end during this time interval such that they run continuously as early as possible, that is, either starting at the beginning of ${𝒥}_{i,\mathrm{\ell }}$, or just at the basic completion time of a job that starts in an earlier time interval and completes in ${𝒥}_{i,\mathrm{\ell }}$ (jobs are reassigned to run without idle time, ignoring the time that was reserved before jobs are started or after they are completed). Moreover, if there is a job whose reserved starting time is during ${𝒥}_{i,\mathrm{\ell }}$, its reserved completion time is in another time interval, but it is small for ${𝒥}_{i,\mathrm{\ell }}$, where we define small for ${𝒥}_{i,\mathrm{\ell }}$ such that its size is smaller than ${\delta }^{10}$ times the length of the interval, it is also shifted to start as early as possible. The set of these jobs, that we call the jobs of ${𝒥}_{i,\mathrm{\ell }}$, can be processed in any order, as long as the length of the interval is sufficient to accommodate all of them such that their completion times are within this time interval. The new starting times and completion times will be called (with a slight abuse of notation) actual starting times and actual completion times, respectively. For jobs whose time slots are not modified, the actual starting times and actual completion times are equal to the basic starting times and basic completion times, respectively.

Let $U$ denote the total size of the jobs whose reserved starting times and reserved completion times are in ${𝒥}_{i,\mathrm{\ell }}$. If there is a job whose reserved starting time is in this time interval but its reserved completion time is not, consider this job and denote it by $x$. The basic starting time of $x$ is in ${𝒥}_{i,\mathrm{\ell }}$ or in a later interval (this may happen because the basic starting time is larger than the reserved starting time), and the basic completion time is larger than its basic starting time. Let $U_2$ denote the total size of $x$ that can run during ${𝒥}_{i,\mathrm{\ell }}$ between its basic starting time and the minimum between its basic completion time and the end of the interval (this value can be zero even if $x$ exists). Let $U_2^{\prime }$ be the size that can be run between the reserved starting time of $x$ and the minimum between the basic starting time of $x$ and the end of the interval (letting $U_2=U_2^{\prime }=0$ if no such job exists). Similarly, if there is a job with a reserved starting time in an earlier time interval on the same machine and a reserved completion time in ${𝒥}_{i,\mathrm{\ell }}$, let $U_1$ denote the total size of this job that can run during ${𝒥}_{i,\mathrm{\ell }}$ until its basic completion time, and let $U_1^{\prime }$ the size that can run in ${𝒥}_{i,\mathrm{\ell }}$ after the basic completion time and until the reserved completion time (where $U_1=U_1^{\prime }=0$ if no such job exists).

For a fixed interval ${𝒥}_{i,\mathrm{\ell }}$ let $Z=s_{\mathrm{\ell }}\cdot \delta \cdot {(1+\delta )}^i$ denote its length.

Consider a (timely) schedule $\widehat{S}$ for $\overline{A^{\prime }}$ and the solution $\overline{S}$ obtained from $\widehat{S}$ by time stretching by a factor of $1+\delta$. Let ${𝒥}_{i,\mathrm{\ell }}$ be an interval that is not contained in a reserved time interval of any job. By the last claim, this interval contains an idle time of length at least ${\delta }^3$ times the length of the interval, and such idle time in an interval ${𝒥}_{i,\mathrm{\ell }}$ is called a gap in ${𝒥}_{i,\mathrm{\ell }}$. The lower bound on the length is found by $(U+{\delta }^2\cdot Z)-(U+{\delta }^{10}\cdot Z)={\delta }^2(1-{\delta }^8)\cdot Z>{\delta }^3\cdot Z$ for $\delta \le \frac{1}{36}$.

Observe that there might be other time intervals containing idle time which are not gaps. This happens in the case that the time interval is contained in a reserved period of some job and at least one of the basic starting time and the basic completion time is an inner point of that interval.

Consider the solution $\overline{S}$ obtained from a timely schedule $\widehat{S}$ by time stretching by a factor of $1+\delta$, and let $j$ be a job whose starting time in $\widehat{S}$ is in the interval ${𝒥}_{i,\mathrm{\ell }}$. The reserved starting and completion time of $j$ in $\overline{S}$ are not larger than $1+\delta$ multiplied by the starting time and completion time of $j$ in $\widehat{S}$. The processing time of $j$ on machine $\mathrm{\ell }$ is at most $\frac{{(1+\delta )}^i}{\delta }$ since $\widehat{S}$ is timely, and since the starting time of $j$ in $\widehat{S}$ is ${𝒥}_{i,\mathrm{\ell }}$. Thus, the completion time of $j$ in $\widehat{S}$ is at most ${(1+\delta )}^i+\frac{{(1+\delta )}^i}{\delta }=\frac{{(1+\delta )}^{i+1}}{\delta }$. In $\overline{S}$, the reserved completion time of $j$ is at most $\frac{{(1+\delta )}^{i+2}}{\delta }$, and the end of the time interval containing the reserved completion time of this job is at most $\frac{{(1+\delta )}^{i+3}}{\delta }$. Therefore, using $\frac{{(1+\delta )}^3}{\delta }\le \frac{1}{{\delta }^2}$ we conclude the following.

In what follows, given a time-stretched schedule, we refer to basic starting times and basic completion times simply as starting times and completion times, respectively.

We now return to focusing on the design of our EPTAS, and we consider the rounded input $A^{\prime }$ resulting from the standard rounding steps. Recall that the density of job $j$ in $A^{\prime }$ is the ratio $\frac{w_j}{p_j}$.

Our next goal is to create a new input from $A^{\prime }$ by increasing the release date of some of the jobs while keeping all other parts of the input unchanged, such that the following holds. There is a positive constant $z$, such that for every integer value of $t$, the set of jobs released at time ${(1+\delta )}^t$ of a common density can be scheduled on the $m$ machines to complete no later than time $z{(1+\delta )}^t$. This goal was achieved for identical machines by Afrati et al. [1] using a fairly straightforward exchange argument. The case of uniformly related machines is significantly more difficult because in the exchange argument for uniformly related machines (as opposed to the situation for identical machines), a small job that is delayed to a later time interval need not stay small since it may be assigned to a different (slower) machine. This difficulty was not observed by Chekuri and Khanna [8], and thus we cannot use their procedure. Therefore, in order to overcome this difficulty, we provide a new procedure that handles each density separately, and uses a fine partition of the jobs of each density for which we are able to show such a bound.

First, we define divisions of job sizes as follows. Let $\mathrm{\Delta }=\lceil {\log }_{1+\delta }2\rceil$. We have $\mathrm{\Delta }\le \frac{1}{\delta }$ as ${(1+\delta )}^{\frac{1}{\delta }}>2$ (which can be verified since $\frac{1}{\delta }$ is an integer). For a job size ${(1+\delta )}^i$, let $k_i$ be an integer such that $2^{k_i}\cdot {(1+\delta )}^i\in (1,2]$. Let $k_i^{\prime }=\lceil {\log }_{1+\delta }{2}^{k_i}\rceil +i$, where $k_i^{\prime }\le \mathrm{\Delta }$ as $2^{k_i}\cdot {(1+\delta )}^i\le 2$, and therefore $\lceil {\log }_{1+\delta }(2^{k_i}\cdot {(1+\delta )}^i)\rceil \le \lceil {\log }_{1+\delta }2\rceil$. Additionally, $k_i^{\prime }\ge 1$, as $2^{k_i}\cdot {(1+\delta )}^i>1$.

The division of a job of size ${(1+\delta )}^i$ is defined to be $k_i^{\prime }$, and its subdivision is $k_i$. The pseudo-size of such a job is defined to be ${\pi }_i=\frac{{(1+\delta )}^{k_i^{\prime }}}{2^{k_i}}$. Since , we have ${(1+\delta )}^{k_i^{\prime }-i}\ge 2^{k_i}$ and . Thus, we have (so the pseudo-size is not smaller than the size, but it is not much larger). Since every job has a value $k_i^{\prime }$, and $1\le k_i^{\prime }\le \mathrm{\Delta }$, the divisions $1,2,\mathrm{\dots },\mathrm{\Delta }$ form a partition of $[1,2)$.

More intuitively, the division of a size of a job (a power of $1+\delta$) is the part of $[1,2)$ that it belongs to when it is multiplied by an appropriate integer power of $2$. The subdivision is this last power of $2$. For example, a job of size ${(1+\delta )}^{-1}$ has the subdivision $1$, as . Its division is $\lceil {\log }_{1+\delta }2\rceil -1=\mathrm{\Delta }-1$, which means that once the size is multiplied by the appropriate power of $2$ (which is $2^1$ for this example), it becomes relatively close to $2$ (and indeed $\frac{1}{1+\delta }$ is not much smaller than $1$). Two other examples are jobs of sizes $1$ and $1+\delta$. The subdivisions of these jobs are $1$ and $0$, respectively, their divisions are $\mathrm{\Delta }$ and $1$ (and indeed the second size is not much larger than $1$).

Let $A^{\prime \prime }$ be $A^{\prime }$ such that the size of a job of size ${(1+\delta )}^i$ is replaced with the pseudo-size ${\pi }_i$. The values ${\pi }_i$ of one division form a divisible sequence, and more specifically, given two such distinct values of one division, the larger one divided by the smaller one is a positive integral power of $2$. In what follows we will schedule the jobs of $A^{\prime \prime }$ in some cases. Let $\widetilde{𝒪}$ be an optimal timely solution for $A^{\prime \prime }$ and recall that ${𝒪}^{\prime \prime }$ is an optimal timely schedule for $A^{\prime }$.

Recall that any job of size below ${\delta }^{10}\cdot s_{\mathrm{\ell }}\cdot \delta {(1+\delta )}^i={\delta }^{11}\cdot s_{\mathrm{\ell }}\cdot {(1+\delta )}^i$ is defined to be small for interval ${𝒥}_{i,\mathrm{\ell }}$. We also say that any job of size in $[{\delta }^{11}\cdot s_{\mathrm{\ell }}\cdot {(1+\delta )}^i,s_{\mathrm{\ell }}\cdot \delta \cdot {(1+\delta )}^i)$ is called medium for this time interval, any job of size in $[s_{\mathrm{\ell }}\cdot \delta \cdot {(1+\delta )}^i,\frac{s_{\mathrm{\ell }}}{\delta }\cdot {(1+\delta )}^{i+1})$ is called large for this time interval, and larger jobs (of size at least $\frac{s_{\mathrm{\ell }}}{\delta }\cdot {(1+\delta )}^{i+1}$) are called huge for the interval. Recall that a job that is huge for a given time interval cannot start during this time interval in a timely schedule, and a large job cannot be assigned to run only in the interval (it is not possible that both its starting time and completion time are in the interval due to the length of the interval). We say that a job is big for an interval if it is either medium or large for it. The following definition uses the pseudo-sizes of jobs that are their sizes in $A^{\prime \prime }$.

Since the considered schedule $A^{\prime \prime }$ is timely, jobs $j_1,j_2$ are not huge for ${𝒥}_{i_1,{\mathrm{\ell }}_1}$ and ${𝒥}_{i_2,{\mathrm{\ell }}_2}$, respectively. This means that for $j_{\psi }$ ($\psi =1,2$), if it is not small for ${𝒥}_{i_{\psi },{\mathrm{\ell }}_{\psi }}$, it has to be big for this interval. Note that in the case , if $i_1=i_2=i$, the case where $j_1$ is big for ${𝒥}_{i,{\mathrm{\ell }}_1}$ while $j_2$ is small for ${𝒥}_{i,{\mathrm{\ell }}_2}$, cannot occur since speeds are sorted (so machine ${\mathrm{\ell }}_2$ is not faster than ${\mathrm{\ell }}_1$).

This definition specifies fixed priorities on jobs. For jobs of equal sizes and densities, a job of a smaller release date has higher priority, and out of two such jobs with the same release date, the one of the higher index has a higher priority. For a fixed time interval, there are also priorities between jobs of one division that are small for it in the sense that the interval will contain jobs that are prioritized while jobs with a lower priority are assigned to start during a later interval or to a parallel interval (during the exact same time) on a machine of a higher index. The priority between two jobs of one size remains the same, and additionally, a larger job has a higher priority than a smaller job (this is defined per time interval, and only for jobs of the instance that are small for it). Obviously, given a time interval ${𝒥}_{i,\mathrm{\ell }}$, all jobs that are released at time ${(1+\delta )}^{i+1}$ or later are irrelevant for it and have no priority. Let $\overline{𝒪}$ denote an optimal organized schedule for $A^{\prime \prime }$ (in particular, $\overline{𝒪}$ must be timely).

We apply an additional transformation on release dates to obtain the instance $\tilde{A}$ from $A^{\prime }$ where the release date of $j$ is denoted by $r_j$ (and satisfies $r_j\ge r_j^{\prime }$). Other than modified release dates for some of the jobs, $\tilde{A}$ and $A^{\prime }$ have the same machines and the same jobs. The instance $\tilde{A}$ may contain release dates that do not exist in $A^{\prime }$, but all release dates are integer powers of $1+\delta$ and the smallest release date will remain ${(1+\delta )}^{\theta }$. Thus, any (timely) solution for $\tilde{A}$ is a (timely) solution for $A^{\prime }$ as well. In order to use a solution of $A^{\prime }$ for $\tilde{A}$, one has to show that each job $j$ that has a starting time in ${𝒥}_{i,\mathrm{\ell }}$ has $r_i\le {(1+\delta )}^i$ (while other aspects of feasibility follow from the feasibility for $A^{\prime }$). In particular, we can use an organized schedule for $A^{\prime \prime }$ as a schedule for $A^{\prime }$ and thus for $\tilde{A}$. In $\tilde{A}$, for every type of jobs, if too many (in terms of the number or the total size) pending jobs exist at time ${(1+\delta )}^i$, the release date of some of them is increased. This can be done when it is impossible to schedule all these jobs due to the lengths of intervals. We need to take into account jobs that have starting times in an interval ${𝒥}_{i,\mathrm{\ell }}$ even if their completion times are in later time intervals. Jobs with this property are called special. The total size of jobs that are not special will be at most the total lengths of time intervals. The process is applied separately and independently on every possible density.

We will define $\tilde{A}$ using a process that acts on increasing values of $i$ and at each step applies a modification on release dates of jobs whose current release date is ${(1+\delta )}^i$. For a given density $d$, initialize $r_j=r_j^{\prime }$ for every job $j$ of density $d$. For each possible size, create a list of preferences. In this list, jobs are ordered by non-decreasing release dates in $A^{\prime }$, and within every release date, by decreasing indices. In what follows, for any job $j$ we will refer to $r_j^{\prime }$ as the initial release date of $j$, and to the values $r_j$ as modified release dates. As these values will be changed during a modification process that we define (they can possibly be changed a number of times for each job), when we discuss such a value, we will always refer to the current value even if it will be changed later. We apply the process for $i=\theta ,\theta +1,\mathrm{\dots }$. The stopping condition will be the situation where for some $i$ there are no jobs whose modified release dates are at least ${(1+\delta )}^i$. If during the process for some $i$ there are no jobs with modified release date ${(1+\delta )}^i$, but there exist jobs with larger release dates (in this case these are both initial and modified release dates of those jobs), we skip this value of $i$ and move to the next value.

Recall that our goal is to increase some (modified) release dates of jobs where these jobs will not be started before the next possible release date, and to break ties consistently, we do this for jobs that would not be started before the next release date in an organized schedule. Since we are interested in organized schedules that are, in particular, timely, jobs that are huge for a given interval should not be scheduled a starting time in this interval.

For a given value of $i$, and a fixed density $d$, we consider jobs whose modified release date is ${(1+\delta )}^i$. Out of these jobs we will select a subset, and for every such $j$ in the subset, the current value of $r_j$ will remain ${(1+\delta )}^i$ and will not change later. For every job $j^{\prime }$ that is not selected (after applying the process to all machines), we modify its modified release date into $r_{j^{\prime }}={(1+\delta )}^{i+1}$. Initially, no job is selected. For every time interval ${𝒥}_{i,\mathrm{\ell }}$ (for some $1\le \mathrm{\ell }\le m$), for every size that is big (large or medium) for this interval and every density, select the unselected highest priority job $j$ such that $r_j={(1+\delta )}^i$. For sizes that no such job exists obviously no job is selected. So far we selected at most one job for every size and density among sizes that are not huge for the interval (for which we do not choose jobs) and sizes that are not small for the interval. We proceed to choosing additional medium jobs and to choosing small jobs.

For every size that is medium for this interval and every density, select an additional unselected $\frac{1}{{\delta }^{10}}$ highest priority jobs of this size (selecting all such jobs if less than $\frac{1}{{\delta }^{10}}$ such jobs exist). For every division $k$ and every density, consider the job sizes of this division that are small for this time interval in non-increasing order. For each size (that is small for the interval), unselected jobs of one size are selected according to priorities. Keep selecting unselected jobs according to priorities, moving to the next size if all jobs of one size have been selected, until the total size of selected jobs of division $k$ (and density $d$, that are small for ${𝒥}_{i,\mathrm{\ell }}$) is at least $s_{\mathrm{\ell }}\delta {(1+\delta )}^i$ (and thus their total size is at most $s_{\mathrm{\ell }}\delta {(1+\delta )}^i(1+{\delta }^{10})$, since any such job is small for ${𝒥}_{i,\mathrm{\ell }}$). If the total size of all these jobs is smaller than $s_{\mathrm{\ell }}\cdot \delta {(1+\delta )}^i$, all of them are selected. For a given triple $d,i,\mathrm{\ell }$, letting $Z=s_{\mathrm{\ell }}\cdot \delta {(1+\delta )}^i$, the total size of selected jobs is as follows. There are at most ${\log }_{1+\delta }\frac{1+\delta }{{\delta }^2}+1\le \frac{1}{{\delta }^3}+2$ sizes of large jobs, each having a size of at most $\frac{1+\delta }{{\delta }^2}\cdot Z$. There are at most ${\log }_{1+\delta }\frac{1}{{\delta }^{10}}+1\le \frac{1}{{\delta }^{11}}+1$ sizes of medium jobs, each having a size of at most $Z$. To find an upper bound on the total size of small jobs that are selected, recall that there are at most $\frac{1}{\delta }$ divisions. The total size of selected large jobs is at most . The total size of selected medium jobs is at most . The total size of small jobs is at most $Z\cdot \frac{1}{\delta }(1+{\delta }^{10})$. The total size is therefore at most $\frac{Z}{{\delta }^{23}}$.

Let $t\ge r$, and schedule the jobs whose modified release date is $r$ starting at time $t$, such that the jobs scheduled on machine $\mathrm{\ell }$ are those that were selected for ${𝒥}_{i,\mathrm{\ell }}$ (where $r={(1+\delta )}^i$). The total size of the jobs of one density is at most $\frac{Z}{{\delta }^{23}}=\frac{s_{\mathrm{\ell }}{(1+\delta )}^i}{{\delta }^{22}}=\frac{s_{\mathrm{\ell }}\cdot r}{{\delta }^{22}}$ so the jobs of $\widehat{y}$ densities will be completed (on a machine of speed $s_{\mathrm{\ell }}$) within a time interval not longer than $\frac{r\cdot \widehat{y}}{{\delta }^{22}}$. To prove the second claim, note that the total size of jobs of one density and modified release date at most $r$ that will run on machine $\mathrm{\ell }$ is at most $\frac{s_{\mathrm{\ell }}\cdot r}{{\delta }^{22}}\cdot {\sum }_{i=0}^{{\log }_{1+\delta }r-\theta }\frac{1}{{(1+\delta )}^i}\le \frac{s_{\mathrm{\ell }}r}{{\delta }^{22}}\cdot \frac{1+\delta }{\delta }$, since previous interval lengths are smaller by a multiplicative factor which is a positive integral power of $\frac{1}{1+\delta }$ dependent on the distance to $r$. $◀$

Consider an optimal schedule ${𝒪}_s^{\prime }$, and let $R^{\prime }=\frac{\widehat{y}R}{{\delta }^{24}}$. We define $T$ as follows. Let be such that $T={(1+\delta )}^{\iota }$ for an integer $\iota$. Consider the jobs released by time $R$ whose completion times are above $T$ (and thus in their pseudo-costs, their weights are multiplied by at least $T(1+\delta )$). By Lemma 17, it is possible to schedule these jobs during $[T,T+\frac{R\widehat{y}}{{\delta }^{23}})$. We have , and therefore it is possible to remove all these jobs from ${𝒪}_s^{\prime }$, and schedule them within the time interval $[T,(1+\delta )T)$. As all jobs that are still running at time $T$ (jobs whose starting times are smaller than $T$ but their completion times are larger than $T$) are also removed, before the jobs are assigned again, the time interval $[T,(1+\delta )T)$ is idle on all machines. No reassigned job has an increased cost, and therefore the resulting schedule, ${𝒪}_s$ is optimal as well. We are done since . $◀$

This concludes the initial steps of our scheme. Together with later steps (see the full version of this work) we derive an EPTAS for our problem.