Search

We consider scheduling problems with job processing time compatibility on a single unbounded batch machine. Each job's processing time is characterized by an interval. Any number of jobs can be processed in a batch under the condition that the processing time intervals of the jobs in the same batch have a nonempty intersection. The processing time of a batch is given by the left endpoint of the intersection of the processing time intervals of the jobs in the batch. For the makespan minimization problem with individual job release dates, we design a pseudo-polynomial dynamic programming algorithm for the case where the number of distinct release dates is fixed. We also present a class of online algorithms that are 2-competitive and a polynomial-time approximation scheme for the case where the number of release dates is arbitrary. For the problem to minimize the weighted number of tardy jobs under a common due date, we show that it is binary NP -hard and provide a polynomial-time algorithm when the jobs have a common weight. [ABSTRACT FROM AUTHOR]

Abstract: We consider a problem of scheduling resumable deteriorating jobs on a single machine with non-availability constraints. The objective is to minimize the total completion time. We prove that the problem with a single non-availability period is NP-hard in the ordinary sense and possesses a fully polynomial-time approximation scheme. In addition, we show that there does not exist a polynomial-time approximation algorithm with a constant worst-case ratio for the problem with two or more non-availability periods, unless . [ABSTRACT FROM AUTHOR]

Abstract: We consider several parallel-machine scheduling problems in which the processing time of a job is a (simple) linear increasing function of its starting time and jobs can be rejected by paying penalties. The objective is to minimize the scheduling cost of the accepted jobs plus the total penalty of the rejected jobs. Three variations of the scheduling cost are considered in this paper. The first is the makespan, the second is the total weighted completion time (for simple linear deterioration), and the third is the total completion time. For the former two problems, we propose two fully polynomial-time approximation schemes to solve them when the number of machines is fixed. For the last problem, we present an optimal -time dynamic programming algorithm when the deteriorating rates are equal for all jobs. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study the problem of scheduling deteriorating jobs with release dates on a single machine. The processing time of a job is assumed to be the product of its deteriorating rate and its starting time. Precedence relations may be imposed on the set of jobs. Unlike the classical time-dependent scheduling problems, we assume that the execution of a job can be preempted in the sense that the job’s deteriorating rate is reduced when it is preempted and each continuously processed part of a job can be regarded as an independent job with a specified deteriorating rate. The objective is to minimize some common regular scheduling performance measures. We first show that minimizing a class of regular symmetric functions is polynomially solvable. Then we construct an algorithm for minimizing the maximum job completion cost with or without precedence constraints. Finally we show that minimizing the total weighted completion time is NP-hard even if there are only two distinct release dates. [ABSTRACT FROM AUTHOR]

Abstract: We consider in this paper the scheduling of families of jobs in which both processing and delivery are coordinated together. Only one vehicle is available to deliver the jobs to specified customers. The jobs can be processed together to form processing batches on the machine and setups of batches are required when the machine is changing from one family to another. Jobs from different families cannot be transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We propose an -time optimal algorithm for the scheduling problem under the group technology assumption. For the scheduling problem without the group technology assumption, we show that the problem is NP-hard and give an -time dynamic programming algorithm, where is the number of jobs, and is the number of families; we also provide a heuristic algorithm with a performance ratio of 3/2. [Copyright &y& Elsevier]