1 Introduction

Due dates are generally considered as inputs in scheduling problems. If all jobs’ due dates are the same, then this is named a scheduling problem with the common due date. Even a common due date can be an input, the decision-maker would desire to optimize the common due date to satisfy the performance criterion minimizing the cost combination of earliness/tardiness and setting a common due date. Such an optimization for the accurate common due date for the scheduling problem is named the common due date assignment problem. The effort for responding to customer orders on time by utilizing manufacturing facilities, time, and minimizing costs is the main goal of each manufacturing company. Negotiation between customers and the company might be about determining the due dates of jobs and there might be a common due date that all customers agree on. If both the customer’s satisfaction and cost minimization of the company lies under setting the due dates of all jobs to a common due date, then the best way to assign that common due date is to optimize it according to each customer’s objective and the company’s own objective. The common due date in a scheduling problem makes some jobs early and others tardy. When a job is completed before the promised due date, such a job is called an early job. For instance, an early job is not desired because it has to be stored in a warehouse, resulting in costs for inventory and insurance. When a job is completed after the promised due date, such a job is called a tardy job. A tardy job is not desired because the manufacturer loses some of its earnings due to the contract penalties as well as some goodwill and reputation [1]. Since there is a common due date for all jobs of the customers, some of these jobs will be completed before/after the assigned common due date and they will be early/tardy. Earliness/tardiness has some costs for the company. Since these jobs might belong to different customers and their importance might be different as well. Earliness/tardiness unit cost for each job might be different than others. Thus earliness/tardiness weights/costs can be different within a scheduling problem with common due date consideration. The common due date assignment has been investigated by researchers for more than 30 years. Panwanker et al. [2] consider a single machine weighted earliness/tardiness scheduling problem where the common due date is a decision variable and each early/tardy job’s weight is the same. In a classical scheduling triple notation, the problem with \(n\) jobs can be expressed as \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\) where j is the job index (\(j\in \{\text{1,2},3,.,n\}\)), \(d\) is the common due date, \(\gamma\) is the penalty cost of assigning common due date, \(\alpha \left(\beta \right)\) is earliness (tardiness) penalty cost for all jobs, and \({E}_{j}\left({T}_{j}\right)\) is earliness/tardiness of job \(j\). \({E}_{j}\) is a positive decision variable for the problem and \({E}_{j}=\text{max}\left(0,d-{C}_{j}\right)\) where \({C}_{j}\) is the completion time of job \(j\). Similarly, \({T}_{j}\) is also a positive decision variable and \({T}_{j}=\text{max}\left(0,{C}_{j}-d\right)\). They propose a polynomial time algorithm to solve their investigated problem and prove that their algorithm solve the problem optimally. The problem with given common due date \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}\) has also polynomial time algorithm [2] to solve it optimally if \(d\) is an unrestrictive common due date. In a scheduling problem with a given common due date, there are two options: (1) unrestrictive common due date where \(d\) is big enough to make all jobs completed before or at the common due date and (2) restrictive common due date where \({d}^{res}\) is not big enough to make all jobs early or on-time. The same problem with restrictive common due date \(1\left|{d}_{j}={d}^{res}\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}\) is a NP-Hard [3] problem and an optimal solution algorithm has not been revealed by the researchers so far. Furthermore, \(1\left|{d}_{j}={d}^{res}\right|\sum {a}_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}\) where \({a}_{j}\)(\({\beta }_{j}\)) is the distinct earliness/tardiness cost/weight for job \(j\) is also NP-Hard and the optimal sequence of this problem has the V-shaped property [4,5,6,7,8] showing that early jobs are sequenced in decreasing order of their ratios of processing times/earliness weights and tardy jobs are sequenced in increasing order of their ratios of processing times/tardiness weights. Kanet [4] shows that there is a polynomial time algorithm to solve \(1\left|{d}_{j}=d\right|\sum {E}_{j}+\sum {T}_{j}\) optimally. As understood from this short literature, if jobs in the problem have different earliness/tardiness weights, the problem becomes a NP-Hard problem.

