Scheduling with a common due-window: Polynomially solvable cases

The single machine scheduling problem to minimize maximum weighted absolute deviations of job completion times from a common due-date, is known to be NP-hard. However, two special cases have been shown to have polynomial time solutions: the case of unit processing time jobs, and the case of due-date assignment for a given job sequence. We extend both cases to a setting of a common due-window. We show that the unit-job problem includes 12 different sub-cases, depending on the size and location of the (given) due-window. Scheduling and due-window assignment for a given job sequence is solved for a single machine, for parallel identical machines and for flow-shops. For each of the above cases, an appropriate special-structured linear program is presented.     

Scheduling a maintenance activity and due-window assignment on a single machine

We study a single machine scheduling and due-window assignment problem. In addition to the traditional decisions regarding sequencing the jobs and scheduling the due-window, we allow an option for performing a maintenance activity. This activity requires a fixed time interval during which the machine is turned off and no production is performed. On the other hand, after the maintenance time, the machine becomes more efficient, as reflected in the new shortened job processing times. The objective is to schedule the jobs, the due-window and the maintenance activity, so as to minimize the total cost consisting of earliness, tardiness, and due-window starting time and size. We introduce an efficient (polynomial time) solution for this problem.     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

Earliness/tardiness production planning approaches with due-window for manufacturing systems

Although the earliness/tardiness production planning approaches for manufacturing systems with due-date have appeared in the literature, in practice, customers prefer a time duration rather than an exact due-date. This kind of due-date is called due-window. This paper focuses on the production planning problems to minimize the total earliness and tardiness penalties with a due-window subject to the manufacturing resource constraints. Two models, one for mass manufacture and another for one-of-a-kind product (OKP) manufacture, are discussed separately. By means of mathematical deduction, the model for mass manufacture is translated into a linear programming problem and solved by a simplex method. In the case of OKP manufacture, the problem is reduced to a linear 0–1 programming model, using the elaborate definition of variables. The computational results show that both algorithms achieve the optimal production planning and are applicable to practical manufacturing systems.     

Scheduling problems with two competing agents to minimized weighted earliness–tardiness

We study scheduling problems with two competing agents, sharing the same machines. All the jobs of both agents have identical processing times and a common due date. Each agent needs to process a set of jobs, and has his own objective function. The objective of the first agent is total weighted earliness–tardiness, whereas the objective of the second agent is maximum weighted deviation from the common due date. Our goal is to minimize the objective of the first agent, subject to an upper bound on the objective value of the second agent. We consider a single machine, and parallel (both identical and uniform) machine settings. An optimal solution in all cases is shown to be obtained in polynomial time by solving a number of linear assignment problems. We show that the running times of the single and the parallel identical machine algorithms are O(n^m+3), where n is the number of jobs and m is the number of machines. The algorithm for solving the problem on parallel uniform machine requires O(n^m+3m³) time, and under very reasonable assumptions on the machine speeds, is reduced to O(n^m+3). Since the number of machines is given, these running times are polynomial in the number of jobs.     

An improved earliness–tardiness timing algorithm

Earliness–tardiness criteria with distinct due dates usually induce NP-complete problems. Researchers have focused on particular cases like the timing problem, which is to look for the optimal schedule when the jobs sequence is already known. These timing algorithms are very useful since they can be used in more complex procedures. In the first part of this paper we provide the most efficient and fairly general algorithm to solve the one-machine timing problem. It is then adapted to a permutation flow shop problem.     

A note: Minmax due-date assignment problem with lead-time cost

All three major classes of due-date assignment models (CON, SLK and DIF) have been solved in the literature for a minsum setting, and only two of them (CON and SLK) have been solved for a minmax setting. In this note we introduce a solution for the missing minmax model of DIF. Specifically, we study a single-machine scheduling and due-date assignment problem, in which job-dependent lead-times   are considered. Three cost components for each job are assumed: earliness cost, tardiness cost, and the cost for delaying the due-date (beyond its lead-time). The goal is to schedule the jobs and to assign due-dates, such that the maximum cost among all the jobs is minimized. We introduce an O(nlog²n)$O(n{\log }^{2}n)$ solution algorithm (where n is the number of jobs).     

Minimizing the earliness–tardiness costs on a single machine

