Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time

This paper considers the problems of scheduling jobs on parallel identical machines where an optimal schedule is defined as one that gives the smallest maximum tardiness (or the minimum number of tardy jobs) among the set of schedules with optimal total flow-time (the sum of the completion times of all jobs). We show that these problems are unary NP-Hard, develop lower bounds for these two secondary criteria problems, and describe heuristic algorithms for their solution. Results of a computational study show that the proposed heuristic algorithms are quite effective and efficient in solving these hierarchical criteria scheduling problems.     

Minimizing the weighted number of tardy jobs on a single machine with release dates

In this paper, we describe an exact algorithm to minimize the weighted number of tardy jobs on a single machine with release dates. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate the proposed exact algorithm solves either weighted or unweighted problems. It solves the hardest problems to date. Indeed, it solves all previously unsolved instances. Its run time is the shortest to date.     

Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem

We study a static stochastic single machine scheduling problem in which jobs have random processing times with arbitrary distributions, due dates are known with certainty, and fixed individual penalties (or weights) are imposed on both early and tardy jobs. The objective is to find an optimal sequence that minimizes the expected total weighted number of early and tardy jobs. The general problem is NP-hard to solve; however, in this paper, we develop certain conditions under which the problem is solvable exactly. An efficient heuristic is also introduced to find a candidate for the optimal sequence of the general problem. Our illustrative examples and computational results demonstrate that the heuristic performs well in identifying either optimal sequences or good candidates with low errors. Furthermore, we show that special cases of the problem studied here reduce to some classical stochastic single machine scheduling problems including the problem of minimizing the expected weighted number of early jobs and the problem of minimizing the expected weighted number of tardy jobs which are both solvable by the proposed exact or heuristic methods.     

Minimizing makespan on a single machine subject to random breakdowns

We investigate optimal sequencing policies for the expected makespan problem with an unreliable machine, where jobs have to be reprocessed in their entirety if preemptions occur because of breakdowns. We identify a class of uptime distributions under which LPT minimizes expected makespan.     

Minimizing total tardiness on a single machine with unequal release dates

This study addresses the problem of minimizing total tardiness on a single machine with unequal release dates. Dominance properties established in previous literatures and herein are adopted to develop branch and bound and heuristic procedures. Computational experiments were conducted to evaluate the approaches. The results revealed that the branch and bound algorithm is efficient in solving hard problems and easy problems that involve up to 50 and 500 jobs, respectively. The computational effectiveness of the heuristic is also reported.     

Minimizing number of tardy jobs on a batch processing machine with incompatible job families

In this paper we consider the problem of minimizing number of tardy jobs on a single batch processing machine. The batch processing machine is capable of processing up to B jobs simultaneously as a batch. We are given a set of n jobs which can be partitioned into m incompatible families such that the processing times of all jobs belonging to the same family are equal and jobs of different families cannot be processed together. We show that this problem is NP-hard and present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also show that when the jobs of a family have a common due date the problem can be solved by a pseudo-polynomial time procedure.     

A tabu search approach for the single machine mean tardiness problem

In this paper, a tabu search approach is proposed for solving the single machine mean tardiness scheduling problem. Simulation experiment results obtained from the tabu search approach and three other heuristics are compared. Although computation time is increased, the results indicate that the proposed approach provides a much better solution than the other three approaches.     

Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs

Motivated by just-in-time manufacturing, we consider a single machine scheduling problem with dual criteria, i.e., the minimization of the total weighted earliness subject to minimum number of tardy jobs. We discuss several dominance properties of optimal solutions. We then develop a heuristic algorithm with time complexity O(n³) and a branch and bound algorithm to solve the problem. The computational experiments show that the heuristic algorithm is effective in terms of solution quality in many instances while the branch and bound algorithm is efficient for medium-size problems.     

Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due date constraints

The relocation problem addressed in this paper is to determine a reconstruction sequence for a set of old buildings, under a limited budget, such that there is adequate temporary space to house the residents decanted during rehabilitation. It can be regarded as a resource-constrained scheduling problem where there is a set of jobs to be processed on a single machine. Each job demands a number of resources for processing and returns probably a different number of resources on its completion. Given a number of initial resources, the problem seeks to determine if there is a feasible sequence for the successful processing of all the jobs. Two generalizations of the relocation problem in the context of single machine scheduling with due date constraints are studied in this paper. The first problem is to minimize the weighted number of tardy jobs under a common due date. We show that it is NP-hard even when all the jobs have the same tardy weight and the same resource requirement. A dynamic programming algorithm with pseudo-polynomial computational time is proposed for the general case. In the second problem, the objective is to minimize the maximum tardiness when each job is associated with an individual due date. We prove that it is strongly NP-hard. We also propose a pseudo-polynomial time dynamic programming algorithm for the case where the number of possible due dates is predetermined.     

Single machine scheduling to minimize weighted earliness subject to no tardy jobs

This paper considers the single machine scheduling problem where the objective is to minimize the total weighted earliness subject to no tardy jobs. Known results for a well researched single machine scheduling problem where the objective is to minimize the weighted completion time subject to no tardy jobs have been used in analyzing this problem. Several important results are proved and both exact and approximate methods are developed to solve this problem.     