Even most single-machine earliness/tardiness scheduling problems are still NP-Hard, the researchers have investigated polynomial-time optimal or approximation algorithms for earliness/tardiness scheduling problems with due date determination decisions. Cheng and Gupta [9] presented a survey paper for scheduling problems with due date determination decisions. They investigated the problem from the perspectives “static” and “dynamic”. This classification was made by Elion [10]. Nowadays some sort of dynamic is also referred as online. Gordon et al. [11] drew an extensive framework for common due date assignment problems in their survey paper. They investigated common due assignment problems in single and parallel machine environments. They summarized the results of the algorithms and the complexity of the common due date assignment and scheduling problems. Seidmann et al. [12] investigated \(1\left|{d}_{j}\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma {A}_{j}\) where \({A}_{j}=\text{m}\text{a}\text{x}(0, {d}_{j}-A)\), \({d}_{j}\) is assigned due date for job \(j\) and \(A\) is the lead time that customers consider to be reasonable and expected. In their problem, the objective function is to minimize the earliness/tardiness costs of jobs and the total time that the assigned due dates for all jobs exceeds \(A\). They proved that there is a polynomial time algorithm to solve their problem optimally. For \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\), the optimal solution has a property that shows the assigned common due date is equal to one of the completion times of jobs. This was showed by Panwalkar et al. [2]. Cheng [13] offered an alternative proof for this property of the optimal solution by using Kuhn-Tucker’s optimality conditions. Sung et al. [14] considered the problem of \(1\left|{d}_{j}=d\right|\sum {w}_{j}\left({d-C}_{j}\right)/{w}_{j}\) to minimize the total weighted mean absolute deviations of job completion times from the common due date. They determined several dominant solution properties to organize two efficient heuristic solution algorithms for their problem. Koulamas [15] proposed a polynomial time (O(n3)) dynamic programming to solve the problem of \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum {a}_{j}{V}_{j}+\sum {b}_{j}{U}_{j}+\sum \gamma d\) where \({V}_{j}\)(\({U}_{j}\)) is a binary decision variable that is 1 if job \(j\) is early(tardy) and \({a}_{j}\)(\({b}_{j}\)) is the penalty cost of job \(j\) if it is early(tardy). Furthermore, Koulamas [15] showed that there is a linear time algorithm to solve \(1\left|{d}_{j}=d\right|\sum {a}_{j}{V}_{j}+\sum {b}_{j}{U}_{j}+\sum \gamma d\) optimally. De et al. [16] showed that there is a linear-time algorithm for the problem of \(1\left|{d}_{j}=d\right|\sum {b}_{j}{U}_{j}+\sum \gamma d\). Koulamas [17] proposed a linear time dynamic programming algorithm to solve of \(1\left|{d}_{j}=d\right|\sum {\alpha }_{j}{E}_{j}+\sum {b}_{j}{U}_{j}+\sum \gamma d\). For the same problem’s optimal solution, Kahlbacker and Cheng [18] proposed an O(n2) polynomial-time algorithm for the problem in parallel machine environment. Li and Chen [19] proposed a polynomial-time O(n3) algorithm to solve the problem of \(1\left|{d}_{j}=d, {p}_{j}=p\right|\sum {\alpha }_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}+\sum {a}_{j}{V}_{j}+\sum {b}_{j}{U}_{j}+\sum \gamma d\) where all jobs have the same processing time. Shabtay et al. [20] investigated the problems of \(1\left|{d}_{j}=d\right|\sum {\alpha }_{j}{Q}_{j}+\sum {\beta }_{j}{Y}_{j}+\sum \gamma d\) and \(1\left|d\le {d}_{j}\le d+\delta \right|\sum {\alpha }_{j}{Q}_{j}+\sum {\beta }_{j}{Y}_{j}+\sum \gamma d+\sum \phi \delta\) where \({Q}_{j}=\text{min}\left({p}_{j},{max}\left(0,d-{C}_{j}+{p}_{j}\right)\right)\forall j\), \({Y}_{j}=\text{min}\left({p}_{j},{T}_{j}\right)\forall j\), \(\delta\) is the time interval for the common due date window and \(\phi\) is the penalty of the common due date window. Their problems’ objective functions are to minimize the penalty cost of early and tardy work, the common due date assignment cost, and the cost of the common due date window. They showed polynomially solvable cases of their problem when the common due date and the common due date window are unbounded. They also stated that their problem becomes NP-Hard when it is bounded. Yeung et al. [21] proposed an O(nlogn) polynomial-time algorithm to find the optimal solution of the problem of \(1\left|d\le {d}_{j}\le d+\delta \right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum a{V}_{j}+\sum b{U}_{j}+\sum \gamma d\) where \(a\)(\(b\)) is the penalty cost of any job if it is early(tardy). We summarize the literature review for due date assignment problems in Table 1 by adding other important studies in multi machine environment. As seen in Table 1, \(\sum _{j=1}^{n}\left({\alpha }_{j}{E}_{j}+{\beta }_{j}{T}_{j}+\gamma d\right)\) problem for all machine environments has not been studied by researchers. As long as we know from the reported literature, Mosheiov and Yovel [27] only investigated \(\sum _{j=1}^{n}\left({\alpha }_{j}{E}_{j}+{\beta }_{j}{T}_{j}+\gamma d\right)\) problem with unit processing times (\({P}_{j}=1 \forall j\)) by proposing a heuristic approach. The rest of studies considered \(\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\) problem or its variants by proosing heuristics and polynomial time algorithms. Since \(\sum _{j=1}^{n}\left({\alpha }_{j}{E}_{j}+{\beta }_{j}{T}_{j}+\gamma d\right)\) problem is NP-Hard, it needs still an approximate solution approach for finding a near-optimal solution. As seen from the literature given in Table 1, there are so few studies considering metaheuristic for the problem when the common due date is a decision variable, most of the studies in Table 1 have proposed heuristics for NP hard problem with the common due date that is a decision variable.

