A tabu method for a two-agent single-machine scheduling with deterioration jobs

In recent 10 years, the multi-agent idea applied in scheduling issues has received continuing attention. However, the study of the multi-agent scheduling with deteriorating jobs is relatively limited. In light of this, this paper deliberates upon a two-agent single-machine scheduling problem with deteriorating jobs. Taking the proposed model, the actual processing time of a job from both the first agent and the second agent is modeled as a linearly increasing function of its starting time. The goal of this paper is to minimize the total weighted number of tardy jobs of the first agent subject to the condition that the maximum lateness of the second agent is allowed to have an upper bound. The complexity of the model concerned in the paper is claimed as an NP-hard one. Following that, several dominance rules and a lower bound are proposed to be applied in a branch-and-bound algorithm for the optimal solution, and a tabu algorithm is applied to find near-optimal solutions for the problem. The simulation results obtained from all the proposed algorithms are also reported.     

Two-machine flowshop scheduling with three-operation jobs subject to a fixed job sequence

This paper studies the problem of scheduling three-operation jobs in a two-machine flowshop subject to a predetermined job processing sequence. Each job has two preassigned operations, which are to be performed on their respective dedicated machines, and a flexible operation, which may be processed on either of the two machines subject to the processing order as specified. Five standard objective functions, including the makespan, the maximum lateness, the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs are considered. We show that the studied problem for either of the five considered objective functions is ordinary NP-hard, even if the processing times of the preassigned operations are zero for all jobs. A pseudo-polynomial time dynamic programming framework, coupled with brief numerical experiments, is then developed for all the addressed performance metrics with different run times.     

Scheduling n jobs on one machine to minimize the maximum tardiness with minimum number

The “one machine” scheduling problem is considered with the dual objective of minimizing the maximum tardiness with minimum number of tardy jobs. A simple procedure is introduced to obtain an optimal schedule with minimum “maximum tardiness” when the set of nontardy jobs is specified. A branch and bound algorithm is presented to obtain the optimal schedule that minimizes the maximum tardiness with minimum number of tardy jobs. A condition is also given to identify an initial set of early jobs. Several theorems are formulated and proved in order to justify the elimination of much branching.     

Unary NP-hardness of minimizing the number of tardy jobs with deadlines

For single machine scheduling to minimize the number of tardy jobs with deadlines, Lawler showed in 1983 that the problem is binary NP-hard. But the exact complexity (unary NP-hard or pseudo-polynomial-time solvability) is a long- standing open problem. We show in this paper that the problem is unary NP-hard. Our research also implies that the scheduling problem for finding an optimal schedule to minimize the number of tardy jobs that also satisfies the restriction of deadlines is unary NP-hard. As a consequence, some multi-agent scheduling problems related to minimizing the number of tardy jobs and maximum lateness are unary NP-hard.     

Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times

In various real life scheduling systems job processing times vary according to the number of jobs previously processed. The vast majority of studies assume a restrictive functional form to describe job processing times. In this note, we address a scheduling problem with the most general job processing time functions. The machine setting assumed is an m-machine proportionate flowshop, and the objective function is minimum number of tardy jobs. We show that the problem can be formulated as a bottleneck assignment problem with a maximum cardinality constraint. An efficient polynomial time (O(n⁴ log n)) solution is introduced.     

A heuristic procedure to minimize number of tardy jobs and total tardiness in single machine scheduling

Moore has suggested an optimizing algorithm for minimizing the number of tardy jobs in single machine scheduling. This article explores the possibility of modifying the Moore's algorithm so that total tardiness is minimized while keeping the number of tardy jobs minimum. A heuristic procedure based on the Moore's original algorithm is presented and its performance is evaluated. A simple extension of the algorithm to parallel machine scheduling is also provided.     

Single-machine scheduling with trade-off between number of tardy jobs and compression cost

