Two-parallel machines scheduling with rate-modifying activities to minimize total completion time

This paper considers the two-parallel machines scheduling problem with rate-modifying activities. In this model, each machine has a rate-modifying activity that can change the processing rate of machine under consideration. Hence the actual processing times of jobs vary depending on whether the job is scheduled before or after the rate-modifying activity. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We provide polynomial and pseudo-polynomial time algorithms to solve the total completion time minimization problem and total weighted completion time minimization problem under agreeable ratio condition.     

Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties

In this paper we consider identical parallel machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remain polynomially solvable under the proposed model.     

Parallel machine scheduling with high multiplicity

In high-multiplicity scheduling problems, identical jobs are encoded in the efficient format of describing one of the jobs and the number of identical jobs. Similarly, identical machines are efficiently encoded in the same manner. We investigate parallel-machine, high-multiplicity problems, where there are three possible machine speed structures: identical, proportional, or unrelated. For the objectives of minimizing the sum of job completion times and minimizing the makespan, we consider both nonpreemptive and preemptive problems. For some problems, we develop polynomial time algorithms. For several problems, we demonstrate that the recognition versions can be solved in polynomial time, while the optimization versions require pseudo-polynomial time. We also show that changing from standard binary encoding to high-multiplicity encoding does not affect the complexity class of NP-complete problems. Received: April 1996 / Accepted: July 2000?Published online January 17, 2001     

Single machine scheduling with exponential learning functions

In this paper we consider the single machine scheduling problem with exponential learning functions. By the exponential learning functions, we mean that the actual job processing time is a function of the total normal processing times of the jobs already processed. We prove that the shortest processing time (SPT) rule is optimal for the total lateness minimization problem. For the following three objective functions, the total weighted completion time, the discounted total weighted completion time, the maximum lateness, we present heuristic algorithms according to the corresponding problems without exponential learning functions. We also analyse the worst-case bound of our heuristic algorithms. It also shows that the problems of minimizing the total tardiness and discounted total weighted completion time are polynomially solvable under some agreeable conditions on the problem parameters.     

Single machine common flow allowance scheduling with deteriorating jobs and a rate-modifying activity

We study a single machine slack due date assignment (usually referred to as SLK) scheduling problem with deteriorating jobs and a rate-modifying activity. The deterioration effect manifest such that the job processing time is a function of its starting time in a sequence. The rate-modifying activity is an activity that changes the processing rate of machine, i.e., the machine performs a rate-modifying activity. Hence the actual processing time of a job is a variable, which depends not only on its starting time in a sequence but also on whether it is scheduled before or after a rate-modifying activity. The goal is to schedule the rate-modifying activity, the optimal common flow allowance and the sequence of jobs to minimize the total earliness, the total tardiness and the common flow allowance cost. We show that the problem remains polynomially solvable under the proposed model.     

An Algorithm for Minimizing the Range of Lateness on a Single Machine

This paper considers the problem of minimizing the range of lateness on a single machine. All the algorithms in the literature for solving this problem are based on the branch-and-bound approach, which has an exponential time complexity. In this paper, we demonstrate that this problem can actually be solved in pseudo-polynomial time, and develop such an algorithm. Computational performance of this algorithm on problems with various sizes is provided.     

Scheduling linear deteriorating jobs with rejection on a single machine

We consider several single machine scheduling problems in which the processing time of a job is a linear function of its starting time and jobs can be rejected by paying penalties. The objectives are to minimize the makespan, the total weighted completion time and the maximum lateness/tardiness plus the total penalty of the rejected jobs. We show that these problems are NP-hard, and design algorithms based on dynamic programming (including pseudo-polynomial time optimal algorithms and fully polynomial time approximation schemes) to solve them.     

带有拒绝的单机和同型机排序问题

研究了带有拒绝的单机和同型机排序问题. 对于单机情形, 工件的惩罚费用是对应加工时间的\alpha倍.如果工件有到达时间, 目标为最小化时间表长与惩罚费用之和, 证明了这个问题是可解的.如果所有工件在零时刻到达, 目标为最小化总完工时间与惩罚费用之和, 也证明了该问题是可解的.对于同型机排序问题, 研究了工件分两批在线实时到达的情形, 目标为最小化时间表长与惩罚费用之和.针对机器台数2和m, 分别给出了竞争比为2和4-2/m的在线算法.     

A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs

The problem of scheduling on a single machine is considered in this paper with the objective of minimizing the sum of weighted tardiness of jobs. A new ant-colony optimization (ACO) algorithm, called fast ACO (FACO), is proposed and analysed for solving the single-machine scheduling problem. By considering the benchmark problems available in the literature for analysing the performance of algorithms for scheduling on a single machine with the consideration of weighted tardiness of jobs, we validate the appropriateness of the proposed local-search schemes and parameter settings used in the FACO. We also present a comparison of the requirements of CPU time for solving the single-machine total-weighted tardiness problem by the FACO and the existing algorithms.     

Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration

This paper considers two scheduling problems for a two-machine flowshop where a single machine is followed by a batching machine. The first problem is that there is a transporter to carry the jobs between machines. The second problem is that there are deteriorating jobs to be processed on the single machine. For the first problem with minimizing the makespan, we formulate it as a mixed integer programming model and then prove that it is strongly NP-hard. A heuristic algorithm is proposed for solving this problem and its worst case performance is analyzed. The computational experiments are carried out and the numerical results show that the heuristic algorithm is effective. For the second problem, we derive the optimal algorithms with polynomial time for minimizing the makespan, the total completion time and the maximum lateness, respectively.     