In this paper the one-machine scheduling problem with linear earliness and tardiness costs is considered. The cost functions are job dependent and asymmetric. The problem consists of two sub-problems. The first one is to find a sequence of jobs and the second one is to find the job completion times that are optimal for the given sequence. We consider the second sub-problem and propose an algorithm solving the problem in O(nlogn)$\mathrm{O}(n\log n)$ time.     

An efficient algorithm for minimizing earliness,tardiness, and due-date costs for equal-sized jobs

We consider a single-machine scheduling problem with equal-sized jobs. The objective is to minimize the maximum weighted earliness–tardiness and due-date costs. We present an algorithm to solve this problem. Our algorithm makes use of bottleneck jobs and priority queues, and has a computational complexity of O(n⁴logn)$O(n^4\log n)$. This complexity is a significant improvement of the existing algorithm in the literature.     

Scheduling in a two-machine flowshop for the minimization of the mean absolute deviation from a common due date

This paper addresses the minimization of the mean absolute deviation from a common due date in a two-machine flowshop scheduling problem. We present heuristics that use an algorithm, based on proposed properties, which obtains an optimal schedule for a given job sequence. A new set of benchmark problems is presented with the purpose of evaluating the heuristics. Computational experiments show that the developed heuristics outperform results found in the literature for problems up to 500 jobs.     

A new model for the preemptive earliness–tardiness scheduling problem

This paper addresses a new model for the one-machine earliness–tardiness scheduling problem where jobs can be interrupted. Some dominance rules and a lower bound are derived. A new timing algorithm is also presented and a local search algorithm based on this timing algorithm permits the computation of good feasible solutions. We experimentally compare our timing algorithm with a previously published timing algorithm. The tests show that the execution time of the new timing algorithm is significantly faster, especially for large instances. The values of the solutions are compared to the lower bound.     

Unrelated parallel machine scheduling with dedicated machines and common deadline

This paper addresses a scheduling problem in the manufacturing of Polyvinyl Chloride pipes. There are two main attributes of PVC pipes: diameter and color. Each attribute has a corresponding attribute setup time and usually has several different levels. Each extruder produces different PVC pipe products based on the diameters as large, middle and small. The alternatives exist between these extruders, where the large and the middle type extruders can be used to produce the PVC pipes with the other diameters; the small type extruders can be used to produce the PVC pipes with middle diameters but cannot produce those with large diameters. The processing times are longer in all of the alternatives among different types of extruders. The objective is to minimize the total completion time for the unrelated parallel machine problem.Three dedicated machine heuristics are proposed herein for the problem and have been evaluated by comparing with the current scheduling method used in the case plant. The computational results show that the proposed constructive heuristics outperform the current scheduling method with significant improvements and can be used to solve large-size problems in reasonable computational times.     

Weighted tardiness for the single machine scheduling problem:An examination of precedence theorem productivity

Earlier research by Kanet [11] has provided a number of new theorems for deciding precedence between pairs of jobs for 1∣∣Σw_jT_j. The theorems supplant those of Rinnooy Kan, Lageweg, and Lenstra [16]. Presented here are the results of an analysis of the marginal benefit these new theorems provide over the earlier versions of Rinnooy Kan et al. Results show that the new theorems can provide noteworthy improvements in the ability to discover precedence relations between job pairs. For a large set of problem instances the new theorems uncovered up to 8% more precedence relations than the original theorems of Rinnooy Kan et al. The improvement in the productivity in discovering precedence relations shows to be dependent on the coefficient of variation of the distribution of job weights. Logical application of the theorems is to include them in search procedures and/or heuristic approaches to 1||Σw_jT_j. One such heuristic based on the theorems is provided here in which the solutions to a large set of sample problems are within 8–12% of the optimum.     

A note on “Two-machine flow-shop scheduling with rejection” and its link with flow-shop scheduling and common due date assignment

In a recent paper by Shabtay and Gasper “Two-machine flow-shop scheduling with rejection, Computers and Operations Research”, forthcoming, doi:10.1016/j.cor.2011.05.023, several complexity and approximation results are proposed for a two-criteria two-machine flow-shop scheduling problem with rejection. The two criteria to be minimized are the makespan the total rejection cost. This note positions the contribution of such results with respect to the contributions of the literature on common due date assignment and flow-shop scheduling not considered in the work of Shabtay and Gasper.     

