Single-machine scheduling with convex resource dependent processing times and deteriorating jobs

In this study, we consider scheduling problems with convex resource dependent processing times and deteriorating jobs, in which the processing time of a job is a function of its starting time and its convex resource allocation. The objective is to find the optimal sequence of jobs and the optimal convex resource allocation separately. This paper focus on the single-machine problems with objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. It shows that the problems remain polynomially solvable under the proposed model.     

A note on the complexity of flow-shop scheduling with deteriorating jobs

This paper is a note on “Complexity analysis of job-shop scheduling with deteriorating jobs” [G. Mosheiov, Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics 117 (2002) 195-209]. A proportional deterioration rate is assumed and the objective is the minimization of the makespan. Mosheiov presents NP-hardness results for flow-shops and open-shops with three or more machines and for job-shops with two or more machines. The proof of NP-hardness for the flow-shop case is however not correct. This paper provides a correct proof.     

Unrelated parallel machines scheduling with deteriorating jobs and resource dependent processing times

We consider unrelated parallel machines scheduling problems involving resource dependent (controllable) processing times and deteriorating jobs simultaneously, i.e., the actual processing time of a job is a function of its starting time and its resource allocation. Two generally resource consumption functions, the linear and convex resource, were investigated. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. This paper focus on the objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. If the number of unrelated parallel machines is a given constant, we show that the problems remain polynomially solvable under the proposed model.     

Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times

In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier – this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems.     

Single-machine scheduling with deteriorating functions for job processing times

In many realistic scheduling settings a job processed later consumes more time than when it is processed earlier – this phenomenon is known as scheduling with deteriorating jobs. In the literature on deteriorating job scheduling problems, majority of the research assumed that the actual job processing time of a job is a function of its starting time. In this paper we consider a new deterioration model where the actual job processing time of a job is a function of the processing times of the jobs already processed. We show that the single-machine scheduling problems to minimize the makespan and total completion time remain polynomially solvable under the proposed model. In addition, we prove that the problems to minimize the total weighted completion time, maximum lateness, and maximum tardiness are polynomially solvable under certain agreeable conditions.     

Minimizing the number of machines for scheduling jobs with equal processing times

In this paper, we consider a parallel machine environment when all jobs have the same processing time and arbitrary release dates and deadlines of the jobs are given. We suppose that the available number of machines, which can be used simultaneously, may vary over time. The aim is to construct a feasible schedule in such a way that the maximal number of simultaneously used machines is minimal. We give a polynomial algorithm for this problem.     

Some scheduling problems with time-dependent learning effect and deteriorating jobs

Although machine scheduling problems with learning and deteriorating effects consideration have received increasing attention in the recent years, most studies have seldom considered the two phenomena simultaneously. However, learning and deteriorating effects might co-exist in many realistic scheduling situations. Thus, in this article, a model which takes the effects of time-dependent learning and deterioration simultaneously is proposed and applied into some scheduling problems. Under the proposed model, the processing time of a job is determined by a function of its corresponding starting time and positional sequence in each machine. We show that some single machine and flowshop scheduling problems are polynomially solvable with the certain performance measures such as makespan, total completion time, and weighted completion time.     

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes

This paper considers the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makespan and total completion time are given using mixed integer programming method and the computational complexity is analyzed. The bound on the number of feasible solutions is given and the properties of the optimal solutions are presented. Then a polynomial time algorithm is proposed and the worst case ratios for minimizing total completion time and makespan is proved to be 2 and (8/3–2/3 m) respectively. To test the proposed algorithm, we generate different levels of random instances. The computational results demonstrate the effectiveness of the algorithm for minimizing the two objectives.     

Considerations of single-machine scheduling with deteriorating jobs

This paper considers some scheduling problems with deteriorating jobs. The objectives are to minimize the makespan, the total completion time, the total absolute deviation of completion time, the earliness, tardiness, and due date penalty, the sum of earliness penalties subject to no tardy jobs, respectively. We also explore two resource constrained scheduling problems: how to minimize the resource consumption with makespan constraints and how to minimize the makespan with the total resource consumption constraints. Several polynomial time algorithms are proposed to optimally solve the problems with the above objective functions.     

On-line scheduling on a batch processing machine with unbounded batch size to minimize the makespan