Table 1 Literature review
Full size table

In this study, we consider \(1\left|{d}_{j}=d\right|\sum {\alpha }_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}+\sum \gamma d\) where each job’s weights for earliness and tardiness are different from others. By using some properties of optimal solutions of similar problems such as \(1\left|{d}_{j}={d}^{res}\right|\sum {a}_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}\), \(1\left|{d}_{j}=d\right|\sum {E}_{j}+\sum {T}_{j}\), \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}\) and \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\), we propose a heuristic for single machine weighted earliness/tardiness scheduling and common due date assignment problem. The remainder of the paper is as follows: Sect. 2 presents a mathematical model for the problem. Section 3 introduces our proposed heuristic for the problem. Section 4 presents an experimental study to compare our proposed heuristic with an exact solution approach. Section 5 draws a conclusion and future projection for the reader.

2 Mathematical model

In this section, we present a mixed-integer linear programming model for our investigated problem. The model was originally proposed by Keha et al. [33]. We just add common due date assignment consideration into the model. There are \(n\) jobs to be processed in a single machine. Each job has its own earliness and tardiness weights in the objective function. All jobs have the same common due date which is a decision variable that is a part of the performance criterion of the problem. Determination of this common due date has a constant cost for all jobs in the objective function. We have some assumptions for the investigated problem as follows: the machine can only process at most one job at the same time, the machine is ready to process jobs at zero start time, processing times of jobs, and costs for earliness and tardiness are non-negative and preemption is not allowed. Indices, parameters, decision variables, and equations/inequations of the model are as follows:

Indices:

\(j\), \(k\): indices of jobs (\(j\in \{\text{1,2},\dots ,n\}\) and \(k\in \{\text{1,2},\dots ,n\}\))

Parameters:

\({p}_{j}:\) processing time of job \(j\)

\({\alpha }_{j}:\) earliness unit cost/weight of job \(j\)

\({\beta }_{j}:\) tardiness unit cost/weight of job \(j\)

\(\gamma :\) common due date assignment cost for each job

\(M\): arbitrary large number (\(M=\sum _{j=1}^{n}{p}_{j}\))

Decision variables:

\({C}_{j}:\) completion time of job \(j\)

\({E}_{j}:\) earliness duration of job \(j\)

\({T}_{j}:\) tardiness duration of job \(j\)

\(d:\) common due date

\({y}_{jk}:\) binary decision variable for determining which job is processed before another job. If job \(j\) is processed before job \(k\) in the machine, then it is 1. Otherwise, it is 0.

Objective function:

$$\text{Min} \,\,\sum _{j}{\alpha }_{j}{E}_{j}+\sum _{j}{\beta }_{j}{T}_{j}+n\gamma d$$
(1)

S.t.:

$${C}_{j}\ge {p}_{j}\quad \forall j$$
(2)
$${C}_{j} + {p}_{k}\ge {C}_{k}+M\left(1-{y}_{jk}\right) \quad \forall j,k \,\, and \,\, j<k$$
(3)
$${C}_{k} + {p}_{j}\ge {C}_{j}+M{y}_{jk} \quad \forall j,k \,\, and \,\, j<k$$
(4)
$${C}_{j}+{E}_{j}-{T}_{j}=d \quad \forall j$$
(5)
$${y}_{jk}\in \left\{\text{0,1}\right\} \quad \forall j,k$$
(6)
$${C}_{j},{E}_{j},{T}_{j}\ge 0\quad \forall j$$
(7)

The objective function (1) is to minimize the cost combination of the weighted earliness/tardiness costs and setting common due date costs. Constraint (2) assures that the completion time of job \(j\) is greater than or equal to its processing time. Constraints (3–4) are disjunctive constraints assuring that either job j is processed before job k or job j is processed after job k. These constraints are for all job pairs. For any jobs \(j\) and \(k\), there must be only two potential job sequences: (1) the sequence where the job \(j\) is processed before job \(k\) or (2) the sequence where job j is processed after job \(k\). Therefore if \({y}_{jk}=1\), then \({y}_{kj}\)must be 0 or the other way around. Constraint (5) shows that job \(j\) can be completed as early, on time, or tardy. If \({C}_{j}=d\) then job \(j\) is an on-time job and \({E}_{j}\)(\({T}_{j}\)) is 0. Else if \({C}_{j}<d\) (\({C}_{j}>d\)), then job \(j\) is early (tardy) and \({E}_{j}=d-{C}_{j}\) (\({T}_{j}={C}_{j}-d\)). For any job \(j\), there is no possibility of both \({E}_{j}\) and \({T}_{j}\) are greater than zero since \({C}_{j}\) is either equal to \(d\) or less (greater) than \(d\).

3 The proposed heuristic

In this section, we propose a heuristic for \(1\left|{d}_{j}=d\right|\sum {\alpha }_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}+\sum \gamma d\) by using some properties of optimal solutions of similar problems such as \(1\left|{d}_{j}={d}^{res}\right|\sum {a}_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}\), \(1\left|{d}_{j}=d\right|\sum {E}_{j}+\sum {T}_{j}\), \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}\) and \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\). These properties are as follows:

  • For the problem of \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\), the optimal common due date must be less than or equal to the sum of processing times \({d}^{*}\le \sum _{j}{P}_{j}\) where \({d}^{*}\)is the optimal common due date. Therefore, the optimal common due date is a restrictive common due date. This property (See Panwanker et al. [2]) can be applied to our investigated problem.

  • For the problem of \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\), if \(\gamma \ge \beta\) then \({d}^{*}=0\) and the job sequence arranged with the shortest processing time (SPT) rule is the optimal sequence. This property (See Panwanker et al. [2]) can be applied to our investigated problem.

  • For any job sequence of the problem of \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\), there exists an optimal common due date that is equal to one of the completion times of jobs. This property (See Panwanker et al. [2]) can be applied to our investigated problem.

  • For any job sequence of the problem of \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\), there exists an optimal common due date equal to \({C}_{\left[K\right]}\), where \(K\) is the smallest integral value greater than or equal to \(n(\beta -\gamma )/(\alpha +\beta )\). This property (See Panwanker et al. [2]) cannot be applied to our investigated problem since \({\alpha }_{j}\)(\({\beta }_{j})\) is distinct for each job.

  • For problems of \(1\left|{d}_{j}={d}^{res}\right|\sum {a}_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}\), \(1\left|{d}_{j}=d\right|\sum {E}_{j}+\sum {T}_{j}\), and \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}\), the common due date is an input. The optimal job sequences for these problems have the V-Shaped property. This property (See Kanet [4] and Arık [8]) of the optimal solution shows that the early jobs in the optimal sequence are sequenced in decreased order of \({P}_{j}/{a}_{j}\) values and the tardy jobs are sequences in increased order of \({P}_{j}/{\beta }_{j}\) values. Thus the optimal sequence can be arranged with the weighted shortest processing time (WSPT) and the weighted longest processing time (WLPT) rules. This property can be also applied to our investigated problem.

  • For problems of \(1\left|{d}_{j}={d}^{res}\right|\sum {a}_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}\), \(1\left|{d}_{j}=d\right|\sum {E}_{j}+\sum {T}_{j}\), and \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}\), the start time of the first job in the sequence can be greater than zero and none of the completion times of jobs can be equal to the common due date. This property (See Kanet [4] and Arık [1]) cannot be applied to our problem.

