A note: Common due date assignment for a single machine scheduling with the rate-modifying activity

In this paper we study the single machine common due date assignment and scheduling problem with the possibility to perform a rate-modifying activity (RMA) for changing the processing times of the jobs following this activity. The objective is to minimize the total weighted sum of earliness, tardiness and due date costs. Placing the RMA to some position in the schedule can decrease the objective function value. Several properties of the problem are considered which in some cases can reduce the complexity of the solution algorithm.     

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.     

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.     

Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system

This study addresses 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, P∥(E+T)/∑_Ci$P\parallel (E+T)/\sum C_i$. The problem is demonstrated to be transformed into a simplified version of the parallel machine problem with the objective of minimizing makespan subject to minimum total flowtime, P∥_Cmax/∑_Ci$P\parallel C_{\max }/\sum C_i$. Several properties are considered to solve optimally the restricted version of the problem. A streamlined binary integer programming model is developed to solve the P∥_Cmax/∑_Ci$P\parallel C_{\max }/\sum C_i$ problem and the P∥(E+T)/∑_Ci$P\parallel (E+T)/\sum C_i$ problem. Computational experiments indicate that the binary integer programming model is superior to the existing optimization algorithm for the P∥_Cmax/∑_Ci$P\parallel C_{\max }/\sum C_i$ problem in the literature.     

Tabu search for scheduling on identical parallel machines to minimize mean tardiness

This paper presents a tabu search approach for scheduling jobs on identical parallel machines with the objective of minimizing the mean tardiness. Initially, we consider a basic tabu search that uses short term memory only. Local search is performed on a neighborhood defined by two types of moves. Insert moves consist of transferring each job from one machine to another and swap moves are those obtained by exchanging each pair of jobs between two machines. Next, we analyze the incorporation of two diversification strategies with the aim of exploring unvisited regions of the solution space. The first strategy uses long term memory to store the frequency of the moves executed throughout the search and the second makes use of influential moves. Computational tests are performed on problems with up to 10 machines and 150 jobs. The heuristic performance is evaluated through a lower bound given by Lagrangean relaxation. A comparison is also made with respect to the best constructive heuristic reported in the literature.     

Minimizing total earliness and tardiness on a single machine using a hybrid heuristic

This paper focuses on scheduling jobs with different processing times and distinct due dates on a single machine with no inserted idle time as to minimize the sum of total earliness and tardiness. This scheduling problem is a very important and frequent industrial problem that is common to most just-in-time production environments. This NP hard scheduling problem is herein solved using a hybrid heuristic which combines local search heuristics (dispatching rules, hill climbing and simulated annealing) and an evolutionary algorithm based on genetic algorithms. The heuristic involves low and high, relay and teamwork hybridization. Computational results reflect the sizeable solution quality improvement induced by hybridization, and assess the impact of each type of hybridization on the efficiency of the hybrid heuristic.     

Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration

This paper considers a parallel machine earliness/tardiness (ET) scheduling problem with different penalties under the effects of position based learning and linear and nonlinear deterioration. The problem has common due-date for all jobs, and effects of learning and deterioration are considered simultaneously. By the effects of learning we mean that the job processing time decreases along the sequence of partly similar jobs, and by the effects of deterioration we mean slowing performance or time increases along the sequence of jobs. This study shows that optimal solution for ET scheduling problem under effects of learning and deterioration is V-shape schedule under certain agreeable conditions. Furthermore, we design a mathematical model for the problem under study and algorithm and lower bound procedure to solve larger test problems. The algorithm can solve problems of 1000 jobs and four machines within 3 s on average. The performance of the algorithm is evaluated using results of the mathematical model.     

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.     

Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria

The problem of scheduling N jobs on M uniform parallel machines is studied. The objective is to minimize the mean tardiness or the weighted sum of tardiness with weights based on jobs, on periods or both. For the mean tardiness criteria in the preemptive case, this problem is NP-hard but good solutions can be calculated with a transportation problem algorithm. In the nonpreemptive case the problem is therefore NP-hard, except for the cases with equal job processing times or with job due dates equal to job processing times. No dominant heuristic is known in the general nonpreemptive case. The author has developed a heuristic to solve the nonpreemptive scheduling problem with unrelated job processing times. Initially, the algorithm calculates a basic solution. Next, it considers the interchanges of job subsets to equal processing time sum interchanging resources (i.e. a machine for a given period). This paper models the scheduling problem. It presents the heuristic and its result quality, solving 576 problems for 18 problem sizes. An application of school timetable scheduling illustrates the use of this heuristic.     

Two due date assignment problems with position-dependent processing time on a single-machine