We present on-line algorithms to minimize the makespan on a single batch processing machine. We consider a parallel batching machine that can process up to b jobs simultaneously. Jobs in the same batch complete at the same time. Such a model of a batch processing machine has been motivated by burn-in ovens in final testing stage of semiconductor manufacturing. We deal with the on-line scheduling problem when jobs arrive over time. We consider a set of independent jobs. Their number is not known in advance. Each job is available at its release date and its processing requirement is not known in advance. This general problem with infinite machine capacity is noted 1∣p − batch, r_j, b = ∞∣C_max. Deterministic algorithms that do not insert idle-times in the schedule cannot be better than 2-competitive and a simple rule based on LPT achieved this bound [Z. Liu, W. Yu, Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics 105 (2000) 129–136]. If we are allowed to postpone start of jobs, the performance guarantee can be improved to 1.618. We provide a simpler proof of this best known lower bound for bounded and unbounded batch sizes. We then present deterministic algorithms that are best possible for the problem with unbounded batch size (i.e., b = ∞) and agreeable processing times (i.e., there cannot exist an on-line algorithm with a better performance guarantee). We then propose another algorithm that leads to a best possible algorithm for the general problem with unbounded batch size. This algorithm improves the best known on-line algorithm (i.e. [G. Zhang, X. Cai, C.K. Wong, On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics 48 (2001) 241–258]) in the sense that it produces a shortest makespan while ensuring the same worst-case performance guarantee.     

Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times

In this paper, we study the identical parallel machine scheduling problem with a planned maintenance period on each machine to minimize the sum of completion times. This paper is a first approach for this problem. We propose three exact methods to solve the problem at hand: mixed integer linear programming methods, a dynamic programming based method and a branch-and-bound method. Several constructive heuristics are proposed. A lower bound, dominance properties and two branching schemes for the branch-and-bound method are presented. Experimental results show that the methods can give satisfactory solutions.     

A survey of scheduling with controllable processing times

In classical deterministic scheduling problems, the job processing times are assumed to be constant parameters. In many practical cases, however, processing times are controllable by allocating a resource (that may be continuous or discrete) to the job operations. In such cases, each processing time is a decision variable to be determined by the scheduler, who can take advantage of this flexibility to improve system performance. Since scheduling problems with controllable processing times are very interesting both from the practical and theoretical point of view, they have received a lot of attention from researchers over the last 25 years. This paper aims to give a unified framework for scheduling with controllable processing times by providing an up-to-date survey of the results in the field.     

Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time

This paper investigates scheduling problems with simultaneous considerations of deterioration effects and deteriorating multi-maintenance activities on unrelated parallel machines. We examine two models of scheduling with the deterioration effect, namely the job-dependent and position-dependent deterioration model and the time-dependent deterioration model. We assume that each machine may be subject to several maintenance activities over the scheduling horizon, and the duration of maintenance on a machine depends on its running time. Moreover, due to the restriction of the budget of maintenance, the upper bound of the total maintenance frequencies on all the machines is assumed to be known in advance. The objective is to find jointly the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequences such that the total completion time is minimized. If the number of machines is fixed, we introduce polynomial time solutions for all the versions of the problem under study.     

工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.     

Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan

We consider a scheduling problem in which n jobs are to be processed on a single machine. The jobs are processed in batches and the processing time of each job is a simple linear function of its waiting time, i.e., the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. The objective is to minimize the makespan, i.e., the completion time of the last job. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B  , the problem remains strongly NP-hard when B?U$B?U$ for a variable U?2$U?2$ or B?U$B?U$ for any constant U?2$U?2$. For the case of B?U$B?U$, we present a dynamic programming algorithm that runs in pseudo-polynomial time and a fully polynomial time approximation scheme (FPTAS) for any constant U?2$U?2$. Furthermore, we provide an optimal linear time algorithm for the special case where the jobs are subject to a linear precedence constraint, which subsumes the case where all the job growth rates are equal.     

Minimizing the sum of job completion times on capacitated two-parallel machines

This paper considers a scheduling problem with two identical parallel machines. One has unlimited capacity; the other can only run for a fixed time. A given set of jobs must be scheduled on the two machines with the goal of minimizing the sum of their completion times. The paper proposes an optimal branch and bound algorithm which employs three powerful elements, including an algorithm for computing the upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1 second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems.