1 Introduction, theoretical framework, and literature review

Although, minimizing the weighted sum of earliness/tardiness (E/T) costs or minimizing the weighted sum of completion times in parallel machine scheduling problems have been investigated since the 1970s, the problem that tries to minimize both of the sums of E/T durations and the sum of completion times simultaneously addressed in this paper has not got so much attention from the literature. According to the reported literature, Biskup and Cheng [1] only investigated the problem and they showed the problem is NP-hard and presented a polynomially solvable special case in which the processing times of all jobs are equal. Also, they proposed a heuristic that tries to assign jobs more evenly to have equal workloads for machines as much as possible. The main observation of Biskup and Cheng [1] in their study was that “in an optimal schedule, the numbers of jobs on the machines differ by as few as possible”. Up to the nature of the problem, if jobs are distributed machines more evenly, the completion times of jobs may decrease and other costs such as earliness and tardiness may be evenly shared among all jobs. There are similar solution approaches that try to share jobs evenly to machines. Arık and Toksarı [2] proposed a serpentine algorithm to distribute jobs evenly to machines in parallel where the objectives are to minimize the total tardiness penalty cost, to minimize the earliness penalty cost, and to minimize the cost of setting due dates. The objective of the proposed problem is interesting since it includes three different costs (the cost of completion time, the cost of earliness, and the cost of tardiness). Biskup and Cheng [1] gave an example of an application of the problem for readers.

The contemporary industrial landscape necessitates meticulous optimization of operational processes, especially in complex environments like parallel machine scheduling. Amidst evolving market dynamics, companies face multifaceted challenges requiring a delicate balance between minimizing completion times, earliness, and tardiness penalties while optimizing resource utilization. The overarching goal of this study is to delve into an unexplored realm of parallel machine scheduling, specifically focusing on the minimization of completion times, earliness, and tardiness costs simultaneously—an area significantly underrepresented in current literature. Existing research has extensively explored variants of parallel machine scheduling, primarily concentrating on either minimizing weighted sums of earliness/tardiness costs or completion times in isolation. However, the critical interplay between these factors has received scant attention. The dearth of studies addressing the simultaneous optimization of completion times alongside earliness and tardiness costs in parallel machine environments forms the core gap that this research aims to fill. This study presents a compelling contribution by not only identifying this critical research gap but also by introducing optimal policies tailored to the unique complexities of this unexplored problem domain. By outlining strategies to increase early jobs, implement effective tardy job sequencing, and distribute tardy jobs efficiently across machines, this research lays the groundwork for an efficient heuristic algorithm—a key contribution to the field. Moreover, the comparative analysis against existing algorithms reveals the superior performance of the proposed heuristic. This underlines the practical relevance and applicability of the identified optimal policies, showcasing their efficacy in real-world scenarios. In addition to immediate applications in parallel machine environments, the implications of this study extend to diverse industries where timely delivery and efficient resource utilization are paramount. This research paves the way for strategic decision-making, aiding managers in devising scheduling strategies that optimize operations, minimize costs, and enhance overall operational efficiency. The limitations of existing studies and the unexplored potential for further enhancements, such as integrating additional constraints like release dates and sequence-dependent setup times, present promising avenues for future research. By extending the scope of the investigated problem and refining the identified optimal policies, future studies can further enrich the field of parallel machine scheduling. This study shows some properties of the problem and optimal policies for finding an optimal schedule for the problem where the objective is to minimize the completion times and earliness/tardiness durations.

For a close literature review of the investigated problem, there are similar papers considering both E/T durations and the sum of completion times. Su [3] addressed the identical parallel machine scheduling problem in which the total earliness and tardiness about a common due date are minimized subject to minimum total flowtime. He showed how to transform the problem into a simplified version of the parallel machine problem to minimize makespan subject to minimum total flowtime. Sivrikaya and Ulusoy [4] proposed a genetic algorithm for parallel machine E/T scheduling with sequence-dependent setup times and distinct due dates. Weng et al. [5] proposed several heuristics for unrelated parallel machine E/T scheduling problems with setup consideration and a total weighted completion time objective. Bilge et al. [6] considered uniform parallel machine tardiness scheduling with non-identical due dates, arrival times, and sequence-dependent setups. Liaw et al. [7] considered unrelated parallel machine weighted tardiness scheduling problems. They developed efficient lower and upper bounds for the problem. Radhakrishnan and Ventura [8] proposed simulated annealing for parallel machine scheduling with E/T penalties and sequence-dependent set-up times. Cheng et al. [9] proposed genetic algorithms for minimax E/T scheduling in identical parallel machines. Balakrishnan et al. [10] presented a mixed-integer formulation for E/T scheduling with sequence-dependent setups on uniform parallel machines. Cheng and Chen [11] considered an identical parallel machine E/T scheduling problem where the common due date is a decision variable. They also showed that the special case in which all jobs have an equal processing time for the problem is polynomially solvable. Toksarı and Güner [12] introduced mixed nonlinear integer programming formulation for parallel machine E/T scheduling with simultaneous effects of learning and linear deterioration, sequence-dependent setups, and a common due date for all jobs. Biskup et al. [13] proposed a heuristic approach for identical parallel machines to minimize total tardiness. Shim and Kim [14] developed dominance properties and lower bounds for parallel identical machine problems where the objective is to minimize total tardiness. Furthermore, they developed a branch and bound algorithm using their properties. Bank and Werner [15] proposed heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties. Yin et al. [16] considered a two-agent unrelated parallel machine scheduling problem where the overall objective is to minimize the total completion time of the jobs of one agent while keeping the weighted number of tardy jobs of another agent within a given limit. They introduced a novel column generation scheme for the problem. Arık [17] compared three different metaheuristic algorithms to determine what kind (swarm intelligence-based, evolutionary or single solution) of metaheuristics is effective in solving unrelated parallel machine E/T scheduling problems. Computational results in Arık’s study showed that the artificial bee algorithm outperforms its opponents in view of solution quality as a swarm intelligence-based metaheuristic algorithm. Arık et al. [18] investigated an unrelated parallel machine weighted earliness/tardiness scheduling problem with the common due date. They proposed four solution construction algorithms using the V-shaped property of the problem and two well-known dispatching rules. Then they proposed five solution improvement heuristics including different local search mechanisms. They compared their algorithms with Arık’s [17] proposed algorithms and other algorithms in the literature. The experimental study reveals that their solution improvement algorithm with swap and reinsertion-based local search mechanisms outperforms other algorithms in the literature.

