Bounded single-machine parallel-batch scheduling with release dates and rejection

We consider the bounded single-machine parallel-batch scheduling problem with release dates and rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and then processed on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs. When the jobs have identical release dates, we present a polynomial-time algorithm. When the jobs have a constant number of release dates, we give a pseudo-polynomial-time algorithm. For the general problem, we provide a 2-approximation algorithm and a polynomial-time approximation scheme.     

A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time

This paper proposes an efficient exact algorithm for the general single-machine scheduling problem where machine idle time is permitted. The algorithm is an extension of the authors’ previous algorithm for the problem without machine idle time, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. We first extend our previous algorithm to the problem with machine idle time and next propose several improvements. Then, the proposed algorithm is applied to four types of single-machine scheduling problems: the total weighted earliness-tardiness problem with equal (zero) release dates, that with distinct release dates, the total weighted completion time problem with distinct release dates, and the total weighted tardiness problem with distinct release dates. Computational experiments demonstrate that our algorithm outperforms existing exact algorithms and can solve instances of the first three problems with up to 200 jobs and those of the last problem with up to 80 jobs.     

带有线性恶化工件和释放时间的两个代理单机调度问题

研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题. 所有工件在一台机器上加工, 每个代理有各自依赖于自己工件的优化目标. 针对工件释放时间相同与不同两种情况, 研究了有约束的优化模型, 即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界. 当工件具有相同的释放时间, 我们主要考虑的目标函数有: 总加权完工时间和总加权拖期工件数. 当工件具有不同释放时间, 我们考虑的目标函数有: 最大完工时间、总完工时间以及拖期工件数. 对于每一个问题, 我们分析了问题的计算复杂性. 此外, 对于NP难问题的一些特殊情况本文分析了最优解性质, 基于这些性质给出了最优算法.     

Optimality proof of the Kise–Ibaraki–Mine algorithm

Kise, Ibaraki and Mine (Operations Research 26:121–126, 1978) give an O(n ²) time algorithm to find an optimal schedule for the single-machine number of late jobs problem with agreeable job release dates and due dates. Li, Chen and Tang (Operations Research 58:508–509, 2010) point out that their proof of optimality for their algorithm is incorrect by giving a counter-example. In this paper we give a correct proof of optimality for their algorithm.     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.     

Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates

This paper is the first attempt to successfully design efficient approximation algorithms for the single-machine weighted flow-time minimization problem when jobs have different release dates and weights equal to their processing times under the assumption that one job is fixed (i.e., the machine is unavailable during a fixed interval corresponding to the fixed job). Our work is motivated by an interesting algorithmic application to the generation of valid inequalities in a branch-and-cut method. Our analysis shows that the trivial FIFO sequence can lead to an arbitrary large worst-case performance bound. Hence, we modify this sequence so that a new 2-approximation solution can be obtained for every instance and we prove the tightness of this bound. Then, we propose a fully polynomial-time approximation algorithm with efficient running time for the considered problem. Especially, the complexity of our algorithm is strongly polynomial.     

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.     

Scheduling with job release dates, delivery times and preemption penalties

We consider in this paper the single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties, where each time a job is started, whether initially or after preemption, a job-dependent setup must take place. First, we prove that the problem is strongly NP-hard. Then, we present a dynamic programming algorithm and a polynomial time approximation scheme.     

Exact algorithms for single-machine scheduling with time windows and precedence constraints

We study a single-machine scheduling problem that is a generalization of a number of problems for which computational procedures have already been published. Each job has a processing time, a release date, a due date, a deadline, and a weight representing the penalty per unit-time delay beyond the due date. The goal is to schedule all jobs such that the total weighted tardiness penalty is minimized and both the precedence constraints as well as the time windows (implied by the release dates and the deadlines) are respected. We develop a branch-and-bound algorithm that solves the problem to optimality. Computational results show that our approach is effective in solving medium-sized instances, and that it compares favorably with existing methods for special cases of the problem.     

