1 Introduction

In this paper, we address and combine two popular topics in scheduling theory: due-date assignment problems and controllable processing times. One influential effect of the Just-In-Time (JIT) production methodology on scheduling theory was the vast research on due-date assignment and scheduling problems. In this class of problems, the due-dates are decision variables and we seek to balance the inherent trade-off between early competitive due-dates on the one hand and late and, consequently, undemanding due-dates on the other. Three significant models were introduced: (i) CON (Common)—where all the jobs share a common due-date (Panwalkar et al. 1982); (ii) DIF (Different)—the unrestricted due date assignment method, in which each job can be assigned a different due date with no restrictions (Seidmann et al. 1981); and (iii) SLK (Slack)—where the job-dependent due-dates are often linear functions of the job processing times (Adamopoulos and Pappis 1996).

The vast majority of studies addressed the minsum versions, i.e., minimizing the total cost of earliness, tardiness and due-date of all jobs. These objective functions were studied with various machine environments, position-independent/dependent job processing times, constant/controllable job processing times, problems involving optional job-rejection, and with single/multi-agent settings. Recent articles include, among others, Wang et al. (2016), Yin et al. (2016), Gerstl et al. (2017), Mor (2017, 2019a), Mor and Mosheiov (2017), Cheng and Cheng (2018), Gao et al. (2018), Xiong et al. (2018), Ji et al. (2019), Geng et al. (2019), Liu et al. (2020), Liu and Jiang (2020) and Mor et al. (2020).

In this study, we combine very important classes of scheduling theory—due-date assignment and scheduling problems and convex resource allocation, and provide optimal algorithm solutions for very practical problems. We concentrate on the SLK model, i.e., due-date assignments based on common flow-allowance. Unlike minsum, the minmax version has not received appropriate research attention. In minmax problems, we aim to minimize the maximal cost among all jobs. The importance of these problems is threefold: (i) realize a value that demonstrates the utilization of the production system that can be compared to the competition; (ii) estimate the worst case performance of the production system; and (iii) treat all clients in an equal way. Typically, in minmax scheduling problems with common flow-allowance there are three cost components: earliness, tardiness, and flow-allowance. The first to consider single machine minmax scheduling and assignment problems with due-date based on flow-allowance were Mor and Mosheiov (2012a). Later, Mor and Mosheiov (2012b, 2016, 2017) extended the fundamental setting to identical parallel machines, proportionate flow-shop, and two competing agents, respectively.

In this paper, we combine the setting of due-date based on common flow-allowance and the very important and practical model of controllable processing times. Scheduling models with controllable processing times are very widespread and influential. Unlike most studies in scheduling theory that presume constant job processing times, research with controllable processing times assumes that the processing times may be controlled through allocating extended resources to job operations. Thus, the updated approach aims to address various real-life problems where the improved deployment of inputs in the production system is achieved by allocating added resource to the job processing. There are two dominant methodologies when addressing controllable processing times: (i) actual job processing times as a linear function of the amount of resource allocated to the processing of the job and (ii) actual job processing times as a convex decreasing function of the amount of resource allocated to the processing of the job. In their wide-ranging survey, Shabtay and Steiner (2007) state that “For many resource allocation problems in physical or economic systems, however, they do not use a linear resource consumption function, since it fails to reflect the law of diminishing marginal returns. This law states that productivity increases at a decreasing rate with the amount of resource employed.” Thus, in this paper, we assume that the job processing time is a convex decreasing function of the amount of resource allocated to the processing of the job. Recent articles with convex resource allocation include Liu et al. (2016, 2017), Sun et al. (2016), Wang et al. (2017) and Sun et al. (2019).

Many scheduling researchers have studied scheduling problems with variable job processing times, i.e., starting-time-dependent and/or position-dependent. The importance of this method is reflected in Gawiejnowicz (2008) with numerous variable processing time problems, different objective functions, and diverse machine settings. Other articles include Mor and Mosheiov (2011, 2012c, 2018), Rudek (2012), Sun et al. (2013), Agnetis et al. (2014), Agnetis and Mosheiov (2017), Gerstl et al. (2017), Pei et al. (2019) and Zhang et al. (2018). In general, the extension to variable job processing times significantly increases the computational complexity of the problems, whether the processing times are (i) restricted to monotone functions of the job starting times; (ii) position-dependent, i.e., representing aging or learning effects; and (iii) specific functions, e.g., linear or exponential.

Oron (2016) was the first to introduce the realistic and challenging generalization of position-independent workloads to position-dependent workloads. The author restricted the functional form of the workloads to reflect learning effect and studied minimizing makespan and total flowtime on a single machine, as well as minimizing total flowtime on parallel machines. Lu and Liu (2018) analyzed bi-criteria problems, where the first criterion is a scheduling measure and the second criterion is the total resource consumption cost. Mor (2019b) considered single machine minmax common due-window assignment and scheduling problems with convex resource allocation. Recently, Mor (2020) extended the results of Oron (2016) by omitting the restriction on the functional form of the workloads, and provided a unified approach for single machine scheduling with position‑dependent workloads and positional penalties.

Following Mor and Mosheiov (2012a), we focus on the minmax problem with due-date based on flow-allowance on a single machine, and extend their results by considering controllable job processing times. Firstly, we study position-independent workloads, and then proceed to the model of position-dependent workloads. Secondly, we generalize the due-date method to the due-window method. For the problems with position-independent workloads, we provide \(O(n)\) procedure solutions, whereas for the problems with position-dependent workloads, we introduce solution procedures with computational effort of \(O({n}^{3})\). Thus, in combining the minmax approach and controllable processing times, this study addresses theoretical and practical aspects in scheduling theory.

In Sect. 2, we provide the formulation. Sections 3 and 4 are dedicated to the setting of common due-date with position-independent and position-dependent workloads, respectively. In Sects. 5 and 6, we generalize the results of Sects. 3 and 4 to the method of common due-window, respectively. In Sect. 7, we provide conclusions and future research topics.

2 Formulation

A set of jobs \(\mathcal{J}\) needs to be processed on a single machine. All the jobs are available at time zero, and preemption is not allowed. The actual processing time of the job allocated to position \(j, j\in \mathcal{J}\) is defined as \({p}_{j}={\left(\frac{{w}_{j}}{{u}_{j}}\right)}^{k}\), where \({w}_{j}\) is a positive value reflecting the workload of the processing operation, \({u}_{j}\) is a decision variable demonstrating the amount of resource allocated to the processing operation, and \(k\) is a constant positive parameter. We also denote by \({w}_{max}\) the largest workload among all jobs, \({w}_{m\mathit{ax}}={\mathrm{max}}_{j\in \mathcal{J}}\left\{{w}_{j}\right\}\).

We assume a common flow-allowance denoted by \(q\), which is a decision variable. The due-date (DD) of job \(j\) is \({d}_{j}\) and defined as its processing time plus the job-independent constant \(q\):

$${d}_{j}={p}_{j}+q, j\in \mathcal{J}.$$

For a given schedule, the completion time of job \(j, j\in \mathcal{J}\) is denoted by \({C}_{j}\). We denote the makespan, i.e., the completion time of the last job to leave the system by \({C}_{max}\). Jobs completed before/after the due-date are considered as early/tardy jobs and incur penalties. The earliness of the job \(j\) is \({E}_{j}=\mathrm{max}\left\{0, {d}_{j}-{C}_{j}\right\}\) and the tardiness of job \(j\) is defined as \({T}_{j}=\mathrm{max}\left\{0, {C}_{j}-{d}_{j}\right\}, j\in \mathcal{J}\). There are three cost components: for earliness, tardiness, and to motivate the scheduler to set competitive due-dates there is an additional cost for the common flow-allowance. Let \(\alpha \) denote the unit earliness cost, \(\beta \) denote the unit tardiness cost, and \(\gamma \) denote the cost of delaying the due-dates by one time unit. We note that in a given schedule a specific job is either early or tardy, implying that its cost is \(\mathrm{max}\left\{\alpha {E}_{j}+\gamma q, \beta {T}_{j}+\gamma q\right\}=\mathrm{max}\left\{\alpha {E}_{j}, \beta {T}_{j}\right\}+\gamma q\).

We seek to find the optimal sequence and flow-allowance, such that the maximal cost among all jobs is minimized. Formally, the scheduling measure in this case is \(Z={\mathrm{max}}_{ j\in \mathcal{J}}\left\{\mathrm{max}\left\{\alpha {E}_{j}, \beta {T}_{j}\right\}+\gamma q^1 +{\delta D}\right\}\).

First, we focus on minimizing the scheduling measure, given that the total resource consumption cannot exceed an upper bound denoted by \(U\). We denote the problem by \({\varvec{P}}{\mathbf{1}}\) and, utilizing the three-field notation introduced by Graham et al. (1979), the first problem studied is,

$${\varvec{P}}{\mathbf{1}}: \,1\left|SLK\, DD,conv, {w}_{j}, \sum {u}_{j}\le U\right|Z.$$

Next, we extend the setting of common flow-allowance with position-independent workloads to the setting of position-dependent workloads, \({w}_{jr}\), implying that the workload of job \(j\) if assigned to position \(r\) is given by \({p}_{jr}={\left(\frac{{w}_{jr}}{{u}_{j}}\right)}^{k} , j, r = 1, \dots , n\).

Thus, the second problem, denoted by \({\varvec{P}}{\mathbf{2}}\), is:

$${\varvec{P}}{\mathbf{2}}:\, 1\left|SLK\, DD,conv, {w}_{jr}, \sum {u}_{j}\le U\right|Z.$$