Arık [19] considered the common due date assignment for single machine weighted earliness/tardiness scheduling problem with distinct weights to minimize the cost of weighted earliness/tardiness and due date assignment cost. He analyzed optimal properties like V-shaped property of similar problems and applied some of them to generate an efficient heuristic algorithm to solve the problem. Kordmostafapour et al. [20] investigated metaheuristic algorithms for unrelated parallel machine batch scheduling problems in case of that the processing time of jobs is controllable on resource allocation. They proposed also new mathematical model for their problem. Chen et al. [21] presented a polynomial algorithm to solve single machine scheduling problem with due date assignment under group technology environment. Geng et al. [22] proposed a dynamic programming algorithm to solve proportionate flow shop scheduling problems allowing job rejection where the objective function is to minimize the earliness, tardiness, due date cost, and rejection cost. They also presented analyses of the algorithm complexity. Pan et al. [23] designed efficient and fast polynomial time algorithms to solve the single machine scheduling problem with due date assignments, deteriorating jobs, and past sequence-dependent delivery times by using some optimal policies of the problem. Mosheiov and Sarig [24] studied a common due date assignment problem for two parallel uniform machines where jobs have identical processing times and job-dependent and asymmetric earliness and tardiness costs. They showed the existence of a polynomial algorithm for the problem. Wang [25] proved that there are optimal properties of single machine due date assignment problem with past sequence-dependent setup times. Wang also presented a polynomial time algorithm for the problem. Nasrollahi et al. [26] investigated the common due date problem of constrained two-agent scheduling of jobs in a two-machine flow shop environment to minimize the weighted sum of maximum earliness and maximum tardiness. They presented a branch and bound algorithm based on efficient lower and upper bounds and dominance rules for the problem. Falq et al. [27] single machine weighted earliness/tardiness scheduling with unrestrictive common due date. They investigated neighborhood-based dominance properties. Qian and Han [28] considered a single machine scheduling problem with distinct due dates and jobs under deterioration effect. They proved that there are polynomial time algorithms to solve their problems.

Today’s complex and challenging market conditions make the company consider multiple penalty costs such as completion time, tardiness, and earliness penalties because the company has to satisfy its customers by sending them their goods and services on time and it has to increase its operational efficiency. The common due date for all jobs may indicate that all jobs are going to be delivered at the same time and completing any job before/after the shipment date may bring additional costs like insurance costs for an early completed job and shipment delaying costs for a tardy job. Furthermore, the pressure on the company to use its operational resources such as machines, production lines, and facilities efficiently makes considering completion time penalties compulsory for the company. Thus, a natural problem with earliness, tardiness, and completion time penalties arises for companies that have parallel machine environments for manufacturing. This study investigates this problem with an unrelated parallel machine environment and reveals some optimal policies for its solution. Furthermore, this study proposes a solution construction and improvement heuristic algorithm using optimal policies of the problem.

The remainder of the paper is organized as follows: Sect. 2 introduces the properties of the problem. The optimal policies of the problem with four different theorems are shown in Sect. 2. Using these optimal policies, a solution construction and improvement heuristic is also designed for the problem in Sect. 2. In Sect. 3, some test instances are generated for comparison of our proposed heuristics with two existing heuristics. Section 4 discusses the effect of the components of the proposed heuristic. Section 5 concludes the study and gives a future direction of the problem for the reader.

2 Methodology

2.1 Properties of the problem

This section shows some properties of the problem. Let us assume there are \(n\) jobs that are ready to be processed on \(m\) machines in parallel. Each job \(j\) (\(j\in \{\mathrm{1,2},...,n\}\)) can be processed on machine \(i\) (\(i\in \{\mathrm{1,2},...,m\}\)) with the processing time \({P}_{ij}\). There is a common due date \(d\) for all jobs. If a job is completed before the common due date, then that job is early and it has a cost \({E}_{j}\) as follows:

$${E}_{j}=Max\left(0,d-{C}_{j}\right)$$
(1)

where \({C}_{j}\) is the completion time of the job \(j\). If a job is completed after the common due date, then that job is tardy and it has a cost \({T}_{j}\) as follows:

$${T}_{j}=Max\left(0,{C}_{j}-d\right)$$
(2)

The objective function is to minimize the sum of completion times, earliness, and tardiness durations \(\left(\sum_{j=1}^{n}({C}_{j}+{E}_{j}+{T}_{j})\right)\) with equal weights. Since the machines in parallel have different capacities, velocities, and properties; the processing times of each job are different for machines. Thus the problem is an unrelated parallel machine scheduling problem with the common due date where the objective is to minimize the sum of completion times, earliness, and tardiness durations. If the problem is notated with the triple scheduling notations (\(\mathrm{\alpha }/\upbeta /\upgamma\)), then the problem is \(R|{d}_{j}=d|\sum_{j=1}^{n}({C}_{j}+{E}_{j}+{T}_{j})\).

Lemma 1

Each early job’s effect on the objective function is equal to \(d\).

Let \(j\) be a job and its completion time \({C}_{j}\) is less than \(d\). Therefore job \(j\) is an early job. The effect (\({f}_{j}^{E}\)) of job \(j\) on the objective function of the problem of \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\) is follows:

$${f}_{j}^{E}={C}_{j}+{E}_{j}+{T}_{j}$$
(3)
$${f}_{j}^{E}={C}_{j}+{\text{max}}\left(0, d-{C}_{j}\right)+{\text{max}}\left(0, {C}_{j}-d\right)$$
(4)
$${f}_{j}^{E}={C}_{j}+d-{C}_{j}$$
(5)
$${f}_{j}^{E}=d$$
(6)

Lemma 2

Each tardy job’s effect on the objective function is equal to \(2{C}_{j}-d\).

Let \(j\) be a job and its completion time \({C}_{j}\) is more than \(d\). Therefore job \(j\) is a tardy job. The effect (\({f}_{j}^{T}\)) of job \(j\) on the objective function of the problem of \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\) is follows:

$${f}_{j}^{T}={C}_{j}+{E}_{j}+{T}_{j}$$
(7)
$${f}_{j}^{T}={C}_{j}+{\text{max}}\left(0, d-{C}_{j}\right)+{\text{max}}\left(0, {C}_{j}-d\right)$$
(8)
$${f}_{j}^{T}={C}_{j}+{C}_{j}-d$$
(9)
$${f}_{j}^{T}=2{C}_{j}-d$$
(10)

Lemma 3

A tardy job’s effect is more than an early job’s effect on the objective function of the problem of \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\).

Since \({C}_{j}\) is more than \(d\) for a tardy job \(j\), it can be assumed that \({C}_{j}=d+\Delta\) where \(\Delta\) is the sum of processing times that are processed after the common due date and until completion of the job \(j\). The effect of a tardy job on the objective function can be rewritten as follows:

$${f}_{j}^{T}=2{C}_{j}-d$$
(11)
$${f}_{j}^{T}=2\left(d+\Delta \right)-d$$
(12)
$${f}_{j}^{T}=d+2\Delta$$
(13)

Since \(\Delta >0\), \({f}_{j}^{T}\) is greater than \({f}_{j}^{E}\).

Lemma 4

Zero start times of machines decrease the total cost of the given schedule more than the non-zero start times of machines.

The proof of Lemma 4 is trivial because non-zero start times increase (decrease) completion times of jobs (the number of early jobs) so the zero start time of a machine for the problem is a property of the optimal schedule.

2.2 Optimal policies for the problem of \({\varvec{R}}|{{\varvec{d}}}_{{\varvec{j}}}={\varvec{d}}|\sum_{{\varvec{j}}}({{\varvec{C}}}_{{\varvec{j}}}+{{\varvec{E}}}_{{\varvec{j}}}+{{\varvec{T}}}_{{\varvec{j}}})\)

This section shows optimal policies for the problem of \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\). Three theorems are used to demonstrate the policies for the optimal schedule.

Theorem 1

For the problem of \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\), if \(d\) is unrestricted (\(d>\sum_{j}{P}_{ij} \forall i\)), the optimal schedule is the schedule where all jobs are early. Thus the objective function of the optimum schedule is equal to \((n-m)d\) where \(n\) is the number of jobs and \(m\) is the number of machines.

Proof

Since all \({C}_{j}\) values are less than \(d\), when \(d\) is unrestrictive so there is no tardy job and there are \(m\) jobs completed on the common due date. Thus, the optimum objective function value is equal to \(\sum_{j}{f}_{j}^{E}=(n-m)d\). This completes the proof of Theorem 1.

Theorem 2

For the problem of\(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\), if \(d\) is restrictive (\(d<\frac{\sum_{j}{P}_{ij}}{h} for any machine i\)) where \(h\) is the restrictive factor), the optimal schedule is the schedule where all tardy jobs on the same machine are ordered in increasing order of their processing time.

Proof

Let us have two tardy neighboring jobs (\(j,k\)) and these jobs are to be processed on machine \(i\) among all machines in parallel. There are two alternative schedules. These are \(\pi\) and \({\pi }^{\prime}\), respectively. In schedule \(\pi\), job \(j\) precedes job \(k\) in machine \(i\). \({C}_{j}^{\pi },{C}_{k}^{\pi },{C}_{j}^{{\pi }^{\prime}}\) and \({C}_{k}^{{\pi }^{\prime}}\) are completion times of jobs (\(j,k\)) in schedules (\(\pi\), \({\pi }^{\prime}\)) and these are greater than \(d\). These tardy jobs’ costs for \(\pi\) and \({\pi }^{\prime}\) are \({f}^{\pi }\) and \({f}^{{\pi }^{\prime}}\), respectively. Our assumption is \({P}_{ik}>{P}_{ij}\) and let \({M}_{i}\) is the time that machine \(i\) can start processing jobs (\(j, k\)).

For schedule \(\pi\),

$${C}_{j}^{\pi }={M}_{i}+{P}_{ij}$$
(14)
$${C}_{k}^{\pi }={C}_{j}^{\pi }+{P}_{ik}$$
(15)
$${C}_{k}^{\pi }={M}_{i}+{P}_{ij}+{P}_{ik}$$
(16)
$${f}^{\pi }={C}_{j}^{\pi }+{C}_{k}^{\pi }+\left({C}_{j}^{\pi }-d\right)+\left({C}_{k}^{\pi }-d\right)$$
(17)
$${f}^{\pi }={M}_{i}+{P}_{ij}+{M}_{i}+{P}_{ij}+{P}_{ik}+{M}_{i}+{P}_{ij}-d+{M}_{i}+{P}_{ij}+{P}_{ik}-d$$
(18)
$${f}^{\pi }=3{M}_{i}+{4P}_{ij}+{2P}_{ik}-2d$$
(19)

For schedule \({\pi }^{\prime}\),

$${C}_{k}^{{\pi }^{\prime}}={M}_{i}+{P}_{ik}$$
(20)
$${C}_{j}^{{\pi }^{\prime}}={C}_{k}^{{\pi }^{\prime}}+{P}_{ij}$$
(21)
$${C}_{j}^{{\pi }^{\prime}}={M}_{i}+{P}_{ik}+{P}_{ij}$$
(22)
$${f}^{{\pi }^{{{\prime}}}}={C}_{k}^{{\pi }^{{{\prime}}}}+{C}_{j}^{{\pi }^{{{\prime}}}}+\left({C}_{k}^{{\pi }^{{{\prime}}}}-d\right)+\left({C}_{j}^{{\pi }^{{{\prime}}}}-d\right)$$
(23)
$${f}^{{\pi }^{\prime}}={M}_{i}+{P}_{ik}+{M}_{i}+{P}_{ik}+{P}_{ij}+{M}_{i}+{P}_{ik}-d+{M}_{i}+{P}_{ik}+{P}_{ij}-d$$
(24)
$${f}^{{\pi }^{{{\prime}}}}=3{M}_{i}+{4P}_{ik}+{2P}_{ij}-2d$$
(25)

If the shortest processing time dispatching rule assures optimum for tardy jobs then \({f}^{{\pi }^{\prime}}-{f}^{\pi }\) must be greater than zero.

$${f}^{{\pi }^{\prime}}-{f}^{\pi }=3{M}_{i}+{4P}_{ik}+{2P}_{ij}-2d-3{M}_{i}-{4P}_{ij}-{2P}_{ik}+2d$$
(26)
$${f}^{{\pi }^{{{\prime}}}}-{f}^{\pi }={2P}_{ik}-{2P}_{ij}$$
(27)