We consider a single-machine scheduling problem, in which the job processing times are controllable or compressible. The performance criteria are the compression cost and the number of tardy jobs. For the problem, where no tardy jobs are allowed and the objective is to minimize the total compression cost, we present a strongly polynomial time algorithm. For the problem to construct the trade-off curve between the number of tardy jobs and the maximum compression cost, we present a polynomial time algorithm. Furthermore, we extend the problem to the case of discrete controllable processing times, where the processing time of a job can only take one of several given discrete values. We show that even some special cases of the discrete controllable version with the objective of minimizing the total compression cost are NP-hard, but the general case is solvable in pseudo-polynomial time. Moreover, we present a strongly polynomial time algorithm to construct the trade-off curve between the number of tardy jobs and the maximum compression cost for the discrete controllable version. This research was supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of the MOE, China, and the National Natural Science Foundation of China (10271110). The third author was supported in part by The Hong Kong Polytechnic University under a grant from the ASD in China Business Services.     

Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance

This research focuses on the problem of scheduling jobs on a single machine that requires periodic maintenance with the objective of minimizing the number of tardy jobs. We present a two-phase heuristic algorithm in which an initial solution is obtained first with a method modified from Moore's algorithm for the problem without maintenance and then the solution is improved in the second phase. Performance of the proposed heuristic algorithm is evaluated through computational experiments on randomly generated problem instances and results show that the heuristic gives solutions close to those obtained from a commercial integer programming solver in much shorter time and works better than an existing heuristic algorithm in terms of the solution quality.     

Some scheduling problems with deteriorating jobs and learning effects

Although scheduling with deteriorating jobs and learning effect has been widely investigated, scheduling research has seldom considered the two phenomena simultaneously. However, job deterioration and learning co-exist in many realistic scheduling situations. In this paper, we introduce a new scheduling model in which both job deterioration and learning exist simultaneously. The actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled position. For the single-machine case, we derive polynomial-time optimal solutions for the problems to minimize makespan and total completion time. In addition, we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain agreeable conditions. For the case of an m-machine permutation flowshop, we present polynomial-time optimal solutions for some special cases of the problems to minimize makespan and total completion time.     

Relocation scheduling subject to fixed processing sequences

This study addresses a relocation scheduling problem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in \(O(n_1n_2(n_1+n_2))\) time, where \(n_1\) and \(n_2\) are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in \(O(n_1n_2)\) time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processing length is solvable in \(O(n_1n_2\min \{n_1,n_2\})\) time. The studied problem for the minimization of number of tardy jobs is solvable in \(O(n^2_1n^2_2(n_1+n_2)^2)\) time. The solvability of the common-processing-time problems can be generalized to the m-machine cases, where \(m\ge 3\).     

Minimizing the number of tardy jobs under piecewise-linear deterioration

In this paper, we consider a single machine scheduling problem with piecewise-linear deterioration where its objective is to minimize the number of tardy jobs, in which the processing time of each job depends on its starting time where all the jobs have a specific deterioration rate. The problem is known to be NP-hard; therefore a Branch and Bound algorithm and a heuristic algorithm with O(n²) are proposed. The proposed heuristic algorithm has been utilized for solving large scale problems and upper bound of the B&B algorithm. Computational experiments on 1840 problems demonstrate that the Branch and Bound procedure can solve problems with 28 jobs and 85.4% of all the sample problems optimally showing the high capability of the proposed procedure. Also it is shown that the average value of the ratio of optimal answer to the heuristic algorithm result with the objective ∑(1-_Ui)$\sum (1-U_i)$ is at last 1.08 which is more efficient in contrast to other proposed algorithms in related studies in the literature. According to high efficacy of the heuristic algorithm, large scale samples are also being solved and the results are presented. A specific form of this problem is also being considered and it is proven that the B&B procedure can handle problems with more jobs even up to 44 jobs.     

Single-machine scheduling problems with deteriorating jobs and learning effects

In this paper, we introduce a new scheduling model in which deteriorating jobs and learning effect are both considered simultaneously. By deterioration and the learning effect, we mean that the actual processing time of a job depends not only on the processing time of the jobs already processed but also on its scheduled position. For the single-machine case, we show that the problems of makespan, total completion time and the sum of the quadratic job completion times remain polynomially solvable, respectively. In addition,we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain conditions.     

An Exact Method to Minimize the Number of Tardy Jobs in Single Machine Scheduling

