Just-in-time scheduling with controllable processing times on parallel machines

We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider four different models for treating the two criteria. We prove that three of these problems are NP\mathcal{NP} -hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three NP\mathcal{NP} -hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial time optimization algorithm, which is converted to a fully polynomial time approximation scheme.     

A note on the complexity of the problem of two-agent scheduling on a single machine

We consider a two-agent scheduling problem on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the number of tardy jobs of the second agent cannot exceed a given number. It is reported in the literature that the complexity of this problem is still open. We show in this paper that this problem is NP-hard under high multiplicity encoding and can be solved in pseudo-polynomial time under binary encoding. When the first agent's objective is to minimize the total weighted completion time, we show that the problem is strongly NP-hard even when the number of tardy jobs of the second agent is restricted to be zero.     

Two-agent scheduling problems on a single-machine to minimize the total weighted late work

In this paper, two-agent scheduling problems are presented. The different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. The objective functions we consider are the total weighted late work and the maximum cost. The problem is to find a schedule that minimizes the objective function of agent A, while keeping the objective function of agent B cannot exceed a given bound U. Some different scenarios are presented by depending on the objective function of each agent. We address the complexity of those problems, and present the optimal polynomial time algorithms or pseudo-polynomial time algorithm to solve the scheduling problems, respectively.     

A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling

In the multiprocessor scheduling problem to minimize the total job completion time, an optimal schedule can be obtained by the shortest processing time rule and the completion time of each job in the schedule can be used as a guarantee for scheduling revenue. However, in practice, some jobs will not arrive at the beginning of the schedule but are delayed and their delayed arrival times are given to the decision-maker for possible rescheduling. The decision-maker can choose to reject some jobs in order to minimize the total operational cost that includes three cost components: the total rejection cost of the rejected jobs, the total completion time of the accepted jobs, and the penalty on the maximum tardiness for the accepted jobs, for which their completion times in the planned schedule are their virtual due dates. This novel rescheduling problem generalizes several classic NP-hard scheduling problems. We first design a pseudo-polynomial time dynamic programming exact algorithm and then, when the tardiness can be unbounded, we develop it into a fully polynomial time approximation scheme. The dynamic programming exact algorithm has a space complexity too high for truthful implementation; we propose an alternative to integrate the enumeration and the dynamic programming recurrences, followed by a depth-first-search walk in the reschedule space. We implemented the alternative exact algorithm in C and conducted numerical experiments to demonstrate its promising performance.

     

Customer order scheduling to minimize total weighted completion time

In this paper we study the scheduling problem in which each customer order consists of several jobs of different types, which are to be processed on m facilities. Each facility is dedicated to the processing of only one type of jobs. All jobs of an order have to be delivered to the customer at the same time. The objective is to schedule all the orders to minimize the total weighted order completion time. While the problem has been shown to be unary NP-hard, we develop a heuristics to tackle the problem and analyze its worst-case performance.     

New results on two-machine flow-shop scheduling with rejection

In this paper, we consider the off-line and on-line two-machine flow-shop scheduling problems with rejection. The objective is to minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs. For the off-line version, Shabtay and Gasper (Comput Oper Res 39:1087–1096, 2012) showed that this problem is NP-hard and then provided a pseudo-polynomial-time algorithm, two 2-approximation algorithms and a fully polynomial-time approximation scheme. We further study some special cases in this paper. We show that this problem is still NP-hard even when all jobs have the same processing time on one of the machines or all jobs have the same rejection penalty. Furthermore, we also showed that this problem can be solved in polynomialtime algorithm when all jobs satisfy the agreeable condition on their processing times and rejection penalties. For the on-line version without rejection, Chen and Woeginger [in: Du DZ, Pardalos PM (eds.) Minimax and Applications, 1995] showed that the competitive ratio of any determined on-line algorithm is at least 2. We further show that the competitive ratio of any determined on-line algorithm is at least 2 even when all jobs have the same processing time on the first machine. Finally, for the on-line version with rejection, we present a class of on-line algorithms with the best-possible competitive ratio 2.     

Single-machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect

We study single machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect. In the general truncated learning model, the actual processing time of a job is affected by the sum of actual processing times of previous jobs and by a job-dependent truncation parameter. We show that the single machine problems to minimize makespan and to minimize the sum of weighted completion times are both at least ordinary NP-hard and the single machine problem to minimize maximum lateness is strongly NP-hard. We then show polynomial solvable cases and approximation algorithms for these problems. Computational experiments are also conducted to show the effectiveness of our approximation algorithms.

     

Online scheduling to minimize the total weighted completion time plus the rejection cost

We consider the online scheduling on a single machine, in which jobs are released over time and each job can be either accepted and scheduled on the machine or rejected under a certain rejection cost. The goal is to minimize the total weighted completion time of the accepted jobs plus the total rejection cost of the rejected jobs. For this problem, we provide an online algorithm with a best possible competitive ratio of 2.     

