Single machine scheduling with controllable processing times to minimize total tardiness and earliness

In most deterministic scheduling problems job processing times are considered as invariable and known in advance. Single machine scheduling problem with controllable processing times with no inserted idle time is presented in this study. Job processing times are controllable to some extent that they can be reduced or increased, up to a certain limit, at a cost proportional to the reduction or increase. In this study, our objective is determining a set of compression/expansion of processing times in addition to a sequence of jobs simultaneously, so that total tardiness and earliness are minimized. A mathematical model is proposed firstly and afterward a net benefit compression–net benefit expansion (NBC–NBE) heuristic is presented so as to acquire a set of amounts of compression and expansion of jobs processing times in a given sequence. Three heuristic techniques in small problems and in medium-to-large instances two meta-heuristic approaches, as effective local search methods, as well as these heuristics are employed to solve test examples. The single machine total tardiness problem (SMTTP) is already NP-hard, so the considered problem is NP-hard obviously. The computational experiments demonstrate that our proposed heuristic is efficient approach for such just-in-time (JIT) problem, especially equipped with competent heuristics.     

Minimizing total tardiness on a single machine with controllable processing times

The concept of time-cost trade-off is commonly considered in PERT/CPM, but it is seldom considered in the scheduling area. Such concept implies that the processing times of jobs are controllable by increasing or decreasing the available resources, such as manpower and equipment. In this paper, we focus on the single machine total tardiness problem with controllable processing times. First, a mixed-integer programming (MIP) model is formulated to find the optimal solution. Then, we propose both a linear programming model and a net benefit of compression (NBC) algorithm to obtain a set of optimal amounts of compression for a given sequence. To solve medium- to large-size problem instances, we develop a heuristic based on the NBC algorithm. To verify the proposed heuristic, the MIP model is used as a comparison for small-size problem instances, whereas for medium- to large-size instances the variable neighborhood search, a useful local search method, is employed. Computational results show that the proposed heuristic has a good performance.     

A heuristic algorithm to minimize total weighted tardiness on a single machine with release times

This paper attempts to solve a single machine‐scheduling problem, in which the objective function is to minimize the total weighted tardiness with different release dates of jobs. To address this scheduling problem, a heuristic scheduling algorithm is presented. A mathematical programming formulation is also formulated to validate the performance of the heuristic scheduling algorithm proposed herein. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. Overall, this algorithm can find the optimal solutions for 2200 out of 2400 randomly generated problems (91.67%). For the most complicated 20 job cases, it requires less than 0.0016 s to obtain an ultimate or even optimal solution. This heuristic scheduling algorithm can therefore efficiently solve this kind of problem.     

A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup. Firstly, a mathematical model is given to describe the problem formally. Since the problem is NP-hard, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. Initial solution for the GVNS algorithm is obtained by using a constructive heuristic that is widely used in the literature for the problem. The proposed algorithm is tested on 120 benchmark instances. The results show that 37 out of 120 best known solutions in the literature are improved while 64 instances are solved equally. Next, the GVNS algorithm is applied to single machine scheduling problem with sequence dependent setup times to minimize the total tardiness problem without changing any implementation issues and the parameters of the GVNS algorithm. For this problem, 64 test instances are solved varying from small to large sizes. Among these 64 instances, 35 instances are solved to the optimality, 16 instances' best-known results are improved, and 6 instances are solved equally compared to the best-known results. Hence, it can be concluded that the GVNS algorithm is an effective, efficient and a robust algorithm for minimizing tardiness on a single machine in the presence of setup times.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

Single machine scheduling problem with interval processing times to minimize mean weighted completion time