Minimizing the weighted number of tardy jobs on parallel processors

We present a branch-and-bound algorithm to minimize the weighted number of tardy jobs on either identical or non-identical processors. Bounds come from a surrogate relaxation resulting in a multiple-choice knapsack. Extensive computational experiments indicate problems with 400 jobs and several machines can be solved quickly. The results also indicate what parameters affect solution difficulty for this algorithmic approach.     

A note on the single machine scheduling to minimize the number of tardy jobs with deadlines

It is known that the single machine scheduling problem of minimizing the number of tardy jobs is polynomially solvable. However, it becomes NP-hard if each job has a deadline. Recently, Huo et al. solved some special cases by a backwards scheduling approach. In this note we present a dual approach—forwards greedy algorithms which may have better running time. For example, in the case that the due dates, deadlines, and processing times are agreeable, the running time of the backwards scheduling algorithm is O(n²)$O(n^2)$, while that of the forwards algorithm is O(nlogn)$O(n\log n)$.     

Minimizing mean squared deviation of completion times with maximum tardiness constraint

We consider a nonpreemptive single-machine scheduling problem to minimize mean squared deviation of job completion times about a common due date with maximum tardiness constraint (MSD/T_max problem), where the common due date is large enough so that it does not constrain the minimization of MSD.The MSD/T_max problem is classified into three cases according to the value of maximum allowable tardiness Δ: Δ-unconstrained, Δ-constrained and tightly Δ-constrained cases. It is shown that the Δ-unconstrained MSD/T_max problem is equivalent to the unconstrained MSD problem and that the tightly Δ-constrained MSD/T_max problem with common due date d is equivalent to the tightly constrained MSD problem with common due date Δ. We also provide bounds to decide when the MSD/T_max problem is Δ-unconstrained or Δ-constrained. Then a solution procedure to the MSD/T_max problem is presented with several examples.     

Minimizing the number of machines for minimum length schedules

In this paper, we present a new objective function for scheduling on parallel machines: minimizing the number of machines for schedules of minimum length. We study its complexity and we prove the NP-completeness of this problem, even if there is no precedences or for unitary execution times. We propose several polynomial algorithms for various particular cases.     

Scheduling uniform parallel machines subject to a secondary resource to minimize the number of tardy jobs

This research investigates the problem of scheduling jobs on a set of parallel machines where the speed of the machines depends on the allocation of a secondary resource. The secondary resource is fixed in quantity and is to be allocated to the machines at the start of the schedule. The scheduling objective is to minimize the number of tardy jobs. Two versions of the problem are analyzed. The first version assumes that the jobs are pre-assigned to the machines, while the second one takes into consideration the task of assigning jobs to the machines. The paper proposes an Integer Programming formulation to solve the first case and a set of heuristics for the second.     

Minimizing the expected weighted number of tardy jobs in stochastic flow shops

This paper is devoted to two types of stochastic scheduling problems, one involving a single machine and the other involving a flow shop consisting of an arbitrary number of machines. In both problem types, all jobs to be processed have due dates, and the objective is to find a job sequence that minimizes the expected weighted number of tardy jobs. For the single-machine case, sufficient optimality conditions for job sequences are derived for various choices of due date and processing time distributions. For the case of a flow shop with an arbitrary number of machines and identically distributed due dates for all jobs, we prove the following intuitively appealing results: (i) when all jobs have the same processing time distributions, the expected weighted number of tardy jobs is minimized by sequencing the jobs in decreasing order of the weights, (ii) when all weights are equal, the jobs should be sequenced according to an increasing stochastic ordering of the processing time distributions.     

On the single machine total tardiness problem

In this paper we study the single machine total tardiness problem. We first identify some optimality properties based on which a special case with a given number of distinct due dates is proved polynomially solvable. The results are then extended to the case with release dates.     

Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint

In this paper, we consider the problem of minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that under a mild assumption, this problem can be solved by solving a linearly constrained convex univariate minimization problem. Finally, the superior efficiency of the new approach compared to the known semidefinite relaxation and a known approach from the literature is demonstrated by solving several randomly generated test problems.     

A heuristic for single machine scheduling with early and tardy costs

The problem of scheduling jobs with distinct ready times and due dates in a single machine to minimise the total earliness and tardiness penalties is considered. A constructive heuristic, which determines the sequence of jobs and simultaneously inserts idle times, is proposed. Adjacent pairwise interchange is then applied to the schedule obtained. For problems involving at most 12 jobs the heuristic solutions are compared to optimal solutions. For larger problems with up to 80 jobs the heuristic is tested against a local search based on pairwise interchanges and four dispatching rules presented in the literature. In each case, idle times are optimally inserted.     

A decomposition algorithm for the single machine total tardiness problem

The problem of sequencing jobs on a single machine to minimize total tardiness is considered. An algorithm, which decomposes the problem into subproblems which are then solved by dynamic programming when they are sufficiently small, is presented and is tested on problems with up to 100 jobs.