The focus of this study is to analyze single-machine scheduling and due date assignment problems with position-dependent processing time. Two generally positional deterioration models and two frequent due date assignment methods are investigated. The objective functions include the cost of changing the due dates, the total cost of positional weight earliness, and the total cost of the discarded jobs that cannot be completed by their due dates. We conclude that the problems are polynomial time solvable. Significantly enough, after assessing the special case of each problem, this research found out that they can be optimally solved by lower order algorithms.     

Common due date assignment and scheduling with a rate-modifying activity to minimize the due date,earliness, tardiness,holding, and batch delivery cost

e consider a single-machine batch delivery scheduling and common due date assignment problem. In addition to making decisions on sequencing the jobs, determining the common due date, and scheduling job delivery, we consider the option of performing a rate-modifying activity on the machine. The processing time of a job scheduled after the rate-modifying activity decreases depending on a job-dependent factor. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a common due date for all the jobs, a location of the rate-modifying activity, and a delivery date for each job to minimize the sum of earliness, tardiness, holding, due date, and delivery cost. We provide some properties of the optimal schedule for the problem and present polynomial algorithms for some special cases.     

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.     

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.     

A differential evolution approach for the common due date early/tardy job scheduling problem

The problem of scheduling multiple jobs on a single machine so that they are completed by a common specified date is addressed in this paper. This type of scheduling set costs depend on whether a job is finished before (earliness) or after (tardiness) the specified due date. The objective is to minimize a summation of earliness and tardiness penalty costs. Minimizing these costs pushes the completion time of each job as close as possible to the due date. The use of differential evolution as the optimization heuristic to solve this problem is investigated in this paper. Computational experiments over multiple (280 in total) public benchmark problems with up to 1000 jobs to be scheduled show the effectiveness of the proposed approach. The results obtained are of high quality putting new upper bounds to 60% of the benchmark instances.     

A branch-and-bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties

This paper considers the problem of scheduling a single machine, in which the objective function is to minimize the weighted quadratic earliness and tardiness penalties and no machine idle time is allowed. We develop a branch and bound algorithm involving the implementation of lower and upper bounding procedures as well as some dominance rules. The lower bound is designed based on a lagrangian relaxation method and the upper bound includes two phases, one for constructing initial schedules and the other for improving them. Computational experiments on a set of randomly generated instances show that one of the proposed heuristics, used as an upper bound, has an average gap less than 1.3% for instances optimally solved. The results indicate that both the lower and upper bounds are very tight and the branch-and-bound algorithm is the first algorithm that is able to optimally solve problems with up to 30 jobs in a reasonable amount of time.     

Heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties

In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose several dispatching heuristics, and analyse their performance on a wide range of instances. The heuristics include simple and widely used scheduling rules, as well as adaptations of those rules to a quadratic objective function. We also propose heuristic procedures that specifically address both the earliness and the tardiness penalties, as well as the quadratic cost function. Several improvement procedures were also analysed. These procedures are applied as an improvement step, once the heuristics have generated a schedule.     

Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates

In this paper, we consider an identical parallel machine scheduling problem with sequence-dependent setup times and job release dates. An improved iterated greedy heuristic with a sinking temperature is presented to minimize the maximum lateness. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem data set. The experimental results show that the proposed heuristic outperforms the basic iterated greedy heuristic and the state-of-art algorithms on the same benchmark problem data set. It is believed that this improved approach will also be helpful for other applications.     

Scheduling unit length jobs with parallel nested machine processing set restrictions

This article explores the impact of restricting the machines upon which individual jobs may be scheduled. Even the simple case of a single stage of identical parallel machines cannot be solved to optimality in a reasonable time. We therefore focus on the case when job processing times are identical. In some applications the machine processing sets of jobs are structured in a nested fashion and do not partially overlap. We present efficient algorithms for solving this nested problem to optimality for each of the standard scheduling objective functions. In particular, an algorithm with constant running time minimises makespan on a fixed number of machines regardless of the number of jobs. Improvements in efficiency have been gained by attention to implementation issues, thus challenging the conventional approach to evaluating complexity.     

Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties

The present paper studies the single machine, no-idle-time scheduling problem with a weighted quadratic earliness and tardiness objective. We investigate the relationship between this problem and the assignment problem, and we derive two lower bounds and several heuristic procedures based on this relationship. Furthermore, the applicability of the time-indexed integer programming formulation is investigated. The results of a computational experiment on a set of randomly generated instances show (1) the high-quality results of the proposed heuristics, (2) the low optimality gap of one of the proposed lower bounds and (3) the applicability of the integer programming formulation to small and medium size cases of the problem.