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.     

Minimum weighted number of tardy jobs on an m-machine flow-shop with a critical machine

We study a flow-shop problem, where each of the jobs is limited to no more than two operations. One of these operations is common for all the jobs, and is performed on the same (”critical”) machine. Reflecting many applications, jobs are assumed to be processed in blocks on the critical machine. All the jobs share a common due-date, and the objective is minimum weighted number of tardy jobs. We prove that the problem is NP-hard. Then we formulate the problem as an integer program, and introduce a pseudo-polynomial dynamic programming algorithm, proving that the problem is NP-hard in the ordinary sense. We also propose an efficient heuristic, which is shown numerically to produce very close-to-optimal schedules. Finally, we show that the special case of identical weights is polynomially solvable.     

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)$.     

Single-machine scheduling to minimize earliness and number of tardy jobs

This paper considers the problem of assigning a common due-date to a set of simultaneously available jobs and sequencing them on a single machine. The objective is to determine the optimal combination of the common due-date and job sequence that minimizes a cost function based on the assigned due-date, job earliness values, and number of tardy jobs. It is shown that the optimal due-date coincides with one of the job completion times. Conditions are derived to determine the optimal number of nontardy jobs. It is also shown that the optimal job sequence is one in which the nontardy jobs are arranged in nonincreasing order of processing times. An efficient algorithm of O(n logn) time complexity to find the optimal solution is presented and an illustrative example is provided. Finally, several extensions of the model are discussed.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG0036424. The authors are thankful to two anonymous referees for their constructive comments.     

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.     

Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness

Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time p_j, a due date d_j and a weight w_j. We consider bi-criteria scheduling problems involving the maximum weighted tardiness and the number of tardy jobs. We give NP-hardness proofs for the scheduling problems when either one of the two criteria is the primary criterion and the other one is the secondary criterion. These results answer two open questions posed by Lee and Vairaktarakis in 1993. We consider complexity relationships between the various problems, give polynomial-time algorithms for some special cases, and propose fast heuristics for the general case. The effectiveness of the heuristics is measured by empirical study. Our results show that one heuristic performs extremely well compared to optimal solutions.     

New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs

We consider the bicriteria scheduling problem of minimizing the number of tardy jobs and average flowtime on a single machine. This problem, which is known to be NP-hard, is important in practice, as the former criterion conveys the customer’s position, and the latter reflects the manufacturer’s perspective in the supply chain. We propose four new heuristics to solve this multiobjective scheduling problem. Two of these heuristics are constructive algorithms based on beam search methodology. The other two are metaheuristic approaches using a genetic algorithm and tabu-search. Our computational experiments indicate that the proposed beam search heuristics find efficient schedules optimally in most cases and perform better than the existing heuristics in the literature.     

Learning effect and deteriorating jobs in the single machine scheduling problems

This paper studies the single machine scheduling problems with learning effect and deteriorating jobs simultaneously. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, the makespan, the total completion time and the sum of the k$k$th power of completion times minimization problems remain polynomially solvable, respectively. But for the following objective functions: the total weighted completion time and the maximum lateness, this paper proves that the shortest weighted processing time first (WSPT) rule and the earliest due-date first (EDD) rule can construct the optimal sequence under some special cases, respectively.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

Single machine quadratic penalty function scheduling with deteriorating jobs and group technology

This paper considers single machine scheduling problems with group technology (GT) and deteriorating jobs. We consider the case of jobs whose processing times are a simple linear function of their starting time. The two objectives of scheduling problems are to minimize the weighted sum of squared completion times and the weighted sum of squared waiting times, respectively. We also provide polynomial time algorithms to solve these problems.     

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.     

Single machine common flow allowance scheduling with deteriorating jobs and a rate-modifying activity

We study a single machine slack due date assignment (usually referred to as SLK) scheduling problem with deteriorating jobs and a rate-modifying activity. The deterioration effect manifest such that the job processing time is a function of its starting time in a sequence. The rate-modifying activity is an activity that changes the processing rate of machine, i.e., the machine performs a rate-modifying activity. Hence the actual processing time of a job is a variable, which depends not only on its starting time in a sequence but also on whether it is scheduled before or after a rate-modifying activity. The goal is to schedule the rate-modifying activity, the optimal common flow allowance and the sequence of jobs to minimize the total earliness, the total tardiness and the common flow allowance cost. We show that the problem remains polynomially solvable under the proposed model.     

Single machine batch scheduling to minimize the weighted number of late jobs

The single machine batch scheduling problem to minimize the weighted number of late jobs is studied. In this problem,n jobs have to be processed on a single machine. Each job has a processing time, a due date and a weight. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of this batch is processed. The completion time of each job in the batch coincides with the completion time of the last job in this batch. A job is late if it is completed after its due date. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find a schedule which minimizes the weighted number of late jobs. This problem isNP-hard even if all due dates are equal. For the general case, we present a dynamic programming algorithm which solves the problem with equal weights inO(n ³) time. We formulate a certain scaled problem and show that our dynamic programming algorithm applied to this scaled problem provides a fully polynomial approximation scheme for the original problem. Each algorithm of this scheme has a time requirement ofO(n ³/ +n ³ logn). A side result is anO(n logn) algorithm for the problem of minimizing the maximum weight of late jobs.Supported by INTAS Project 93-257.     

A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates

In this paper we consider the scheduling problem of minimizing the weighted number of late jobs on a single machine (1|_rj|∑_wjUj)$\left(1|r_j|\sum w_j{U}_j\right)$. A branch-and-check algorithm is proposed, where a relaxed integer programming formulation is solved by branch-and-bound and infeasible solutions are cut off using infeasibility cuts. We suggest two ways to generate cuts. First, tightened “no-good” cuts are derived using a modification of the algorithm by Carlier (1982, EJOR, v.11, 42–47) which was developed for the problem of minimizing maximum lateness on a single machine. Secondly we show how to create cuts by using constraint propagation. The proposed algorithm is implemented in the Mosel modelling and optimization language. Computational experiments on instances with up to 140 jobs are reported. A comparison is presented with the exact approach of Péridy at al. (2003, EJOR, v.148, 591–603).     

A faster algorithm for a due date assignment problem with tardy jobs

The single-machine due date assignment problem with the weighted number of tardy jobs objective, (the TWNTD problem), and its generalization with resource allocation decisions and controllable job processing times have been solved in O(n⁴) time by formulating and solving a series of assignment problems. In this note, a faster O(n²) dynamic programming algorithm is proposed for the TWNTD problem and for its controllable processing times generalization in the case of a convex resource consumption function.     

Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains

In this paper, an integrated due date assignment and production and batch delivery scheduling problem for make-to-order production system and multiple customers is addressed. Consider a supply chain scheduling problem in which n orders (jobs) have to be scheduled on a single machine and delivered to K customers or to other machines for further processing in batches. A common due date is assigned to all the jobs of each customer and the number of jobs in delivery batches is constrained by the batch size. The objective is to minimize the sum of the total weighted number of tardy jobs, the total due date assignment costs and the total batch delivery costs. The problem is NP-hard. We formulate the problem as an Integer Programming (IP) model. Also, in this paper, a Heuristic Algorithm (HA) and a Branch and Bound (B&B) method for solving this problem are presented. Computational tests are used to demonstrate the efficiency of the developed methods.