Scheduling with machine cost and rejection

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case, (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.     

Single-machine scheduling with production and rejection costs to minimize the maximum earliness

In this paper, we consider the single-machine scheduling problem with production and rejection costs to minimize the maximum earliness. If a job is accepted, then this job must be processed on the machine and a corresponding production cost needs be paid. If the job is rejected, then a corresponding rejection cost has to be paid. The objective is to minimize the sum of the maximum earliness of the accepted jobs, the total production cost of the accepted jobs and the total rejection cost of the rejected jobs. We show that this problem is equivalent to a single-machine scheduling problem to minimize the maximum earliness with two distinct rejection modes. In the latter problem, rejection cost might be negative in the rejection-award mode which is different from the traditional rejection-penalty mode in the previous literatures. We show that both of two problems are NP-hard in the ordinary sense and then provide two pseudo-polynomial-time algorithms to solve them. Finally, we also show that three special cases can be solved in polynomial time.     

Online integrated production–distribution scheduling problems without preemption

We study an integrated production–distribution scheduling problem where jobs are released by customers to a manufacturer over time. The jobs are released online, that is, at any time the information of the number, release and processing times of future jobs is unknown, and the processing time of a job becomes known when the job is released. The manufacturer processes the jobs on a single machine. During the processing of jobs preemption is not allowed. Completed jobs are delivered in batches to customers via sufficient capacitated vehicles. For the objective of minimizing the sum of the total delivery time and the total distribution cost, we present a 3-competitive algorithm for the single-customer case and then extend the result to the multi-customer case. A lower bound of two on the competitive ratio of the problem is also given.     

Single machine batch scheduling with release times

Motivated by a high-throughput logging system, we investigate the single machine scheduling problem with batching, where jobs have release times and processing times, and batches require a setup time. Our objective is to minimize the total flow time, in the online setting. For the online problem where all jobs have identical processing times, we propose a 2-competitive algorithm and we prove a corresponding lower bound. Moreover, we show that if jobs with arbitrary processing times can be processed in any order, any online algorithm has a linear competitive ratio in the worst case. A preliminary version of a part of this paper was presented at the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). We gratefully acknowledge reviewers’ comments that helped to improve the presentation of this work. Supported by the Swiss SBF under contract no. C05.0047 within COST-295 (DYNAMO) of the European Union. Research carried out while B. Weber was affiliated with the Institute of Theoretical Computer Science, ETH Zurich.     

Minimizing the Number of Late Jobs under the Group Technology Assumption

We consider the one-machine scheduling problem to minimize the number of late jobs under the group technology assumption, where jobs are classified into groups and all jobs from the same group must be processed contiguously. This problem is shown to be strongly NP-hard, even for the case of unit processing time and zero set-up time. A polynomial time algorithm is developed for the restricted version in which the jobs in each group have the same due date. However, the problem is proved to be ordinarily NP-hard if the jobs in a group have the same processing time as well as the same due date.     

混合离散差分进化算法在单机批处理调度中的应用

本文研究单机批处理调度问题,批处理机有批次容量限制,批处理时间由每个批次所含作业中的最长作业处理时间决定。每个作业具有不同的大小、处理时间、提前拖期惩罚权重,所有作业具有公共交货期,且交货期无限晚。目标函数为最小化所有作业的加权提前拖期惩罚之和。该问题已被证明为NP难题,本研究找到了其最优解具有的一些性质,在此基础上利用它们提出了一种动态规划(DP)与差分进化(DE)算法相结合的混合离散差分进化(HDDE)算法来求解该问题,通过与传统的遗传算法、模拟退火算法和迭代贪婪算法进行对比,HDDE算法显示了更加强大的全局搜索能力。     

On single machine scheduling with resource constraint

The single machine scheduling with resource constraint is a nonlinear combinatorial optimization problem in cloud computing applications. Given a set of jobs and certain resource, the problem is to find a permutation of jobs and a distribution of resource to optimize certain objective function. The processing time of each job is a nonlinear function with respect to the resource assigned to it. In this paper, we propose a naive algorithm and study a subproblem in the algorithm that suppose the permutation of jobs is also given, how to find a resource distribution to minimize the total weighted flow time. We found a polynomial-time optimal solution for a special case and an approximation solution in general case.     

On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time

Scheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times C _j is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time w _j C _j. We provide a linear time on-line algorithm for the unrestrictive model (i.e., b n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + )-competitive on-line algorithm for any > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.     

Non-resumable scheduling on a single bounded parallel-batch machine with periodic maintenance

We consider the problem of scheduling a set of jobs with different processing times and sizes on a single bounded parallel-batch machine with periodic maintenance. Because the machine is in batch-processing model and the capacity is fixed, several jobs can be processed simultaneously in a batch provided that the total size of the jobs in the batch doesn’t exceed the machine capacity. And the processing time of a batch is the largest processing time of the jobs contained in the batch. Meanwhile, the production of each batch is non-resumable, that is, if a batch cannot be completed processing before some maintenance, that batch needs to be processed anew once the machine returns available. Our goal is to minimize the makespan. We first consider two special cases where the jobs have the same sizes or the same processing times, both of which are strongly NP-hard. We present two different approximation algorithms for them and show that these two algorithms have the same tight worst-case ratio of 2. We then consider the general case where the jobs have the arbitrary processing times and arbitrary sizes, for which we propose a 17/5-approximation algorithm.

     

MINIMIZING ABSOLUTE AND SQUARED DEVIATION OF COMPLETION TIMES FROM DUE DATES

This is a study of a single-machine scheduling problem with the objective of minimizing the sum of a function of earliness and tardiness called the earliness and tardiness (ET) problem. I will show that if priority weights of jobs are proportional to their processing times, and if earliness and tardiness cost functions are linear, the problem will be equivalent to the total weighted tardiness problem. This proves that the et problem is np -hard. In addition, I present a heuristic algorithm with worst case bound for the et problem based on the equivalence relation between the two. When earliness and tardiness cost functions are quadratic, I consider the problem for a common due date for all jobs and for different job due dates. In general, the et problem with quadratic earliness and tardiness cost functions and all job weights equal to one is np -hard. I show that in many cases, when weights of jobs are proportional to their processing times, the problem can be solved efficiently. In the published results on the et problem with quadratic earliness and tardiness cost functions other researchers have assumed a zero starting time for the schedule. I discuss the advantages of a nonzero starting time for the schedule.     

Batch-Processing Scheduling with Setup Times

The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.