The problem of \(1\left|{d}_{j}=d\right|\sum {\alpha }_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}+\sum \gamma d\) have structural similarities with other problems of \(1\left|{d}_{j}={d}^{res}\right|\sum {a}_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}\), \(1\left|{d}_{j}=d\right|\sum {E}_{j}+\sum {T}_{j}\), \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}\) and \(1\left|{d}_{j}=d\right|\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\). We use some of above properties in our proposed heuristic as follows:

  1. 1.

    The zero start time of the machine,

  2. 2.

    The common due date that is less than or equal to the sum of processing times,

  3. 3.

    The V-shaped property of the optimal solution, and.

  4. 4.

    (4)The common due date is equal to one of the completion times of jobs.

We apply these properties in our heuristics as follows:

  1. 1.

    We set always the start time of the first job in the sequence zero in our proposed heuristics,

  2. 2.

    We search the common due date between zero and the sum of processing times,

  3. 3.

    By using the V-shaped property, we order early jobs with the WLPT rule and tardy jobs with the WSPT rule around the determined common due date,

  4. 4.

    We set the common due date to the completion time of the job in position \(r\) where (\(r\in \{\text{0,1},\text{2,3},\dots ,n\}\)) and we increase \(r\) by one at each iteration.

In our proposed heuristic, we search the common due date from zero. When\(d=0\), the best sequence of the problem can be obtained with the WSPT rule. Since \(d=0\), all jobs are tardy and their best sequence can be obtained by using the WSPT rule. In case there are some early jobs because \(d>0\) and the start time of the machine is non-zero, then early jobs must be ordered with the WLPT rule and the remaining tardy jobs must be ordered with the WSPT rule. This is our initial solution (\(\pi\)) and we record it as the best solution (\({\pi }^{*}\)) for now. Within a for loop, we test each job at the first position of solution \(\pi\) by increasing the position number (\(r\in \{\text{0,1},\text{2,3}\dots ,n\}\)) of the completion time of the job by one. We set \({d=C}_{\left[r\right]}\) for each \(r\) (note that \(r=0\)implies that \(d=0\)). For each increment of \(r\), we order early(tardy) jobs with the WLPT(WSPT). When we find a better candidate solution \({\pi }^{{\prime }{\prime }}\) than \({\pi }^{*}\), we replace \({\pi }^{*}\) with \({\pi }^{{\prime }{\prime }}\). Then, the remaining search goes on with new \({\pi }^{*}\) by using the V-shaped property and the zero-start time of the machine until the stopping criterion is satisfied. For this algorithm, we use a predetermined allowed elapsed time limitation as a stopping criterion. The pseudo-code of the proposed heuristic is given in Fig. 1. As seen in Fig. 1, the complexity of our proposed heuristic is O(n3).

4 Experimental study