Finally, we generalize the above results and address the method of due-window (DW) based on common flow-allowance. Thus, jobs that are completed within a time interval (a due-window) are not penalized, whereas jobs that are completed prior to or after the window, are penalized according to their earliness/tardiness. In due-window assignment problems, we seek simultaneously the start time and the size of the window. We address job-dependent due-windows based on common flow-allowance. The job-dependent due-window is denoted by \({D}_{j}\), such that the window of job \(j, j\in \mathcal{J}\) is given by \({D}_{j}=[{d}_{j}^{1}, {d}_{j}^{2}]\), where

$$\begin{aligned}{d}_{j}^{1}&={p}_{j}+{q}^{1}, j\in \mathcal{J}.\\{d}_{j}^{2}&={p}_{j}+{q}^{2}, j\in \mathcal{J}.\end{aligned}$$

Similar to the due-date method, the common flow-allowance constants \({q}^{1}\) and \({q}^{2}\) are decision variables, such that \({q}^{2}\ge {q}^{1}\). Since \({D}_{j}= {d}_{j}^{2}- {d}_{j}^{1}={p}_{j}+{q}^{2}- \left({p}_{j}+{q}^{1}\right)={q}^{2}-{q}^{1}=D, j\in \mathcal{J}\), the size of the due-window is identical for all jobs. The earliness of \(j\) is \({E}_{j}=\mathrm{max}\left\{0, {d}_{j}^{1}-{C}_{j}\right\}\) and the tardiness of job \(j\) is \({T}_{j}=\mathrm{max}\left\{0, {C}_{j}-{d}_{j}^{2}\right\}, j\in \mathcal{J}\). To motivate the scheduler to set reduced due-window size, there are four unit costs: for earliness, tardiness, the cost of the first flow-allowance, and extending the size of the due-window. Let \(\alpha \) denote the unit earliness cost, \(\beta \) denote the unit tardiness cost, \(\gamma \) denote the unit cost of the flow-allowance (\({q}^{1})\), and \(\delta \) denote the unit cost of extending the size of the due-window (\(D\)). Our aim is to find the optimal common constants and the optimal size of the due-window, as well as the sequence, that minimize the maximal cost among all jobs. Formally, the scheduling measure in this case is \(Z={\mathrm{max}}_{j\in \mathcal{J}}\left\{\mathrm{max}\left\{\alpha {E}_{j}+\gamma {q}^{1}+\delta D,\beta {T}_{j}+\gamma {q}^{1}+\delta D\right\}\right\}={\mathrm{max}}_{j\in \mathcal{J}}\left\{\mathrm{max}\left\{\alpha {E}_{j},\beta {T}_{j}\right\}+\gamma {q}^{1}+\delta D\right\}\).

The third and fourth problems, denoted by \({\varvec{P}}{\mathbf{3}}\) and \({\varvec{P}}{\mathbf{4}}\), respectively, are:

$$\begin{aligned}&{\varvec{P}}{\mathbf{3}}: 1\left|SLK\, DW,conv, {w}_{j}, \sum {u}_{j}\le U\right|Z,\\ &{\varvec{P}}{\mathbf{4}}: 1\left|SLK \,DW,conv, {w}_{jr}, \sum {u}_{j}\le U\right|Z.\end{aligned}$$

3 P1: \(1\left|SLK\, DD,conv, {w}_{j}, \sum {u}_{j}\le U\right|Z\)

Mor and Mosheiov (2012a) proved that the same problem with constant job processing time, \(1\left|SLK\, DD\right|Z\), can be formulated as the following Linear Program (LP), denoted by LP3.1:

$$ \begin{aligned} & LP3.1 \\ & \min Z \\ & {\text{s}}.{\text{t}}. \\ & \quad \begin{array}{*{20}l} {Z \ge aE_{1} + \gamma q = q\left( {\alpha + \gamma } \right) ,} \hfill \\ {Z \ge \beta T_{n} + \gamma q = q\left( {\gamma - \beta } \right) + \beta \left( {C_{max} - p_{n} } \right),} \hfill \\ {Z,q \ge 0 .} \hfill \\ \end{array} \\ \end{aligned} $$

In this linear program, the subscript is the index of the job assigned to the \(j\)th position in a given sequence. Analyzing LP3.1, the authors concluded that an optimal schedule exists in which the job with the largest processing time is scheduled last and the sequence of the remaining \(n-1\) jobs is immaterial.

Based on the above, the authors provided a closed form solution, where there are only two possible cases, and the optimal flow-allowance and cost function are given by:


Case 1: \(\gamma >\beta \)

$$ q^{*} = 0\;\;{\text{and}}\;\;Z^{*} = \beta \left( {C_{max} - p_{n} } \right) = \beta \mathop \sum \limits_{j = 1}^{n - 1} p_{j} . $$

Case 2: \(\gamma \le \beta \)