Since \({P}_{ik}>{P}_{ij}\), \({2P}_{ik}-{2P}_{ij}\) is greater than zero. This completes the proof for Theorem 2.

Theorem 3

If the number of early jobs increases for the problem of \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\), the objective function value of the schedule decreases.

Proof

Let us have \(n\) jobs. The schedule \(\pi\) includes \(x\) early jobs and \(y\) tardy jobs. It is known that \(x+y=n\). The schedule \({\pi }^{\prime}\) includes \(x+1\) early jobs and \(y-1\) tardy jobs. The objective functions of these schedules are \({f}^{\pi }\) and \({f}^{{\pi }^{\prime}}\), respectively. If Theorem 3 holds, then \({f}^{\pi }-{f}^{{\pi }^{\prime}}>0.\)

For schedule \(\pi\),

$${f}^{\pi }=xd+\sum_{l=1}^{y}\left(d+{\Delta }_{l}^{\pi }\right)$$
(28)

For schedule \({\pi }^{\prime}\),

$${f}^{{\pi }^{\prime}}=\left(x+1\right)d+\sum_{l=1}^{y-1}\left(d+{\Delta }_{l}^{{\pi }^{\prime}}\right)$$
(29)

\({\Delta }_{l}^{\pi }\) is the duration between the common due date and completion time of a tardy job \(l\) in schedule \(\pi\). Let us have three tardy jobs in a machine. These jobs are \(k\),\(t,\) and \(l\). The job \(k\) is the first tardy job in machine \(i\). The job \(t\) is the second tardy job in machine \(i\). The job \(l\) is the last tardy job in machine \(i\). Thus \({\Delta }_{k}^{\pi }=d+{P}_{ik}\), \({\Delta }_{t}^{\pi }=d+{P}_{ik}+{P}_{it}\) and \({\Delta }_{l}^{\pi }=d+{P}_{ik}+{P}_{it}+{P}_{il}\). Any of these tardy jobs is selected to make it an early job by arranging the schedule so a new schedule \({\pi }^{\prime}\) is obtained. As seen, there is an extra early job in the schedule \({\pi }^{\prime}\) than the schedule \(\pi\) has.

$${f}^{\pi }-{f}^{{\pi }^{\prime}}=xd+\sum_{l=1}^{y}\left(d+{\Delta }_{l}^{\pi }\right)-\left(x+1\right)d-\sum_{l=1}^{y-1}\left(d+{\Delta }_{l}^{{\pi }^{\prime}}\right)$$
(30)
$${f}^{\pi }-{f}^{{\pi }^{{{\prime}}}}=xd+yd+\sum_{l=1}^{y}{\Delta }_{l}^{\pi }-\left(x+1\right)d-\left(y-1\right)d-\sum_{l=1}^{y-1}{\Delta }_{l}^{{\pi }^{{{\prime}}}}$$
(31)
$${f}^{\pi }-{f}^{{\pi }^{\prime}}=\sum_{l=1}^{y}{\Delta }_{l}^{\pi }-\sum_{l=1}^{y-1}{\Delta }_{l}^{{\pi }^{\prime}}$$
(32)

Since \(\sum_{l=1}^{y}{\Delta }_{l}^{\pi }\) includes an extra tardy job than \(\sum_{l=1}^{y-1}{\Delta }_{l}^{{\pi }^{\prime}}\), the expression of \(\sum_{l=1}^{y}{\Delta }_{l}^{\pi }-\sum_{l=1}^{y-1}{\Delta }_{l}^{{\pi }^{\prime}}\) is greater than zero. Thus, Theorem 3 is proved.

Theorem 4

For \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\), if tardy jobs are distributed on machines considering equal tardy workloads on machines as much as possible, and then the objective function of the problem decreases.

Proof

Biskup and Cheng [1] indicate the importance of disturbing jobs evenly to the identical machines or making workloads of the identical machines as equal as possible. Since each job has different processing times for machines in case of unrelated parallel machine problems, it should be considered the workloads of machines instead of the number of jobs on machines. It is also known that any early job’s effect on the objective function is the same and it is independent of its position, machine, and processing time, so the number of early jobs must be increased to decrease tardiness cost. Thus our first case for proving Theorem 4 investigates the earliness of the schedule instead of tardiness. Since each job’s processing time is dependent on machines, it should be considered the machine workload for tardy jobs by assigning each tardy job to the machine with minimum cost or tardiness. Minimizing overall tardiness and distributing the tardy workload to machines serve the same goal which is to minimize the objective function. Our second case investigates the effects of having equal tardy workloads on machines as much as possible.

Case 1

Let us assume that there are \(n\) jobs and two unrelated machines in parallel. The indexes for machines are \(k\) and \(l\). The sum of processing times for the machine \(k\) is \(Wk\) and the sum of processing times for the machine \(l\) is \(Wl\). The starting times of machines to process jobs are \(MK\) and \(ML\) where \(MK\ge 0\) and \(ML\ge 0\). The common due date (\(d\)) is a restrictive due date such as \(d < Wk/2\) or \(d < Wl/2\).

If all jobs are assigned to the machine \(k\), the workload of the machine \(k\) and the completion time of the last job in machine \(k\) will be \(Wk\) and \(Wk+MK\), respectively. Since all jobs are assigned to machine \(k\), the workload of the machine \(l\) will be zero. If all jobs are assigned to machine \(l\), the machine workload of machine \(l\) and the completion time of the last job in machine \(l\) will be \(Wl\) and \(ML + Wl\), respectively. Thus the machine workload of the machine \(k\) will be zero. In both cases, some of the jobs will be early jobs and some of the jobs will be tardy jobs.

Let us have two different schedules named \({\pi }^{1}\), and \({\pi }^{2}\), respectively. Schedule \({\pi }^{1}\) is the schedule where all jobs are assigned to machine \(k\). Schedule \({\pi }^{2}\) is the schedule where \(n-1\) jobs are assigned to machine \(k\) and machine \(l\) has only one job. In schedule \({\pi }^{1}\), there are \(x\) early (and an on-due date job at most) and \(y\) tardy jobs (\(x+y=n\)).The processing time of the job on position \(j\) (\(j\in \{\mathrm{1,2},..,n\}\)) in machine \(i\) (\(i\in \{k,l\}\)) is \({P}_{ij}\). The total cost functions of schedules are \({f}^{\pi 1}\), and \({f}^{\pi 2}\) respectively. If the theorem holds, then \({f}^{\pi 1}>{f}^{\pi 2}\).