Minmax scheduling with acceptable lead-times: Extensions to position-dependent processing times,due-window and job rejection

We focus on a due-date assignment model where due-dates are determined by penalties for jobs exceeding pre-specified (job-dependent, different) deadlines. The underlying assumption of this model, denoted by DIF, is that there are "lead times that customers consider to be reasonable and expected". In a minmax DIF model, the value of the objective function is that of the largest job/due-date cost. The goal is to find both the job sequence and the due-dates, such that this value is minimized.In this paper we study several extensions of the minmax DIF model. First, we consider general position-dependent job processing times. Then we extend the model to a setting of a due-window for acceptable lead-times. Here, the assumption is that a time interval exists, such that due-dates assigned to be within this interval are not penalized. The last extension of the DIF model is to a setting allowing job-rejection. This option reflects many real-life situations, where the scheduler may decide to process only a subset of the jobs, and the rejected jobs are penalized. The first two extensions are shown to be polynomially solvable: we introduce solution algorithms requiring O(n³) and O(n⁴) time, respectively, where n is the number of jobs. The last extension (assuming job-rejection) is proved to be NP-hard in the ordinary sense, and an efficient pseudo-polynomial dynamic programming algorithm is introduced.     

A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity

This note considers a single machine scheduling and due-window assignment problem, in which the processing time of a job is a linear function of its starting time and the job-independent deterioration rates are identical for all jobs. We allow an option for performing a rate-modifying activity for changing the normal processing times of the jobs following this activity. The objective is to schedule the jobs, the due-window and the rate-modifying activity so as to minimize the sum of earliness, tardiness and due-window starting time and due-window size costs. We introduce a polynomial solution for the problem.     

Single-machine batch delivery scheduling with an assignable common due date and controllable processing times

We consider single-machine batch delivery scheduling with an assignable common due date and controllable processing times, which vary as a convex function of the amounts of a continuously divisible common resource allocated to individual jobs. Finished jobs are delivered in batches and there is no capacity limit on each delivery batch. We first provide an O(n⁵) dynamic programming algorithm to find the optimal job sequence, the partition of the job sequence into batches, the assigned common due date, and the resource allocation that minimize a cost function based on earliness, tardiness, job holding, due date assignment, batch delivery, and resource consumption. We show that a special case of the problem can be solved by a lower-order polynomial algorithm. We then study the problem of finding the optimal solution to minimize the total cost of earliness, tardiness, job holding, and due date assignment, subject to limited resource availability, and develop an O(nlog n) algorithm to solve it.     

Group scheduling and job-dependent due window assignment based on a common flow allowance

We study a single-machine group scheduling and job-dependent due window assignment problem in which each job is assigned an individual due window based on a common flow allowance. In the group technology environment, the jobs are divided into groups in advance according to their processing similarities and all the jobs of the same group are processed consecutively in order to improve production efficiency. A sequence-independent machine setup time precedes the processing of the first job of each group. A job completed earlier (later) than its due window will incur an earliness (tardiness) penalty. Our goal is to find the optimal sequence for both the groups and jobs, together with the optimal due window assignment, to minimize the total cost that comprises the earliness and tardiness penalties, and the due window starting time and due window size costs. We give an O(n log n)time algorithm to solve this problem.     

A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date

Although the concept of just-in-time (JIT) production systems has been proposed for over two decades, it is still important in real-world production systems. In this paper, we consider minimizing the total weighted earliness and tardiness with a restrictive common due date in a single machine environment, which has been proved as an NP-hard problem. Due to the complexity of the problem, metaheuristics, including simulated annealing, genetic algorithm, tabu search, among others, have been proposed for searching good solutions in reasonable computation times. In this paper, we propose a hybrid metaheuristic that uses tabu search within variable neighborhood search (VNS/TS). There are several distinctive features in the VNS/TS algorithm, including different ratio of the two neighborhoods, generating five points simultaneously in a neighborhood, implementation of the B/F local search, and combination of TS with VNS. By examining the 280 benchmark problem instances, the algorithm shows an excellent performance in not only the solution quality but also the computation time. The results obtained are better than those reported previously in the literature.