基于重新排序时间错位限制下的最小化总完工时间的平行分批排序（英文）

In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.     

Flow shop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date

We consider two problems of m-machine flow shop scheduling in this paper: one, with the objective of minimizing the variance of completion times of jobs, and the other with the objective of minimizing the sum of squares of deviations of job completion times from a common due date. Lower bounds on the sum of squares of deviations of job completion times from the mean completion time of jobs for a given partial sequence are first presented. Using these lower bounds, a branch and bound algorithm based on breadth-first search procedure for scheduling n jobs on m-machines with the objective of minimizing completion time variance (CTV) is developed to obtain the best permutation sequence. We also present two lower bounds and thereafter, a branch and bound algorithm with the objective of minimizing the sum of squares of deviations of job completion times from a given common due date (called the MSD problem). The computational experience with the working of the two proposed branch and bound algorithms is also reported. Two heuristics, one for each of the two problems, are developed. The computational experience on the evaluation of the heuristics is discussed.     

Scheduling problems in master-slave model

We consider scheduling problems in the master slave model, which was introduced by Sahni in 1996. The goal is to minimize the makespan and the total completion time. It has been shown that the problem of minimizing makespan is NP-hard. Sahni and Vairaktarakis developed some approximation algorithms to generate schedules whose makespan is at most constant times the optimal. In this paper, we show that the problem of minimizing total completion time is NP-hard in the strong sense. Then we develop algorithms to generate schedules whose total completion time and makespan are both bounded by some constants times their optimal values. Research supported in part by the National Science Foundation through grant DMI-0300156.     

Coordinating multi-location production and customer delivery

We study two parallel machine scheduling problems with equal processing time jobs and delivery times and costs. The jobs are processed on machines which are located at different sites, and delivered to a customer by a single vehicle. The first objective considered is minimizing the sum of total weighted completion time and total vehicle delivery costs. The second objective considered is minimizing the sum of total tardiness and total vehicle delivery costs. We develop several interesting properties of an optimal scheduling and delivery policy, and show that both problems can be solved by reduction to the Shortest-Path problem in a corresponding network. The overall computational effort of both algorithms is O(n ^m2+m+1) (where n and m are the number of jobs and the number of machines, respectively) by the application of the Directed Acyclic Graph (DAG) method. We also discuss several special cases for which the overall computational effort can be significantly reduced.     

Single machine total tardiness maximization problems: complexity and algorithms

In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the total weighted tardiness maximization problem, we present an NP-hardness proof and a pseudo-polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP-hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well.     

Minimizing Completion Time Variance with Compressible Processing Times

We introduce a new formulation of the standard completion time variance (CTV) problem with n jobs and one machine, in which the job sequence and the processing times of the jobs are all decision variables. The processing time of job i (i=1, ,n) can be compressed by an amount within [l_i, u_i], which however will incur a compression cost. The compression cost is a general convex non-decreasing function of the amount of the job processing time compressed. The objective is to minimize a weighted combination of the completion time variance and the total compression cost. We show that, under an agreeable condition on the bounds of the processing time compressions, a pseudo-polynomial algorithm can be derived to find an optimal solution for the problem. Based on the pseudo-polynomial time algorithm, two heuristic algorithms H1 and H2 are proposed for the general problem. The relative errors of both heuristic algorithms are guaranteed to be no more than , where is a measure of deviation from the agreeable condition. While H1 can find an optimal solution for the agreeable problem, H2 is dominant for solving the general problem. We also derive a tight lower bound for the optimal solution of the general problem. The performance of H2 is evaluated by complete enumeration for small n, and by comparison with this tight lower bound for large n. Computational results (with n up to 80) are reported, which show that the heuristic algorithm H2 in general can efficiently yield near optimal solutions, when n is large.     

Makespan minimization in single-machine scheduling with step-deterioration of processing times

This paper considers a single-machine scheduling problem of minimizing the maximum completion time for a set of independent jobs. The processing time of a job is a non-linear step function of its starting time and due date. The problem is already known to be ????-hard in the literature. In this paper, we first show this problem to be ????-hard in the ordinary sense by proposing a pseudo-polynomial time dynamic programming algorithm. Then, we develop two dominance rules and a lower bound to design a branch-and-bound algorithm for deriving optimal solutions. Numerical results indicate that the proposed properties can effectively reduce the time required for exploring the solution space.     

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.     

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 average completion time in the presence of release dates

A natural and basic problem in scheduling theory is to provide good average quality of service to a stream of jobs that arrive over time. In this paper we consider the problem of schedulingn jobs that are released over time in order to minimize the average completion time of the set of jobs. In contrast to the problem of minimizing average completion time when all jobs are available at time 0, all the problems that we consider are NP-hard, and essentially nothing was known about constructing good approximations in polynomial time. We give the first constant-factor approximation algorithms for several variants of the single and parallel machine models. Many of the algorithms are based on interesting algorithmic and structural relationships between preemptive and nonpreemptive schedules and linear programming relaxations of both. Many of the algorithms generalize to the minimization of averageweighted completion time as well. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This work was performed under US Department of Energy contract number DE-AC04-76AL85000.Research partly supported by NSF Award CCR-9308701, a Walter Burke Research Initiation Award and a Dartmouth College Research Initiation Award.Research partially supported by NSF Research Initiation Award CCR-9211494 and a grant from the New York State Science and Technology Foundation, through its Center for Advanced Technology in Telecommunications.