The single resource scheduling problem is commonly applicable in practice not only when there is a single resource but also in some multiple-resource production systems where only one of the resources is bottle neck. Thus, the single resource (machine) scheduling problem has been widely addressed in the scheduling literature. In this paper, the single machine scheduling problem with uncertain and interval processing times is addressed. The objective is to minimize mean weighted completion time. The problem has been addressed in the literature and efficient heuristics have been presented. In this paper, some new polynomial time heuristics, utilizing the bounds of processing times, are proposed. The proposed and existing heuristics are compared by extensive computational experiments. The conducted experiments include a generalized simulation environment and several additional representative distributions in addition to the restricted experiments used in the literature. The results indicate that the proposed heuristics perform significantly better than the existing heuristics. Specifically, the best performing proposed heuristic reduces the error of the best existing heuristic in the literature by more than 75% while the computational time of the best performing proposed heuristic is less than that of the best existing heuristic. Moreover, the absolute error of the best performing heuristic is only about 1% of the optimal solution. Having a very small absolute error along with a negligible computational time indicates the superiority of the proposed heuristics.     

Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem

In this paper, we consider the single machine scheduling problem with weighted quadratic tardiness costs. Several efficient dispatching rules are proposed. These include existing heuristics for the linear problem, as well as procedures suitably adapted to the quadratic objective function. Also, both forward and backward scheduling procedures are considered.The computational results show that the heuristics that specifically take into account the quadratic objective significantly outperform their linear counterparts. Also, the backward scheduling approach proves to be superior, and the difference in performance is even more noticeable for the harder instances.The best of the backward scheduling heuristics is both quite efficient and effective. Indeed, this procedure can quickly generate a schedule even for large instances. Also, its relative deviation from the optimum is usually rather low, and it performs adequately even for the more difficult instances.     

A heuristic for job shop scheduling to minimize total weighted tardiness

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.     

Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times

Job scheduling has always been a challenging task in modern manufacturing and the most real life scheduling problems which involves multi-criteria and multi-machine environments. In this research our direction is largely motivated by the adoption of the Just-In-Time (JIT) philosophy in parallel machines system, where processing times of jobs are controllable. The goal of this paper is to minimize total weighted tardiness and earliness besides jobs compressing and expanding costs, depending on the amount of compression/expansion as well as maximum completion time called makespan simultaneously. Jobs due dates are distinct and no inserted idle time is allowed after starting machine processing. Also each machine is capable of processing only some predetermined jobs and operations with probably different speeds. A Mixed Integer Programming (MIP) model is proposed to formulate such a problem and is solved optimally in small size instances. A Parallel Net Benefit Compression-Net Benefit Expansion (PNBC–NBE) heuristic is then presented to acquire the optimal jobs set amount of compression and expansion processing times in a given sequence. To solve medium-to-large size cases, a proposed heuristic, two meta-heuristics and a hybrid technique are also employed. Experimental results demonstrate that our hybrid procedure is a proficient method and could efficiently solve such complicated problems.     

Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.     

An O(n 2 ) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness

In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n²) time algorithm to solve the problem.     

A population-based variable neighborhood search for the single machine total weighted tardiness problem

This paper investigates the single machine total weighted tardiness problem, in which a set of independent jobs with distinct processing times, weights, and due dates are to be scheduled on a single machine to minimize the sum of weighted tardiness of all jobs. This problem is known to be strongly NP-hard, and thus provides a challenging area for metaheuristics. A population-based variable neighborhood search (PVNS) algorithm is developed to solve it. This algorithm differs from the basic variable neighborhood search (VNS). First, the PVNS consists of a number of iterations of the basic VNS, and in each iteration a population of solutions is used to simultaneously generate multiple trial solutions in a neighborhood so as to improve the search diversification. Second, the PVNS adopts a combination of path-relinking, variable depth search and tabu search to act as the local search procedure so as to improve the search intensification. Computational experiments show that the proposed PVNS algorithm can obtain the optimal or best known solutions within a reasonable computation time for all standard benchmark problem instances from the literature.     

An efficient memetic algorithm for total weighted tardiness minimization in a single machine with setups

The single machine scheduling problem with sequence-dependent setup times with the objective of minimizing the total weighted tardiness is a challenging problem due to its complexity, and has a huge number of applications in real production environments. In this paper, we propose a memetic algorithm that combines and extends several ideas from the literature, including a crossover operator that respects both the absolute and relative position of the tasks, a replacement strategy that improves the diversity of the population, and an effective but computationally expensive neighborhood structure. We propose a new decomposition of this neighborhood that can be used by a variable neighborhood descent framework, and also some speed-up methods for evaluating the neighbors. In this way we can obtain competitive running times. We conduct an experimental study to analyze the proposed algorithm and prove that it is significantly better than the state-of-the-art in standard benchmarks.     

Metaheuristics for the single machine weighted quadratic tardiness scheduling problem

This paper considers the single machine scheduling problem with weighted quadratic tardiness costs. Three metaheuristics are presented, namely iterated local search, variable greedy and steady-state genetic algorithm procedures. These address a gap in the existing literature, which includes branch-and-bound algorithms (which can provide optimal solutions for small problems only) and dispatching rules (which are efficient and capable of providing adequate solutions for even quite large instances). A simple local search procedure which incorporates problem specific information is also proposed.The computational results show that the proposed metaheuristics clearly outperform the best of the existing procedures. Also, they provide an optimal solution for all (or nearly all, in the case of the variable greedy heuristic) the smaller size problems. The metaheuristics are quite close in what regards solution quality. Nevertheless, the iterated local search method provides the best solution, though at the expense of additional computational time. The exact opposite is true for the variable greedy procedure, while the genetic algorithm is a good all-around performer.     

Single machine scheduling problems with resource dependent release times

We consider two single machine scheduling problems with resource dependent release times that can be controlled by a non-increasing convex resource consumption function. In the first problem, the objective is to minimize the total resource consumption with a constraint on the sum of job completion times. We show that a recognition version of the problem is NP-complete. In the second problem, the objective is to minimize the weighted total resource consumption and sum of job completion times with an initial release time greater than the total processing times. We provide some optimality conditions and show that the problem is polynomially solvable.     

Single machine batch scheduling to minimize total completion time and resource consumption costs

In this paper we study the single-machine batch scheduling problem under batch availability, where both setup and job processing times are controllable by allocating a continuously divisible nonrenewable resource. Under batch availability a set of jobs is processed contiguously and completed together, when the processing of the last job in the batch is finished. We present polynomial time algorithms to find the job sequence, the partition of the job sequence into batches and the resource allocation, which minimize the total completion time or the total production cost (inventory plus resource costs).     

Minimizing the weighted sum of squared tardiness on a single machine

This paper considers a problem in which there is a set of jobs to be sequenced on a single machine. Each job has a weight and the objective is to sequence the jobs to minimize total weighted squared tardiness. A branch-and-bound algorithm is developed for optimally solving the problem. Several dominance conditions are presented for possible inclusion in the branch-and-bound algorithm. The dominance conditions are included in the branch-and-bound algorithm, which is tested on randomly generated problems of various numbers of jobs, due date tightness and due date ranges. The results show that the dominance conditions dramatically improve the efficiency of the branch-and-bound algorithm.     

Robust scheduling on a single machine to minimize total flow time

In a real-world manufacturing environment featuring a variety of uncertainties, production schedules for manufacturing systems often cannot be executed exactly as they are developed. In these environments, schedule robustness that guarantees the best worst-case performance is a more appropriate criterion in developing schedules, although most existing studies have developed optimal schedules with respect to a deterministic or stochastic scheduling model. This study concerns robust single machine scheduling with uncertain job processing times and sequence-dependent family setup times explicitly represented by interval data. The objective is to obtain robust sequences of job families and jobs within each family that minimize the absolute deviation of total flow time from the optimal solution under the worst-case scenario. We prove that the robust single machine scheduling problem of interest is NP-hard. This problem is reformulated as a robust constrained shortest path problem and solved by a simulated annealing-based algorithmic framework that embeds a generalized label correcting method. The results of numerical experiments demonstrate that the proposed heuristic is effective and efficient for determining robust schedules. In addition, we explore the impact of degree of uncertainty on the performance measures and examine the tradeoff between robustness and optimality.