This paper considers the problem of scheduling n jobs on a single machine to minimize the number of tardy (or late) jobs. Each job has a release date, a processing time and a due date. The general case with non-equal release dates and different due dates is considered. Using new and efficient lower bounds and several dominance rules, a branch and bound scheme is proposed based on the definition of a master sequence, i.e. a sequence containing at least one optimal sequence. With this procedure, 95% of 140-job instances are optimally solved in a maximum of one-hour CPU time.     

Single-machine scheduling with a variable maintenance activity

We consider the problem of scheduling a maintenance activity and jobs on a single machine, where the maintenance activity must start before a given deadline and the maintenance duration increases with its starting time. We provide polynomial-time algorithms to solve the problems to minimize the makespan, sum of completion times, maximum lateness, and number of tardy jobs.     

Energy optimal schedules for jobs with multiple active intervals

In this paper, we study the scheduling problem of jobs with multiple active intervals. Each job in the problem instance has disjoint active time intervals where it can be executed and a workload characterized by the required number of CPU cycles. Previously, people studied multiple interval job scheduling problem where each job must be assigned enough CPU cycles in one of its active intervals. We study a different practical version where the partial work done by the end of an interval remains valid and each job is considered finished if total CPU cycles assigned to it in all its active intervals reach the requirement. The goal is to find a feasible schedule that minimizes energy consumption. By adapting the algorithm for single interval jobs proposed in Yao, Demers and Shenker (1995) [1], one can still obtain an optimal schedule. However, the two phases in that algorithm (critical interval finding and scheduling the critical interval) can no longer be carried out directly. We present polynomial time algorithms to solve the two phases for jobs with multiple active intervals and therefore can still compute the optimal schedule in polynomial time.     

Maximizing the throughput of parallel jobs on hypercubes

We study a problem of scheduling n independent parallel jobs on hypercubes. A parallel job is required to be scheduled on a subcube of processors. All jobs are available at the beginning, each of which is associated with a due date. The objective is to maximize the total number of early jobs. We provide an optimal polynomial time algorithm for the unit processing time job system.     

Scheduling for on-time completion in job shops using feasibility function

This article focuses on job shop type manufacturing systems where a high variety of products of different volumes are requested to be produce on a tight due date. The feasibility function (FF) is addressed in this article to schedule jobs in multi-machine random job shop, where the purpose is to minimize unit penalty by achieving a balance between the number of tardy and early jobs, and reducing the difference between the maximum and the minimum lateness of jobs. A job shop simulation model based on multi-agent architecture developed by the authors provides an environment for comparing the FF to commonly used dispatching rules. The results show the benefit of using the FF. Discussions reveal that this concept is more reliable in case of due dates with different tightness level.     

Deteriorating job scheduling to minimize the number of late jobs with setup times

Deteriorating jobs scheduling problems have been widely studied recently. However, research on scheduling problems with deteriorating jobs has rarely considered explicit setup times. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem to minimize the number of late jobs with deteriorating jobs and setup times in this paper. We derive some dominance properties, a lower bound, and an initial upper bound by using a heuristic algorithm to speed up the search process of the branch-and-bound algorithm. Computational experiments show that the algorithm can solve instances up to 1000 jobs in a reasonable amount of time.     

A note on the scheduling with two families of jobs

Baker and Smith [J. Scheduling, 6, 7–16, 2003] introduced a new model of scheduling in which there are two or more distinct families of jobs pursuing different objectives. Their contributions include two polynomial-time dynamic programming recursions, respectively, for the single machine scheduling with two families of jobs to minimize a positive combination of total weighted completion time, or maximum lateness, of the first family of jobs and maximum lateness of the second family of jobs. Unfortunately, these dynamic programming recursions are incorrect. In this paper, we solve the same problems by an O(n₁ n₂(n₁ + n₂)) time algorithm. Project supported by NNSFC (Grant 10371112) and NSFHN (Grant 0411011200)     

A Stronger Complexity Result for the Single Machine Multi-Operation Jobs Scheduling Problem to Minimize the Number of Tardy Jobs

We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.