$$ q^{*} = \frac{\beta }{\alpha + \beta }\left( {C_{max} - p_{n} } \right) = \frac{\beta }{\alpha + \beta }\mathop \sum \limits_{j = 1}^{n - 1} p_{j} \;\;{\text{and}}\;\;Z^{*} = \left( {\alpha + \gamma } \right)q^{*} = \frac{{\beta \left( {\alpha + \gamma } \right)}}{\alpha + \beta }\mathop \sum \limits_{j = 1}^{n - 1} p_{j} . $$

In the context of this study, the actual processing time of each job is a function of the amount of resource allocated to it, i.e., \({p}_{j}={\left(\frac{{w}_{j}}{{u}_{j}}\right)}^{k}\). Therefore, and following the analysis of Cases 1–2 above, we conclude that the job with the largest workload should be scheduled last and, consequently, does not contribute to the cost function. Moreover, since the coefficients in both cases are constants, it suffices to minimize the term \({\sum }_{j=1}^{n-1}{p}_{j}={\sum }_{j=1}^{n-1}{\left(\frac{{w}_{j}}{{u}_{j}}\right)}^{k}\).

We conclude that the following observations are adequate:

Observation 3.1

An optimal schedule exists in which the job with the largest workload is scheduled last and the sequence of the remaining \(n-1\) jobs is immaterial.

Observation 3.2

An optimal schedule exists in which no resource is allocated to the job scheduled last.

From Observations 3.1–3.2, we conclude that \({p}_{n}={w}_{max}\).

Kaspi and Shabtay (2004) proved the following properties for an optimal solution of the problem \(1/w_{j} , \sum u_{j} \le U/C_{max}\):

  • The entire available resource is exploited.

  • The optimal resource allocated to job \(j, j\in \mathcal{J}\) is given by \({u}_{j}=U\frac{{w}_{j}^{\frac{k}{k+1}}}{\sum_{ j\in \mathcal{J}}{w}_{j}^{\frac{k}{k+1}}}\).

  • The actual processing time of job \(j, j\in \mathcal{J}\) is given by \({p}_{j}={\left(\frac{{\sum }_{j=1}^{n}{w}_{j}^{\frac{k}{k+1}}}{U}\right)}^{k}{w}_{j}^{\frac{k}{k+1}}\).

Combining Observation 3.1–3.2 and the results of Kaspi and Shabtay (2004), we can summarize the properties of an optimal solution for \({\varvec{P}}{\mathbf{1}}\):

Property 3.1

The entire available resource is consumed to reduce the processing time of jobs \(j=1, \dots , n-1\).

For ease of reading, we define a constant \(W\), such that \(W={\sum }_{j=1}^{n-1}{w}_{j}^{\frac{k}{k+1}}\).

Property 3.2

The optimal resource allocated to job \(j,j=1, \dots , n-1\) is given by \({u}_{j}=\frac{U}{W}{w}_{j}^{\frac{k}{k+1}}\).

Property 3.3

The actual processing time of job \(j,j=1, \dots , n-1\) is given by \({p}_{j}={\left(\frac{W}{U}\right)}^{k}{w}_{j}^{\frac{k}{k+1}}\).

Property 3.4

The optimal flow-allowance and cost function for \({\varvec{P}}{\mathbf{1}}\) are given by

Case 1: \(\gamma >\beta \)

$$ q^{*} = 0\;\;{\text{and}}\;\;Z^{*} = \beta \left( \frac{W}{U} \right)^{k} \mathop \sum \limits_{j = 1}^{n - 1} w_{j}^{{\frac{k}{k + 1}}} . $$

Case 2: \(\gamma \le \beta \)

$$ q^{*} = \frac{\beta }{\alpha + \beta }\left( \frac{W}{U} \right)^{k} \mathop \sum \limits_{j = 1}^{n - 1} w_{j}^{{\frac{k}{k + 1}}} \;\;{\text{and}}\;\;Z^{*} = \frac{{\beta \left( {\alpha + \gamma } \right)}}{\alpha + \beta }\left( \frac{W}{U} \right)^{k} \mathop \sum \limits_{j = 1}^{n - 1} w_{j}^{{\frac{k}{k + 1}}} . $$

Next, we present the formal solution procedure:

Solution procedure to problem \({\varvec{P}}{\mathbf{1}}\)

Step 1 Find the job with the largest workload and assign it to the last position.

Step 2 Use Property 3.2 to calculate the amount of resource allocated to jobs \(1,\dots ,n-1\).

Step 3 Use Property 3.3 to calculate the actual processing times to jobs \(1,\dots ,n-1\).

Step 4 Use Property 3.4 to determine the relevant case and calculate the optimal common flow-allowance and cost.

Theorem 3.1

The computational complexity of the proposed solution is \(O(n)\) time.

Proof

Step 1: Determining the job with the largest workload requires \(O(n)\) time. Steps 2–3: Computing the amount of resource allocated to each job and the actual processing time of each job, respectively, is done in \(O(n)\). Step 4: Calculating the optimal common flow-allowance and cost is done in \(O(n)\). Hence we conclude that the computational complexity is \(O(n)\).□