$$Wl=\sum_{j=1}^{j=n}{P}_{jl}$$
(33)
$$Wk=\sum_{j=1}^{j=n}{P}_{jk}$$
(34)
$${f}^{\pi 1}=\sum_{j=1}^{j=n}{C}_{jk}+\sum_{j=1}^{j=n}{E}_{jk}+\sum_{j=1}^{j=n}{T}_{jk}$$
(35)

This expression can be simplified by using Lemma 1 and Lemma 2 as follows:

$${f}^{\pi 1}=xd+\sum_{jt=1}^{jt=y}2{C}_{jt,k}-d$$
(36)

where \(jt\) is the index for current tardy jobs in machine \(k\) and \({C}_{jt,k}\) is the completion time of a tardy job \(jt\) in machine \(k\). If the last job from the machine \(k\) in the schedule \({\pi }^{1}\) is moved to machine \(l\) and the start time of that job is to be completed on the common due date, then the new schedule’s (\({\pi }^{2}\)) total cost function will be as follows:

$${f}^{\pi 2}=\left(x+1\right)d+\sum_{jt=1}^{jt=y-1}2{C}_{jt,k}-d$$
(37)

The last job (possibly a tardy job) from machine \(k\) is removed to machine \(l\) by making it an on-date (completed on the common due date) job. This decreases the objective function value of \({\pi }^{1}\) schedule if the processing time of the removed job lets itself be completed on the common due date. Thus, \({f}^{\pi 1}>{ f}^{\pi 2}\) and \({f}^{\pi 1}-{ f}^{\pi 2}>0.\)

$${{ f}^{\pi 1}-f}^{\pi 2}=xd+\sum_{jt=1}^{jt=y}{2C}_{jt,k}-d- \left(x+1\right)d-\sum_{jt=1}^{jt=y-1}{2C}_{jt,k}+d$$
(38)
$${{ f}^{\pi 1}-f}^{\pi 2}=\sum_{jt=1}^{jt=y}{2C}_{jt,k}- \sum_{jt=1}^{jt=y-1}{2C}_{jt,k}$$
(39)
$${{ f}^{\pi 1}-f}^{\pi 2}={2C}_{y,k}$$
(40)

where \({C}_{y,k}\) is the completion time of the removed tardy job from position \(y\) of machine \(k\) and it is known that it is greater than zero. If it is continued to remove tardy jobs and insert them into available machines’ time slots between zero and the common due date, the objective function goes on being decreased too. Thus, Theorem 4 for Case 1 is proved.

Case 2

The workload of tardy jobs must be eliminated by increasing the number of early jobs. If it is not possible then the workloads of tardy jobs on machines should be balanced by distributing tardy jobs to have balanced tardy workloads for all machines without increasing total tardiness. The second case with similar assumptions is proposed. Let us assume that there are \(n\) jobs and two unrelated machines in parallel. The indexes for machines are \(k\) and \(l\). Let us have two different schedules named \({\pi }^{1}\), and \({\pi }^{2}\), respectively. Schedule \({\pi }^{1}\) is the schedule where numbers of early jobs on machines \(l\) and \(k\) are \(x\) and \(y\), respectively. In schedule \({\pi }^{1}\), there are \(z\) tardy jobs (\(x+y+z=n\)) and these are assigned to machine \(k\). As an assumption, none of these tardy jobs can be an early job in any machine by removing them from their current positions because there is no proper position of machines in the time interval between 0 and \(d\) without turning an early job into a tardy job. Schedule \({\pi }^{2}\) is the schedule where the last tardy job in machine \(k\) is removed from its current position to the end of the sequence of machine \(l\). After removing that job, there is a tardy job in machine \(l\) and there are \(z-1\) tardy jobs. If the completion time of the recently assigned tardy job is less than the completion time on its previous position, then the tardy workload of machine \(k\) decreases while the differences among tardy workloads of machines decrease. If the decrease in the differences among tardy workloads of machines makes the schedule better then \({f}^{\pi 1}>{f}^{\pi 2}\).

$${f}^{\pi 1,l}=xd$$
(41)
$${f}^{\pi 1,k}=yd+\sum_{jt=1}^{jt=z}2{C}_{jt,k}-d$$
(42)
$${f}^{\pi 1}=\left(x+y-z\right)d+2\sum_{jt=1}^{jt=z}{C}_{jt,k}$$
(43)

where \({f}^{\pi 1,l}\) and \({f}^{\pi 1,k}\) are cost effects of machines \(k\) and \(l\) on the objective function value \({f}^{\pi 1}\) of schedule \(\pi 1\).

$${f}^{\pi 2,l}=xd+2{C}_{1,l}-d$$
(44)
$${f}^{\pi 2,k}=yd+\sum_{jt=1}^{jt=z-1}2{C}_{jt,k}-d$$
(45)
$${f}^{\pi 2}=\left(x+y-z\right)d+2{C}_{1,l}+ 2\sum_{jt=1}^{jt=z-1}{C}_{jt,k}$$
(46)

where \({f}^{\pi 2,l}\) and \({f}^{\pi 2,k}\) are cost effects of machines \(k\) and \(l\) on the objective function value \({f}^{\pi 2}\) of schedule \(\pi 2\).

$${{ f}^{\pi 1}-f}^{\pi 2}=\left[\left(x+y-z\right)d+2\sum_{jt=1}^{jt=z}{C}_{jt,k}\right]-\left[\left(x+y-z\right)d+2{C}_{1,l}+ 2\sum_{jt=1}^{jt=z-1}{C}_{jt,k}\right]$$
(47)
$${{ f}^{\pi 1}-f}^{\pi 2}=2\left({C}_{z,k}-{C}_{1,l}\right)$$
(48)

If the completion time \({C}_{1,l}\) of the recently assigned tardy job is less than the completion time \({C}_{z,k}\) on its previous position, then the tardy workload of machine \(k\) decreases while the differences among tardy workloads of machines decrease thus \({{ f}^{\pi 1}-f}^{\pi 2}>0\). Thus Theorem 4 holds for Case 2 of its proof and it is the end of the proof for Theorem 4. If we find and remove tardy jobs from their current positions to make them tardy jobs again with fewer completion times and fewer differences among tardy workloads of machines, the objective function value of the schedule is decreased.