Optimal release time on a stochastic single machine

The job release times are usually treated as given information in most scheduling research. However, in practice, the release time can be a controlled variable. It should be controlled carefully for many reasons. Jobs released to the shop floor too early would result in carrying costs (e.g. cost incurred by having unnecessary capital tied up in inventory). On the other hand, jobs released too late would cause machines and other resources to be idle and miss the due dates. With proper job release control, the best trade-off can be achieved, In this paper we consider a single-machine scheduling problem in which the processing times are stochastic. In particular, two models are under consideration. Model I assumes no unreleased jobs in the system while Model II relaxes this assumption. Procedures are developed for both models to determine the optimal release time for the arriving job. The objective is to minimize the weighted average of the expected flow time and the expected make-span     

A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates

This paper presents a bicriterion analysis of time/cost trade-offs for the single-machine scheduling problem where both job processing times and release dates are controllable by the allocation of a continuously nonrenewable resource. Using the bicriterion approach, we distinguish between our sequencing criterion, namely the makespan, and the cost criterion, the total resource consumed, in order to construct an efficient time/cost frontier. Although the computational complexity of the problem of constructing this frontier remains an open question, we show that the optimal job sequence is independent of the total resource being used; thereby we were able to reduce the problem to a sequencing one. We suggest an exact dynamic programming algorithm for solving small to medium sizes of the problem, while for large-scale problems we present some heuristic algorithms that turned out to be very efficient. Five different special cases that are solvable by using polynomial time algorithms are also presented.     

New Hybrid Optimization Algorithms for Machine Scheduling Problems

Dynamic programming, branch-and-bound, and constraint programming are the standard solution principles for finding optimal solutions to machine scheduling problems. We propose a new hybrid optimization framework that integrates all three methodologies. The hybrid framework leads to powerful solution procedures. We demonstrate our approach through the optimal solution of the single-machine total weighted completion time scheduling problem subject to release dates, which is known to be strongly NP-hard. Extensive computational experiments indicate that new hybrid algorithms use orders of magnitude less storage than dynamic programming, and yet can still reap the full benefit of the dynamic programming property inherent to the problem. We are able to solve to optimality all 1900 instances with up to 200 jobs. This more than doubles the size of problems that can be solved optimally by the previous best algorithm running on the latest computing hardware.     

Speed Scaling for Maximum Lateness

We consider the power-aware problem of scheduling non-preemptively a set of jobs on a single speed-scalable processor so as to minimize the maximum lateness, under a given budget of energy. In the offline setting, our main contribution is a combinatorial polynomial time algorithm for the case in which the jobs have common release dates. In the presence of arbitrary release dates, we show that the problem becomes strongly \(\mathcal {N}\mathcal {P}\)-hard. Moreover, we show that there is no O(1)-competitive deterministic algorithm for the online setting in which the jobs arrive over time. Then, we turn our attention to an aggregated variant of the problem, where the objective is to find a schedule minimizing a linear combination of maximum lateness and energy. As we show, our results for the budget variant can be adapted to derive a similar polynomial time algorithm and an \(\mathcal {N}\mathcal {P}\)-hardness proof for the aggregated variant in the offline setting, with common and arbitrary release dates respectively. More interestingly, for the online case, we propose a 2-competitive algorithm.     

Simulated-annealing heuristics for the single-machine scheduling problem with learning and unequal job release times

In scheduling of batch processing machines in the diffusion and oxidation areas of a wafer fabrication facility, it can be found that the processing times of these batching operations can be extremely long (10 h) when compared to other operations (1-2 h) in a wafer fab. Moreover, the jobs to be processed may have different priorities/weights, due dates and ready times. In the presence of unequal ready times, it would be better to wait for future job arrivals in order to increase the fullness of the batch. On the other hand, repeated processing of similar tasks improves workers’ skills. Motivated by these observations, we consider a single-machine problem with the sum of processing times based learning effect and release times. The objective is to find a schedule to minimize the total completion times. We first develop a branch-and-bound algorithm for the optimal solution. Then we propose a simulated-annealing heuristic algorithm for a near-optimal solution. Finally, we conduct a computational experiment to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 24 jobs, and the average error percentage of the simulated-annealing algorithm is less than 0.1482%.     