Numerical example 3.1

We solve the following 8-job problem:

The jobs workloads are: \({w}_{j}=\left(22, 24, 49, 50, 21, 14, 14, 6\right)\).

The cost parameters are: \(\alpha = 8\), \(\beta =10\) and \(\gamma =5\).

The available total resource is, \(U=12\) and \(k=0.5\).

Since \({w}_{max}=50\), switching the positions of jobs 4 and 8, we obtain one optimal sequence \(\left(1, 2, 3, 8, 5, 6, 7, 4\right)\).


Solution:

Since \(\gamma \le \beta ,\) the relevant case is Case 2.

The amount of resource allocated to each job is:

$${u}_{j}=\left(1.794, 1.847, 2.343, 1.163, 1.766, 1.543, 1.543, 0\right).$$

The actual processing times are:

$${p}_{j}=\left(3.502, 3.605, 4.573, 2.271, 3.448, 3.012, 3.012, 50\right).$$

The optimal common flow-allowance is \({q}^{*}=13.013\), implying that the due-dates are:

$$ d_{j} = \left( {16.515,16.618,17.586,15.284,16.461,16.025,16.025,63.013} \right). $$

The optimal cost is: \({Z}^{*}=169.165.\)

4 P2: \(1\left|SLK\, DD,conv, {w}_{jr}, \sum {u}_{j}\le U\right|Z\)

In this section, we extend the due-date setting by considering position-dependent workloads. The solution of Problem \({\varvec{P}}{\mathbf{2}}\) requires us to establish the optimal job sequence and then to evaluate the effect of allocating resource to each job on the optimal due-date and cost function. Let \({w}_{jr}\) denote the workload of job \(j\) if processed in position \(r\), \(j,r=1,\dots n\). Thus, the input for the problem contains three cost parameters, a matrix of \(n\times n\) job-position workloads, the upper bound on the total amount of resource consumption and the constant parameter. Consequently, the flow allowance and the derived due-dates are defined for any given realization of a job sequence, and we have to simultaneously seek the optimal job sequence and the optimal flow allowance. We conclude that for any given job sequence, Observations 3.1–3.2 and Properties 3.1–3.4 are still valid.

Oron (2016) solved the problem, \(1/{w}_{jr},conv,\sum_{ j\in \mathcal{J}}{u}_{j}\le U/{C}_{max}\) and proved that the objective function can be rewritten as:

$$f=\sum \limits_{j=1}^{n}\sum \limits_{r=1}^{n}{\left(\frac{{w}_{jr}}{{u}_{j}}\right)}^{k}{X}_{jr}=\frac{1}{{U}^{k}}{\left(\sum \limits_{j=1}^{n}{\left(\sum \limits_{r=1}^{n}{w}_{jr}^{k}{X}_{jr}\right)}^{\frac{1}{1+k}}\right)}^{1+k}.$$

Since \(U, k>0\), the author proved that minimizing \(f\) is equal to minimizing \({\left({\sum }_{r=1}^{n}{w}_{jr}^{k}{X}_{jr}\right)}^{\frac{1}{1+k}}\).

Subsequently, the author proved that obtaining the optimal job sequence is reduced to solving the following linear Assignment Problem (AP):

$$ \begin{aligned} & \min \mathop \sum \limits_{j = 1}^{n} \mathop \sum \limits_{r = 1}^{n} w_{jr}^{{\frac{k}{1 + k}}} X_{jr} \\ & s.t. \\ & \quad \begin{array}{*{20}l} {\mathop \sum \limits_{j = 1}^{n} X_{jr} = 1,} \hfill & {r = 1, \ldots ,n,} \hfill \\ {\mathop \sum \limits_{r = 1}^{n} X_{jr} = 1,} \hfill & {j = 1, \ldots ,n,} \hfill \\ {X_{jr} ,\;\;\;binary,} \hfill & {j = 1, \ldots ,n,\;\; r = 1, \ldots ,n.} \hfill \\ \end{array} \\ \end{aligned} $$

where