2.3 Solution construction algorithm

Some optimal policies for \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\) are discovered. These are as follows:

  • Increasing the number of early jobs while decreasing the number of tardy jobs,

  • Sequencing tardy jobs in increasing order of their processing times in machines,

  • Distributing tardy jobs on machines with equal tardy workloads without increasing the cost.

By using our main observations, a heuristic method for \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\) is proposed. Since it is needed to increase the number of early jobs per machine, an iterative solution construction algorithm is proposed to assign a job to a machine at each iteration. There are three phases of our proposed algorithm. In the first phase, our construction algorithm selects the job-machine pair that gives the smallest completion time for \(R|{d}_{j}=d|\sum_{j}({C}_{j}+{E}_{j}+{T}_{j})\)\(d\), then it assigns that job to the machine with the smallest completion time. This goes on until there is no unassigned job left. Since our optimal policies are to increase (decrease) the number of early (tardy) jobs and to distribute tardy jobs on machines with equal workloads, it is considered that the machine start times are 0 to assign more early jobs in the time interval between 0 and. Thus completion times of jobs are determined with zero start times of machines. Some of these assigned jobs will be early and tardy according to their completion times. After assigning these jobs, early and tardy jobs of each machine are already sequenced with the SPT dispatching rule. Calculating completion times of jobs and the cost of the schedule are in the second phase of the algorithm. Since Biskup and Cheng [1] proved that there is no idle time between two consecutive jobs in the optimal schedule, the completion times of jobs according to this property of the problem’s optimum schedule are calculated. In the third phase of the algorithm, the workloads of tardy jobs by swapping and moving them among machines are balanced. After all swapping and moving operations are completed for selected jobs, tardy jobs of each machine are reordered in order of their increasing processing times according to the SPT dispatching rule. The pseudo-code of our proposed construction algorithm having \(O(nm)\) complexity is given in Algorithm 1. Also the flowchart of the algorithm is given in Fig. 1.

Fig. 1
figure 1

The flowchart of the algorithm

Full size image

The flowchart of the algorithm in Fig. 1 shows phases of the algorithm. Details of these phases can be found in Algorithm 1.

Algorithm 1
figure a

The proposed heuristic for \(R\left| {d_{j} = d} \right|\sum\nolimits_{j} {\left( {C_{j} + E_{j} + T_{j} } \right)}\)

Full size image

3 Results

For comparison of our proposed heuristic, this section generates some test problems where there are 16 test groups and each group has 10 problems. The numbers of jobs (machines) for test instances are 50, 70, 100, and 150 (2, 4, 7, and 10). The processing times of jobs for unrelated parallel machines are generated randomly by using a uniform distribution like \({P}_{ij}=U\left[\mathrm{1,10}\right] \forall i, j\). For common due date, the formula of Bank and Werner [15] is used as follows:

$$d = \frac{1}{h}\frac{n}{m}\overline{P}$$
(49)

where

$$\overline{P }=\frac{\sum_{i=1}^{n}\sum_{j=1}^{m}{P}_{ij}}{nm}$$
(50)

and \(h\) is the restrictive factor for the problem and Bank and Werner [15] used \(h=3\) in their experiments. Three different restrictive factors (\(h\in \{\mathrm{3,4},5\}\)) are used for our experiments. To compare the performance of our proposed heuristic, two existing heuristic algorithms are used. These are proposed by Biskup and Cheng [1] and Arık and Toksarı [2] for identical parallel machine problems. Biskup and Cheng [1] investigated our problem in an identical parallel machine environment and they proposed a heuristic by using their main observation as “in an optimal schedule, the numbers of jobs on the machines differ by as few as possible”. For an identical parallel machine environment, Arık and Toksarı [2] proposed a serpentine algorithm to distribute jobs evenly to machines in parallel where the objectives are to minimize total tardiness penalty cost, to minimize earliness penalty cost, and to minimize the cost of setting due dates. Up to the nature of the problem in an identical parallel machine environment, if jobs are distributed machines more evenly, the completion times of jobs may decrease and other costs such as earliness and tardiness may be evenly shared among all jobs. Since the proposed problem is in an unrelated parallel machine environment, minimizing differences among workloads of machines instead of minimizing differences among numbers of jobs in machines. Our proposed algorithm is to distribute jobs on machines to have balanced workloads among machines as much as possible considering cost factors. Both algorithms of Biskup and Cheng [1] and Arık and Toksarı [2] are based on list-scheduling that generates a permutation list (SPT or LPT) of jobs and assigns these jobs one by one to positions of machines by following a certain assignment path. Since our problem is in an unrelated parallel machine environment, permutation lists of compared algorithms are modified.

Arık and Toksarı’s [2] serpentine algorithm is designed for identical parallel machine problems and it used an SPT list of jobs considering their processing times to assign them to machines since the processing time of a job is dependent on machines, their algorithm is modified. In each job-machine assignment in the modified serpentine algorithm’s assignment path, the algorithm assigns the job with the smallest processing time to the position of the machine. Biskup and Cheng [1] also used an LPT list of jobs to assign them to identical machines. The permutation list proposed by Adamopoulos and Pappis [29] is used within the algorithm of Biskup and Cheng [1]. Adamopoulos and Pappis’s [29] permutation list of jobs for unrelated parallel machines is a non-increasing order of jobs’ two smallest processing times’ differences. Only that list in the algorithm of Biskup and Cheng [1] is integrated.

Three algorithms are coded in C++ programming language with a standard desktop having an Intel i5-10210U CPU and 8 GB RAM. All test instances are solved with our proposed heuristic and both algorithms of Biskup and Cheng [1] and Arık and Toksarı [2]. Lower bounds of test instances are calculated with a simple formula that is \((n-m)d\). It is known that each early job’s cost is \(d\) and less than any tardy job’s cost. If we have a theoretical schedule in where each machine has one job that is completed on the common due date and has no tardy job, then there are \(n-m\) early jobs. Thus, the lower bound of the problem is equal to \((n-m)d\). Furthermore, we use the average percentage derivations of proposed algorithms from the lower bound of the problem to compare their solution quality. The formula for this derivation is calculated as \((f-LB)/LB\) where \(LB\) is the lower bound of the instance and \(f\) is the objective function value obtained from any proposed algorithm. Table 1 shows the overall average percentage deviation of proposed algorithms for all test instances and restrictive factors. As seen from Table 1, the proposed heuristic outperforms other compared algorithms considering its solution quality. In Table 1, the best value for each restrictive factor is marked with bold font.