On the equivalence of single machine earliness/tardiness problems with job rejection

We present optimal algorithms for single-machine scheduling problems with earliness criteria and job rejection and compare them with the algorithms for the corresponding problems with tardiness objectives. We present an optimal O(n log n) algorithm for minimizing the maximum earliness on a single machine with job rejection. Our algorithm also solves the bi-criteria scheduling problem is which the objective is to simultaneously minimize the maximum earliness of the scheduled jobs and the total rejection cost of the rejected jobs. We also show that the optimal pseudo-polynomial time algorithm for the total tardiness problem with job rejection can be used to solve the corresponding total earliness problem with job rejection.     

Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates

In this paper, we consider a single-machine scheduling problem with release dates. The aim is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose two new lower bounds that can be, respectively, computed in O(n²) and in O(nlogn) time where n is the number of jobs. We prove a sufficient and necessary condition for local optimality, which can also be considered as a priority rule. We present an efficient heuristic using such a condition. We also propose some dominance properties. A branch-and-bound algorithm incorporating the heuristic, the lower bounds and the dominance properties is proposed and tested on a large set of instances.     

Genetic algorithms for a two-agent single-machine problem with release time

Scheduling with two competing agents has drawn a lot of attention lately. However, it is assumed that all the jobs are available in the beginning in most of the research. In this paper, we study a single-machine problem in which jobs have different release times. The objective is to minimize the total tardiness of jobs from the first agent given that the maximum tardiness of jobs from the second agent does not exceed an upper bound. Three genetic algorithms are proposed to obtain the near-optimal solutions. Computational results show that the branch-and-bound algorithm could solve most of the problems with 16 jobs within a reasonable amount of time. In addition, it shows that the performance of the combined genetic algorithm is very good with mean error percentages of less than 0.2% for all the cases.     

Two-agent singe-machine scheduling with release times to minimize the total weighted completion time

In many management situations multiple agents pursuing different objectives compete on the usage of common processing resources. In this paper we study a two-agent single-machine scheduling problem with release times where the objective is to minimize the total weighted completion time of the jobs of one agent with the constraint that the maximum lateness of the jobs of the other agent does not exceed a given limit. We propose a branch-and-bound algorithm to solve the problem, and a primary and a secondary simulated annealing algorithm to find near-optimal solutions. We conduct computational experiments to test the effectiveness of the algorithms. The computational results show that the branch-and-bound algorithm can solve most of the problem instances with up to 24 jobs in a reasonable amount of time and the primary simulated annealing algorithm performs well with an average percentage error of less than 0.5% for all the tested cases.     

Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates

We address the parallel machine total weighted tardiness scheduling problem with release dates. We describe dominance rules and filtering methods for this problem. Most of them are adaptations of dominance rules based on solution methods for the single-machine problem. We show how it is possible to deduce whether or not certain jobs can be processed by a particular machine in a particular context and we describe techniques that use this information to improve the dominance rules. On the basis of these techniques we describe an enumeration procedure and we provide experimental results to determine the effectiveness of the dominance rules.     

Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times

This paper considers a single-machine problem with the sum-of-processing time based learning effect and release times. The objective is to minimize the total weighted completion times. First, a branch-and-bound algorithm incorporating with several dominance properties and two lower bounds are developed for the optimal solution. Then a genetic heuristic-based algorithm is proposed for a near-optimal solution. Finally, a computational experiment is conducted to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 15 jobs, and the average error percentage of the genetic heuristic algorithm is less than 0.105%.