$${X}_{jr}=\left\{\begin{array}{ll}1,& {\text{if}}\, {\text{job}}\, j \,{\text{is}}\, {\text{assigned}}\, {\text{to}}\, {\text{position}}\, r\\ 0,& {\text{otherwise}}\end{array}\right..$$

After the optimal sequence is realized, the makespan can be calculated based on the effect of the additional resource allocation on the actual processing times.

From Property 3.4, the coefficient in the cost function is given by \(\rho =\left\{\begin{array}{ll}\beta,& Case\, 1\\ \frac{\beta \left(\alpha +\gamma \right)}{\alpha +\beta }, & Case \,2\end{array}\right.\).

Since, \(\rho \) is a job-independent and position-independent constant, then the cost function can be formulated as follows,

$$Z=\rho \sum_{j=1}^{n}\sum_{r=1}^{n-1}{\left(\frac{{w}_{jr}}{{u}_{j}}\right)}^{k}{X}_{jr}.$$

Thus, to minimize the cost function it suffices to minimize the term \(\sum_{j=1}^{n}\sum_{r=1}^{n-1}{\left(\frac{{w}_{jr}}{{u}_{j}}\right)}^{k}{X}_{jr}\).

Moreover, the latter implies that to solve Problem \({\varvec{P}}{\text{2}}\), we can use the assignment problem provided by Oron (2016) with a minor modification. Specifically, to obtain the optimal job sequence we need to solve the following special form \(n\times \left(n-1\right)\) AP (denoted AP4.1):

$$ \begin{aligned} & AP4.1 \\ & \min \mathop \sum \limits_{j = 1}^{n} \mathop \sum \limits_{r = 1}^{n - 1} \left( {\frac{{w_{jr} }}{{u_{j} }}} \right)^{k} X_{jr} \\ & s.t. \\ & \quad \begin{array}{*{20}l} {\mathop \sum \limits_{j = 1}^{n} X_{jr} = 1,} \hfill & {r = 1, \ldots ,n - 1,} \hfill \\ {\mathop \sum \limits_{r = 1}^{n - 1} X_{jr} \le 1,} \hfill & {j = 1, \ldots ,n,} \hfill \\ {X_{jr} , \;\; binary,} \hfill & {j = 1, \ldots ,n,\; r = 1, \ldots ,n - 1.} \hfill \\ \end{array} \\ \end{aligned} $$

where

$${X}_{jr}=\left\{\begin{array}{ll}1,& {\text{if}}\, {\text{job}}\, j\, {\text{is}}\, {\text{assigned}}\, {\text{to}}\, {\text{position}}\, r\\ 0,& {\text{otherwise}}\end{array}\right..$$

Now, we are ready to present the formal solution procedure.

Solution procedure to problem \({\varvec{P}}{\mathbf{2}}\):

Step 1 Apply AP4.1 to obtain the optimal sequence of the jobs assigned to positions \(1, \dots ,n-1\).

Step 2 Schedule the unassigned job to position \(n\).

Step 3 Use Property 3.2 to calculate the amount of resource allocated to jobs \(1,\dots ,n-1\).

Step 4 Use Property 3.3 to calculate the actual processing times to jobs \(1,\dots ,n-1\).

Step 5 Use Property 3.4 to determine the relevant case and calculate the optimal common flow-allowance and cost.

Theorem 4.1

The proposed solution solves \({\varvec{P}}{\mathbf{2}}\) in \(O({n}^{3})\) time.

Proof

Step 1: The computational complexity required for solving the assignment problem is known to be \(O({n}^{3})\). Step 2: Scheduling the unassigned job to position \(n\) is done in constant time. Steps 3–4: Computing the amount of resource allocated to each job and the actual processing time of each job, respectively, is done in \(O(n)\). Step 5: The calculation of the optimal cost and due-dates is done in \(O\left(n\right)\). Thus, the total complexity of the solution procedure is dominated by Step 1, and is \(O({n}^{3})\).□

Numerical example 4.1

We solve the \(8\times 8\) job-position workloads problem given in Table 1, where the cost parameters are: \(\alpha =2\), \(\beta =10\), and \(\gamma =15\).

Table 1 Example 2—job-position workloads
Full size table

The available total resource is \(U=14\) and \(k=1\).


Solution:

Applying AP4.1, we obtain an optimal sequence \(\left(6, 2, 7, 3, 5, 8, 4, 1\right)\).

Since \(\gamma >\beta \) the relevant case is Case 1.

The amount of resource allocated to each job is:

$${u}_{j}=\left(1.865, 1.865, 1.668, 0.834, 4.086, 1.180, 2.502, 0\right).$$

The actual processing times are:

$${p}_{j}=\left(2.681, 2.681, 2.398, 1.199, 5.874, 1.696, 3.597, 47.000\right).$$

The optimal common flow-allowance is \({q}^{*}=0\), implying that \({d}_{j}={p}_{j}, j=1,\dots ,n\).

The optimal cost is: \({Z}^{*}=201.248.\)

5 P3: \(1\left|{{S}}{{L}}{{K}}{{D}}{{W}},{{c}}{{o}}{{n}}{{v}},{{{w}}}_{{{j}}},\sum {{{u}}}_{{{j}}}\le {{U}}\right|{{Z}}\)

In this section, we generalize the results of the due-date method (Sect. 3) to the method of due-window. Mor and Mosheiov (2012a) proved that the problem with constant processing times can be formulated by the following LP, denoted LP5.1:

$$ \begin{aligned} & LP5.1 \\ & \min Z \\ & {\text{s}}.{\text{t}}. \\ & \quad Z \ge \alpha E_{1} + \gamma q^{1} + \delta \left( {q^{2} - q^{1} } \right) = q^{1} \left( {\alpha + \gamma - \delta } \right) + q^{2} \delta , \\ & \quad Z \ge \beta T_{n} + \gamma q^{1} + \delta \left( {q^{2} - q^{1} } \right) = q^{1} \left( {\gamma - \delta } \right) + q^{2} \left( {\delta - \beta } \right) + \beta \left( {C_{max} - p_{n} } \right), \\ & \quad q^{2} \ge q^{1} , \\ & \quad Z,q^{1} , q^{2} \ge 0 . \\ \end{aligned} $$

Examining LP5.1, the authors observed that similar to the due-date case, the job sequence is immaterial, except for the last job, which must have the largest processing time. Furthermore they proved several properties of an optimal solution and concluded that there are exactly four candidates for the optimal values of \({q}^{1}\) and \({q}^{2}\):


Case 1: The window has the maximum possible size.

$$ q^{1} = 0,\;\;q^{2} = C_{max} - p_{n} \;\;{\text{and}}\;\;Z = \delta q^{2} . $$

Case 2: The window is reduced to a due-date.

In this case, \({q}^{1}= {q}^{2}=q\), and three sub-cases must be solved and compared.


Sub-Case 2.1:

$$ q^{1} = q^{2} = 0,\;\;\;Z = \beta \left( {C_{max} - p_{n} } \right). $$

Sub-Case 2.2:

$$ q^{1} = q^{2} = q = \beta \frac{{C_{max} - P_{max} }}{\alpha + \beta }\;\;\;{\text{and}}\;\;\;Z = \beta \frac{\alpha + \gamma }{{\alpha + \beta }}\left( {C_{max} - P_{max} } \right). $$

Sub-Case 2.3:

$$ q^{1} = q^{2} = q = C_{max} - p_{n} \;\;\;{\text{and}}\;\;\;Z = (\alpha + \gamma )\left( {C_{max} - P_{max} } \right). $$

Property 5.1

The optimal cost function is given by \(Z=\mathit{min}\left\{\delta ,\beta ,\beta \frac{\alpha +\gamma }{\alpha +\beta },\alpha +\gamma \right\}({C}_{max}-{P}_{max})\).

Based on the above, we conclude that Observations 3.1–3.2 and Properties 3.1–3.3 and 5.1, still hold for Problem \({\varvec{P}}3\), and update the above results accordingly:

Property 5.2

The optional values of \({q}^{1}\) and \({q}^{2}\) and cost function for \({\varvec{P}}{\mathbf{3}}\) are given by,


Case 1: The window has the maximum possible size.

$$ q^{1} = 0,\;\;q^{2} = \left( \frac{W}{U} \right)^{k} \mathop \sum \limits_{j = 1}^{n - 1} w_{j}^{{\frac{k}{k + 1}}} \;\;{\text{and}}\;\;Z = \delta q^{2} = \delta \left( \frac{W}{U} \right)^{k} \mathop \sum \limits_{j = 1}^{n - 1} w_{j}^{{\frac{k}{k + 1}}} . $$

Case 2: The window is reduced to a due-date.

In this case, \({q}^{1}= {q}^{2}=q\), and we have to solve and compare three sub-cases.


Sub-Case 2.1:

$$ q^{1} = q^{2} = 0,\;\;\;Z = \beta \left( \frac{W}{U} \right)^{k} \mathop \sum \limits_{j = 1}^{n - 1} w_{j}^{{\frac{k}{k + 1}}} . $$

Sub-Case 2.2:

$$ q^{1} = q^{2} = q = \frac{\beta }{\alpha + \beta }\left( \frac{W}{U} \right)^{k} \mathop \sum \limits_{j = 1}^{n - 1} w_{j}^{{\frac{k}{k + 1}}} \;\;\;{\text{and}}\;\;\;Z = \left( {\alpha + \gamma } \right)q = \beta \frac{\alpha + \gamma }{{\alpha + \beta }}\left( \frac{W}{U} \right)^{k} \mathop \sum {_{j = 1}^{n - 1} }w_{j}^{{\frac{k}{k + 1}}} . $$

Sub-Case 2.3:

$$ q^{1} = q^{2} = q = \left( \frac{W}{U} \right)^{k} \mathop \sum \limits_{j = 1}^{n - 1} w_{j}^{{\frac{k}{k + 1}}} \;\;\;{\text{and}}\;\;\;Z = \left( {\alpha + \gamma } \right)q = \left( {\alpha + \gamma } \right)\left( \frac{W}{U} \right)^{k} \mathop \sum \limits_{j = 1}^{n - 1} w_{j}^{{\frac{k}{k + 1}}} . $$

Property 5.3

The optimal cost function is given by \(Z=\mathit{min}\left\{\delta ,\beta ,\beta \frac{\alpha +\gamma }{\alpha +\beta },\alpha +\gamma \right\}{\left(\frac{W}{U}\right)}^{k}{\sum }_{j=1}^{n-1}{w}_{j}^{\frac{k}{k+1}}\).

Solution procedure to problem \({\varvec{P}}{\mathbf{3}}\)

Step 1 Find the job with the largest workload and assign it to the last position.

Step 2 Use Property 3.2 to calculate the amount of resource allocated to jobs \(1,\dots ,n-1\).

Step 3 Use Property 3.3 to calculate the actual processing times to jobs \(1,\dots ,n-1\).

Step 4 Use Properties 5.2 and 5.3 to determine the relevant case and to calculate the optimal values of the flow-allowance constants and cost.

Theorem 5.1

The computational complexity of the proposed solution is \(O(n)\) time.

The proof is identical to that given in Sect. 3 for Theorem 3.1 and is thus omitted.

Numerical example 5.1

Consider the following data:

The number of jobs is \(n=8\), the total resource limitation is \(U=13\) and \(k=0.75\).

The workloads are \(\left(33, 22, 44, 6, 49, 41, 33, 2\right)\).

We solve the given input with four different sets of cost parameters to reflect Case 1 and Subcases 2.1–2.3 (see Property 5.1).


Solution:

The optimal amount of resource allocated to each job, the actual processing time of each job, and the optimal flow-allowance values, due-dates and cost are provided in Table 2.

Table 2 Numerical example 5.1—resource allocation, actual processing times, and the optimal flow-allowance values, due-dates and cost
Full size table

6 P4: \(1\left|SLK\, DW,conv, {w}_{jr}, \sum {u}_{j}\le U\right|Z\)

To present a solution for Problem \({\varvec{P}}{\mathbf{4}}\), we combine the results achieved in Sects. 4 and 5. The input for the problem contains four unit costs, a matrix of \(n\times n\) job-position workloads, and an upper bound on the total resource.

From Property 5.1, the coefficient in the cost function is \(\rho =\left\{\begin{array}{ll}\delta , & Case1\\ \beta , & Subcase\,2.1\\ \frac{\beta \left(\alpha +\gamma \right)}{\alpha +\beta },& Subcase\,2.2\\ \alpha +\gamma ,& Subcase\,2.3\end{array}\right.\)

Similar to the due-date setting, \(\rho \) is a job- and position-independent constant and the cost function can be further simplified,

$$Z=\rho \sum_{j=1}^{n}\sum_{r=1}^{n-1}{\left(\frac{{w}_{jr}}{{u}_{j}}\right)}^{k}{X}_{jr}.$$

Thus, to solve Problem \({\varvec{P}}{\mathbf{4}}\), we can utilize AP4.1, presented in Sect. 4 for solving Problem \({\varvec{P}}{\mathbf{2}}\), and the formal solution procedure is as follows.

Solution procedure to problem \({\varvec{P}}{\mathbf{4}}\)

Step 1 Apply AP4.1, to obtain the optimal sequence of the jobs assigned to positions \(1, \dots ,n-1\).

Step 2 Schedule the unassigned job to position \(n\).

Step 3 Use Property 3.2 to calculate the amount of resource allocated to jobs \(1,\dots ,n-1\).

Step 4 Use Property 3.3 to calculate the actual processing times to jobs \(1,\dots ,n-1\).

Step 5 Use Properties 5.2 and 5.3 to determine the relevant case and to calculate the optimal values of the flow-allowance constants and cost.

Theorem 6.1

The proposed solution solves \({\varvec{P}}{\mathbf{4}}\) in \(O({n}^{3})\) time.

The proof is exactly like the one given in Sect. 4 for Theorem 4.1.

Numerical example 6.1

We solve the \(8\times 8\) job-position processing times problem given in Table 3, where \(U=16\) and \(k=0.6\). As in Numerical example 4.1, we solve this input with four different sets of cost parameters.

Table 3 Example 6.1—job-position workloads
Full size table

Solution:

The optimal amount of resource allocated to each job, the actual processing time of each job, and the optimal flow-allowance values, due-dates and cost are provided in Table 4.

Table 4 Numerical example 6.1—resource allocation, actual processing times, and the optimal flow-allowance values, due-dates and cost
Full size table

7 Conclusion

We studied minmax due-dates based on common flow-allowance assignment and scheduling problems on a single machine. We extended the basic model by considering controllable processing times and focused on a model where the job processing time is a convex function of the amount of resource allocated to it. The results of the due-date method were then generalized to that of common due-window. In both settings, the problems with position-independent workloads were shown to be solved in \(O(n)\), whereas the problems with position-dependent workloads were solved in \(O\left({n}^{3}\right).\)

Given the similarities between the single machine and the proportionate flow-shop environments, interesting subjects for future research are the extensions of the addressed problems to the setting of proportionate flow-shop. Another challenging extension is to the setting of parallel machines. However, since even minimizing the makespan with constant processing times is ordinary NP-hard, a different approach must be applied.