In this section, we test our proposed heuristic’s performance in view of solution quality by comparing it with solutions obtained from a commercial solver. We use a stopping criterion that allows running the algorithm until \(n\) seconds or the algorithm ends its all steps to solve the problem. \(n\) seconds means that the algorithm will use the number of jobs in the problem as a stopping criterion of the solution method in elapsed seconds. As seen from the literature review, there is no heuristic, metaheuristic or pseudo-polynomial algorithm for \(1\left|{d}_{j}=d\right|\sum {\alpha }_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}+\sum \gamma d\) problem. Even there are some approximation algorithms for \(\sum \alpha {E}_{j}+\sum \beta {T}_{j}+\sum \gamma d\) problems and their variants, these algorithms are not applicable because of the same earliness/tardiness weight consideration in those problems. Therefore, we use the mathematical modelling approach and an commercial solver to evaluate our proposed heuristic’s performance. We use the CPLEX solver in GAMS 28.2 commercial software to code and solve the mathematical model introduced in this study. The commercial solver’s solution time is also restricted until \(n\) seconds. We use a benchmark data set of common due date scheduling problems. This data set was originally generated by Biskup and Feldmann [34] for the problem where the common due date is a parameter. In this study, we use this data set for our problem where the common due date is a decision variable. This data set includes seven groups of test problems. These groups have 10, 20, 50, 100, 200, 500, and 1000 jobs. Each group has 10 test instances. The data set can be retrieved from http://people.brunel.ac.uk/~mastjjb/jeb/orlib/schinfo.html. This data set doesn’t have \(\gamma\) values for test instances so we use 6 \(\gamma\) values where \(\gamma \in \{\text{0,4},\text{8,12,16,20}\}\) for each instance. We use \(\gamma\) values between 0 and 20 since other parameters in test instances such as \({P}_{j}\), \({\alpha }_{j}\) and \({\beta }_{j}\) are generated randomly between 1 and 20 by Biskup and Feldmann [34]. There are 7 \(n\) values and 6 \(\gamma\) values for our test groups and each group has 10 test instances so there are 420 test problems in our experimental study. Both our proposed heuristic and the commercial solver solve each instance once. We code our proposed heuristic in Visual Studio 2019 by using C# programming language. Furthermore, we use C# programing language to generate GAMS file for all test instances. We call GAMS library by using C# programming language in Visual Studio to solve test instances. Each solution’s objective function, solution times in milliseconds, and the common due date value are recorded. Our experimental study has been done on a workstation desktop having an Intel Xeon E-2136 CPU @ 3.30 GHz and 16 GB RAM. Our proposed heuristic solves test problems in a shorter time by closing more the optimal solution than the commercial solver does. Even the commercial solver could not find a solution for 99 test instances where \(n\ge\) 200 until its solution time reaches \(n\) seconds, the proposed heuristic solves all test instances. For small-size instances where \(n\le\) 50, the commercial solver may find better solutions than our proposed heuristic finds. Table 2 shows how many times our proposed heuristic finds better solutions than the commercial solver within time limitations. For all test problems, the proposed heuristic’s solution quality is 30.74% better than solutions obtained with GAMS. When \(n\) = 10 and \(\gamma\) = 0, the proposed heuristic finds 7 out of 10 best solutions for test instances. When \(n\) = 20 and \(\gamma\) = 8, the proposed heuristic finds none of 10 best solutions for test instances. When \(n\le\) 50, the proposed heuristic does not outperform the commercial solver and it just finds 44 of 180 best solutions. When \(n\ge\) 100, the proposed heuristic obtains better solutions for test instances except for one instance. Table 3 shows the average solution times of compared solution approaches for each test group. As seen in Table 3, the proposed heuristic consumes less time than the commercial solver to obtain a solution. If \(n\ge\) 100 then these solutions are better than the commercial solver finds and they are obtained in a shorter time with the proposed heuristic. We use the same stopping criterion for both methods to be fair in comparison. Someone may wonder what the solution quality of GAMS will be if there is no time limitation. We test our mathematical model using GAMS with its default settings to solve problems optimally. Most of the problems where \(n\ge\)200 could not be solved optimally and the solver did not report solutions for these problems. The solution quality of GAMS for these problems when it works with its default settings is still worse than the solution quality of the proposed heuristic. Since our proposed heuristic is an O(n3) algorithm, we use \(n\) as a parameter in our stopping criterion.

Table 2 How many times our proposed heuristic finds the better solutions
Full size table
Table 3 Average solution times of the proposed heuristic and the commercial solver for test instance group
Full size table
Fig. 1
figure 1

The pseudo-code for the proposed heuristic for \(1\left|{d}_{j}=d\right|\sum {\alpha }_{j}{E}_{j}+\sum {\beta }_{j}{T}_{j}+\sum \gamma d\)

Full size image

5 Conclusion

This study investigates a heuristic algorithm for single machine weighted earliness/tardiness scheduling and common due date assignment problem where earliness/tardiness weights of jobs are different. The objective function of the problem is to minimize the cost combination of weighted earliness/tardiness and common due date assignment cost. By using several properties such as the V-shaped property, the zero-start time, and the common due date that equals to a completion time of a job in the sequence of similar problems, we develop a heuristic solution approach. Since there is no similar heuristic or solution method in the literature, we test our proposed heuristic against the mathematical model coded in a commercial solver. For a fair comparison, we use the same computer environment and solution time restriction in our experimental study. When the number of jobs increases, the efficiency of our proposed heuristic increases and it finds better solutions in a shorter time than the commercial solver finds. For future research, this heuristic can be extended into a parallel machine environment with additional objective functions such as the total tardy work and the total number of tardy jobs. Moreover, solution of this heuristic can be used as an initial solution for other solution improvement heuristics or metaheuristics such as genetic algorithm, simulated annealing and tabu search. Furthermore, additional constraints such as sequence-dependent setup times and release times can be considered in a future extension for the proposed heuristic.