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.     

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.     

A note on the flow time and the number of tardy jobs in stochastic open shops

In this note open shops with two machines are considered. The processing time of job j, j = 1, …, n, on machine 1 (2) is a random variable X_j (Y_j), which is exponentially distributed with rate γ (μ). If the completion time of job j is C_j, a waiting cost is incurred of g(C_j), where g is a function that is increasing concave. The preemptive policy that minimizes the total expected waiting cost E(Σg(C_j)) is determined. Two machine open shops with jobs that have random due dates are considered as well. For the case where the due dates D₁,…,D_n are exchangeable, the preemptive policy that minimizes the expected number of tardy jobs is determined.     

Minimizing the weighted number of late jobs in UET open shops

We consider a two-machine open shop problem where the jobs have release dates and due dates, and where all single operations have unit processing times. The goal is to minimize the weighted number of late jobs. We derive a polynomial time algorithm for this problem, thereby answering an open question posed in a recent paper by Brucker et al.This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.     

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 tardy jobs with due date assignment and capacity-constrained deliveries

We study a supply chain scheduling problem, where a common due date is assigned to all jobs and the number of jobs in delivery batches is constrained by the batch size. Our goal is to minimize the sum of the weighted number of tardy jobs, the due-date-assignment costs and the batch-delivery costs. We show that some well-known NPmathcal{NP}-hard problems reduce to our problem. Then we propose a pseudo-polynomial algorithm for the problem, establishing that it is NPmathcal{NP}-hard only in the ordinary sense. Finally, we convert the algorithm into an efficient fully polynomial time approximation scheme.     

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.     

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.     

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 new branch and bound algorithm for minimizing the weighted number of tardy jobs

In this paper, the problem of sequencing jobs on a single machine to minimize the weighted number of tardy jobs is considered. Some new dominances between jobs are proposed and studied. A new branch and bound algorithm that can solve large problems, e.g. 85 jobs, is presented.     

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.     

Scheduling linear deteriorating jobs to minimize the number of tardy jobs

In this paper a problem of scheduling a single machine under linear deterioration which aims at minimizing the number of tardy jobs is considered. According to our assumption, processing time of each job is dependent on its starting time based on a linear function where all the jobs have the same deterioration rate. It is proved that the problem is NP-hard; hence a branch and bound procedure and a heuristic algorithm with O(n ²) is proposed where the heuristic one is utilized for obtaining the upper bound of the B&B procedure. Computational results for 1,800 sample problems demonstrate that the B&B method can solve problems with 28 jobs quickly and in some other groups larger problems are also solved. Generally, B&B method can optimally solve 85% of the samples which shows high performance of the proposed method. Also it is shown that the average value of the ratio of optimal solution to the heuristic algorithm result with the objective ??(1 ? Ui) is at most 1.11 which is more efficient in comparison to other proposed algorithms in related studies in the literature.     

Minimizing total expected costs in the two-machine,stochastic flow shop

This paper analyzes the n-job, two-machine flowshop sequencing problem with job processing times following exponential distributions. Three sufficient conditions are derived for determining a job sequence which minimizes a total expected linear cost function. Stronger results are obtained for several special cases.     

带机器故障的两台机带权误工数排序问题

讨论机器带故障中断的两台平行机排序问题,工件加工时间均为单位时间,目标是极小化带权误工工件数.当转移时间t=0时给出了最优的算法.当t≠0时,给出了一个多项式时间的近似算法,并证明算法解与最优解至多相差一个带权误工数.     

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.     

Two-machine flowshop scheduling to minimize the number of tardy jobs

We consider the two-machine flowshop problem with the objective of minimizing the total number of tardy jobs. Since this problem is known to be strongly NP-hard, algorithms are described for four polynomially solvable special cases. In addition, several heuristic algorithms are developed to find optimal or near optimal schedules. Results of computational tests in solving problems up to 60 jobs are reported and directions for future research are provided.     

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.     

一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

针对延迟工件数最小的混合流水车间调度问题,给出了一种改进的模拟退火求解算法. 该算法首先给出一个启发式算法来获得初始解,然后用模拟退火算法对初始解改进. 通过交换工件在第一阶段的排序来获得一个新的解,采用最先空闲设备分配规则和先到先被加工规则,对工件在剩余各级的工序进行调度. 实验仿真表明算法是可行有效的.     

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.