Table 1 Overall average percentage derivations of compared algorithms
Full size table

While the restrictive factor is increasing for the same test instances, the common due date increases, and the solution qualities of proposed algorithms decrease because the objective function of the problem is highly dependent on the common due date. The revealed optimal policies of the problem are integrated within our proposed heuristic and these optimal policies increase the solution quality of the proposed algorithm and make it outperform the other two existing algorithms considering solution quality. The serpentine algorithm of Arık and Toksarı [2] is better than the algorithm of Biskup and Cheng [1] because it uses an assignment method that selects the job with the smallest processing time for the current position of the machine while the algorithm of Biskup and Cheng [1] uses an LPT permutation list for jobs. Our algorithm assigns jobs considering the workloads of machines by selecting the machine-job pair with the smallest workload. Therefore, we may state that considering balanced workloads among machines decreases the objective function more than considering balanced numbers of jobs for machines.

4 Discussion

This section briefly discusses what the study has done in this study for the investigated problem. The objective of the investigated problem is to minimize the sum of completion times, earliness, and tardiness durations of jobs in an unrelated parallel machine environment with the common due date. The problem of minimizing both the sums of E/T durations and the sum of completion times simultaneously has not so much attention from the literature. The common due date in scheduling problems is classified as restrictive and unrestrictive. For the problem with either restrictive or unrestrictive common due dates, the optimal schedule has some characteristics that can be expressed with optimal policies of the problem. In Sect. 2, we reveal the optimal policies of the problem which are to increase the number of early jobs, to use the shortest processing time dispatching rule for tardy jobs, and to distribute tardy jobs on machines with tardy workloads differ from each other as much as possible. We adapt these findings to our proposed heuristic that constructs a solution by using SPT-based list scheduling and improves the solution by swapping jobs between machines to distribute tardy job durations evenly among machines. After each swap operation, resequencing of tardy jobs in each machine is done by using the SPT dispatching rule to decrease the objective function value of the solution. Our proposed heuristic outperforms the existing solution approaches of Biskup and Cheng [1] and Arık and Toksarı [2] by using our main findings in Sect. 2, these are as follows:

  • Solution construction phase Increasing the number of early jobs while decreasing the number of tardy jobs,

  • Job swapping phase Distributing tardy jobs on machines with equal tardy workloads without increasing the cost.

  • Resequencing phase Sequencing tardy jobs in increasing order of their processing times in machines.

In this section, we analyze our solution approach with and without these components that serve for optimal policies of the problem. The variants of our solution approach are as follows:

  • Var#0: the original solution approach with its full features as designed in Sect. 4,

  • Var#1: it uses a random initial solution instead of the first phase of Algorithm 1, the rest of its components are the same,

  • Var#2: it does not reorder tardy jobs in each machine, the rest of its components are the same,

  • Var#3: it uses a random initial solution instead of the first phase of Algorithm 1 and it does not reorder tardy jobs in each machine.

  • Var#4: it just reorders tardy jobs in each machine for the best solution in the memory at the end, the rest of its components are the same,

The same test problems in the experimental study of this paper are used to determine which components are effective in solution quality by comparing the variants of the proposed solution approach in an equal computation environment. The average relative percentage derivations of solution approach variants are given in Table 2. Table 1 shows the overall average percentage deviation of the variants of the proposed solution approach for all test instances and restrictive factors. As seen from Table 2, Var#0, Var#2 and Var#4 outperform other compared variants in view of solution quality. Var#0 and Var#4 include Resequencing phase and Solution construction phase. Var#2 includes only Solution construction phase and it does not reorder tardy jobs in each machine. The common feature of effective variants of the solution approach is Solution construction phase and the common feature of ineffective variants (Var#1 and Var#3) is the random initial solution generation at the beginning of the algorithm. In Table 2, the best value for each restrictive factor is marked with bold font.

Table 2 Overall average percentage derivations of all variants of the proposed solution approach
Full size table

As seen from Table 2, the most effective component of the solution approach is Solution construction phase that increases/decreases the number of early/tardy jobs before the solution improvement phase of the algorithm. We do an ANOVA test with a 95% confidence level for measuring the effects of variants on the solution quality of the solution approach. The factors and details of the ANOVA test are given in Fig. 2. As seen from our ANOVA test, all factors have a significant difference with a 95% confidence level and all factors’ P-values are less than 0.05 and equal to 0. Thus, we may say that selecting the right variant of the solution approach has an impact on the solution quality of the algorithm.

Fig. 2
figure 2

ANOVA test for measuring the effects of variants on the solution quality

Full size image

It seems that Resequencing phase in the proposed solution approach doesn’t work as expected. Even though we prove that ordering only tardy jobs according to the SPT rule is an optimal policy for the investigated problem in Sect. 3, the experiment in this section does not validate that ordering tardy jobs in increasing order of their processing time assures better solutions. This can be also deduced from Fig. 3 which shows the interval plot of ARPD values of the variants with different components. As the other component of the proposed solution approach, Job swapping phase within a nested loop searches almost all possible sequences per machine and it does the same thing that is intended within Resequencing phase. If the algorithm executes fewer iterations without a nested loop that gives almost all swap alternatives, the impact of Resequencing phase on the solution quality will be seen more obviously.

Fig. 3
figure 3

The interval plot of ARPD values of the variants with different components

Full size image

If the investigated problem was to minimize only earliness/tardiness cost, then the optimal sequence per machine would have a V-shaped property (please see Toksarı and Guner [30]). V-shaped property indicates that the optimal sequence of early (tardy) jobs must be ordered using the weighted longest processing times (weighted shortest processing time) dispatching rule. The general well-known properties of an optimal solution for the single machine weighted earliness/tardiness scheduling problem with a common due date were presented by.

Panwalkar et al. [31]. Recent studies (Arık [19, 32], Arık et al. [18]) use this property to generate efficient algorithms. Since our investigated problem is to minimize the total cost including completion times and earliness/tardiness of jobs, the V-shaped property and strategies dependent on it do not fit well with the investigated problem. Therefore, new policies must be developed for the problem. The discovered policies referred to Sect. 2 are as follows:

  • Increasing the number of early jobs while decreasing the number of tardy jobs,

  • Sequencing tardy jobs in increasing order of their processing times in machines,

  • Distributing tardy jobs on machines with equal tardy workloads without increasing the cost.

Using these strategies, a heuristic algorithm is developed and its efficiency is tested against two other existing algorithms (Biskup and Cheng [1] and Arık and Toksarı [2]) in the previous section. In the comparison in the previous section, two different strategies are compared. There are (1) disturbing numbers of jobs evenly to machines and (2) balancing the workload of machines. The compared algorithms of Biskup and Cheng [1] and Arık and Toksarı [2] use the first strategy and the experimental study shows that the proposed heuristic with the second strategy and optimal policies outperforms its rivals.

Lots of variants of parallel machine scheduling problems with common due dates, earliness/ tardiness penalties, and other characteristics have been investigated in the literature, but the investigated problem has not attention from researchers. According to reported literature, Biskup and Cheng [1] only studied the problem. In this study, an efficient heuristic algorithm using optimal policies of the problem is proposed and outperforms previous algorithms. Since the problem can be assumed new, there are lot of potential to extend it considering other scheduling characteristics like distinct weights, fuzzy/grey processing times, learning/deterioration effects, and batch processing. Also, the problem can be investigated by considering other machine environments such as flow-shop. There are so many extension possibilities because the problem considering both completion times and earliness/tardiness cost in the objective function can be associated with so many real-life examples. For instance, let us have a manufacturing company that rents machines/equipment in parallel to produce goods/services as jobs for these machines/equipment and this company has to follow a Just-In-Time management for its manufacturing since there are penalty costs associated with earliness and tardiness of jobs. In that sense, the company has to consider both completion times and the earliness/tardiness of jobs. The company has to consider the completion times because it pays for rental machines in its facilities. So many examples can be associated with the investigated problem.

Despite the existence of extensions such as fuzzy and intuitive fuzzy decision-making research problems, it is of great importance to examine operational research problems in a crisp environment. While fuzzy and intuitive approaches address uncertainties and non-precise data, emphasizing clear environments allows for a strong foundational understanding. This necessity arises from the need to establish a solid framework and foundational understanding before delving into more complex, nuanced extensions. Operational research problems in a precise environment serve the fundamental task of providing clear solutions and establishing foundational methodologies that pave the way for further research in fuzzy and intuitive fuzzy areas. The motivation behind investigating operational research problems in a crisp environment is multifaceted. Firstly, a comprehensive understanding of clear models helps to establish a strong conceptual foundation and enables researchers to grasp the underlying principles and techniques. This foundational understanding not only facilitates the development of more advanced models but also sheds light on the advantages and limitations of each approach by enabling a comprehensive comparison between clear and non-clear methodologies. Furthermore, examining problems in a clear environment serves as an important step in improving methodologies, increasing computational efficiency, and identifying scenarios where clear models may be more suitable or effective than their fuzzy counterparts. By elucidating the importance of vibrant environments in operational research, studies (Kumar [33,34,35,36,37]) have paved the way for a more nuanced, comparative analysis that enriches the depth and applicability of the field.

The study can be moved in uncertain environments like fuzzy, grey, and/or stochastic. For fuzzification of scheduling parameters like processing time, due dates, and weights, the papers (Toksarı and Arık [38, 39], Arık and Toksarı [2, 40,41,42], Rostami et al. [43], Arık [44, 45]) can be referred. With fuzzy parameters and decision variables, the arithmetic operations (See Zadeh [46]) must be also done within fuzzy set theory. The solution methodology using these arithmetic operations can be mathematical modeling or approximation methods. For fuzzy mathematical modeling studies of Allahviranloo et al. [47], Kumar et al. [48, 49], Jayalakshmi et al. [50], Lai and Hwang [51], Fullér [52] and Liu and Iwamura [53] can be good guides for readers.

5 Conclusion

5.1 Research conclusion

In this study, we investigate unrelated parallel machine scheduling problems with the restrictive common due date where the objective is to minimize the sum of completion times, earliness durations, and tardiness durations of jobs. We show some properties of the problem. Furthermore, we showed three optimal policies for the problem. The first optimal policy is to increase the number of early jobs in the schedule as much as possible. The second optimal policy is to use the SPT dispatching rule for assigning tardy jobs. The third optimal policy is to distribute tardy jobs on machines with equal tardy workloads without increasing the cost. By using these policies of the problem, we proposed a heuristic algorithm and compared it with two existing algorithms. We generated some test instances for an experimental study. Our experimental study revealed that our proposed heuristic that uses optimal policies of the problem outperforms other existing algorithms. Furthermore, we discuss the performance of our proposed heuristic by separating it into its components. Our discussion and analysis reveal that the most effective component of the proposed heuristic is the solution construction phase that increases/decreases the number of early/tardy jobs at the beginning of the algorithm.

5.2 Theoretical implications

Since the investigated problem considers both earliness/tardiness and completion times in the objective function, the well-known properties and policies such as V-shaped cannot be implemented. Therefore properties and policies have been drawn for this problem and also these can be implemented and improved for similar scheduling problems with both crisp and uncertain parameters like fuzzy processing times and weights.

5.3 Manegerial contribution

The identification of three optimal policies provides a strategic framework for managers to make informed decisions regarding job scheduling. Managers can leverage these policies to devise scheduling strategies that prioritize early jobs, optimize tardy job assignments, and balance workload distribution across machines to minimize completion times and associated costs. Recognizing the potential impact of additional constraints like release dates and setup times prompts managers to prepare for evolving operational scenarios. Managers can anticipate and strategize for the integration of these constraints, allowing for more agile and adaptive scheduling practices. Encourages a culture of innovation within organizations by leveraging cutting-edge scheduling methodologies to stay ahead in a competitive market landscape.

5.4 Limitations and future research perspectives

The proposed properties and policies have been drawn for this problem and also these can be implemented and improved for similar scheduling problems. For future research, optimal policies and the heuristic introduced in this paper may be used in metaheuristic methods to increase solution quality. Furthermore, additional constraints such as release dates and sequence-dependent setup times can be considered within the problem and new optimal policies can be searched.