New directions in scheduling theory

This is an assessment of new developments in the theory of sequencing and scheduling. After a review of recent results and open questions within the traditional class of scheduling problems, we focus on the probabilistic analysis of scheduling algorithms and next discuss some extensions of the traditional problem class that seem to be of particular interest.     

Complexity of the job insertion problem in multi-stage scheduling

The job insertion problem in multi-stage scheduling is: given a schedule for n jobs and an additional job, find a feasible insertion of the additional job into the schedule that minimizes the resulting makespan. We prove that finding the optimal job insertion is NP-hard for flow shops and open shops.     

多供应商多零售商下经济批量问题的多项式时间算法研究

基于多供应商和多零售商构成的经济批量问题,通过构建优化模型,分析了订购费用为全部单位数量折扣和增加数量折扣两种情形模型最优解的相关性质。将这些性质应用到动态规划算法设计中,对订购费用为全部单位数量折扣时的一种特殊情形及增加数量折扣的一般情形分别设计了求解问题最优解的多项式时间算法,并用算例说明了算法的执行过程和有效性。     

A historical note on the complexity of scheduling problems

In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented linear-time reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.     

On the complexity of finding paths in a two‐dimensional domain I: Shortest paths

The computational complexity of finding a shortest path in a two‐dimensional domain is studied in the Turing machine‐based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial‐time computable two‐dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial‐time recognizable domains with polynomial‐time computable distance functions. It is proved that the shortest path problem has the polynomial‐space upper bound for domains of both type (A) and type (B); and it has a polynomial‐space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Outsourcing and scheduling for two-machine ordered flow shop scheduling problems

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement p_j, and machine i a characteristic q_i. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, p_j/q_i. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{p_j, q_i} (min{p_j, q_i}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.     

Polynomial reduction of time-space scheduling to time scheduling

We study the University Course Timetabling Problem (UCTP). In particular we deal with the following question: is it possible to decompose UCTP into two problems, namely, (i) a time scheduling, and (ii) a space scheduling. We have arguments that it is not possible. Therefore we study UCTP with the assumption that each room belongs to exactly one type of room. A type of room is a set of rooms, which have similar properties. We prove that in this case UCTP is polynomially reducible to time scheduling. Hence we solve UCTP with the following method: at first we solve time scheduling and subsequently we solve space scheduling with a polynomial O(n³) algorithm. In this way we obtain a radical (exponential) speed-up of algorithms for UCTP. The method was applied at P.J. Šafárik University.     

A note on scheduling to meet two min-sum objectives

We consider a single machine scheduling problem with two min-sum objective functions: the sum of completion times and the sum of weighted completion times. We propose a simple polynomial time (1+(1/γ),1+γ)-approximation algorithm, and show that for γ>1, there is no (x,y)-approximation with 1<x<1+(1/γ) and 1<y<1+(γ-1)/(2+γ).     

Scheduling data transfers in a network and the set scheduling problem

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. In particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. We show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. Moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum.     

Computational complexity of some scheduling problems with multiprocessor tasks

The paper is concerned with scheduling problems with multiprocessor tasks and presents conditions under which such problems can be solved in polynomial time. The application of these conditions is illustrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem with a UET task system, two parallel processors, the criterion of total completion time, and precedence constraints in the form of out-trees.     

Two-machine flow shop scheduling problem with an outsourcing option

We consider a two-machine flow shop problem in which each job is processed through an in-house system or outsourced to a subcontractor. A schedule is established for the in-house jobs, and performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and total outsourcing costs. We show that the problem is NP-hard in the ordinary sense. We consider a special case in which each job has a processing requirement, and each machine a characteristic value. In this case, the time a job occupies a machine is equal to the job’s processing requirement plus a setup time equal to the characteristic value of that machine. We introduce some optimality conditions and present a polynomial-time algorithm to solve the special case.     

The counting complexity of a simple scheduling problem

Let T be a set of tasks. Each task has a non-negative processing time and a deadline. The problem of determining whether or not there is a schedule of the tasks in T such that a single machine can finish processing each of them before its deadline is polynomially solvable. We prove that counting the number of schedules satisfying this condition is #P-complete.     

Vehicle scheduling with combinable delivery and pickup operations

Motivated by the logistics operations in an express delivery company, we develop and study a new scheduling model. The problem seems similar to scheduling with sequence-dependent setup times and scheduling with release times, however, the ability to combine or separate the job operations makes our problem unique.     

Online weighted flow time and deadline scheduling

In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|r_i,pmtn|∑w_iF_i. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling.     

Pattern scheduling

A pattern is a sequence of disjoint intervals on a circle together with fixed distances between these intervals. The intervals may be interpreted as tasks of a job which is produced perio-dically on one machine. How shouldr patterns be moved relative to each other to minimize the maximum overlapping of intervals (machines needed)? An enumerative procedure for solving this problem is given.     

Batch scheduling and common due-date assignment on a single machine

We consider the problem of scheduling n groups of jobs on a single machine where three types of decisions are combined: scheduling, batching and due-date assignment. Each group includes identical jobs and may be split into batches; jobs within each batch are processed jointly. A sequence independent machine set-up time is needed between each two consecutively scheduled batches of different groups. A due-date common to all jobs has to be assigned. A schedule specifies the size of each batch, i.e. the number of jobs it contains, and a processing order for the batches. The objective is to determine a value for the common due-date and a schedule so as to minimize the sum of the due date assignment penalty and the weighted number of tardy jobs. Several special cases of this problem are shown to be ordinary NP-hard. Some cases are solved in O(n log n) time. Two pseudopolynomial dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.     

Batch scheduling and common due date assignment problem: An NP-hard case

An important special case of the problem studied in Cheng and Kovalyov (1996) arises when there are equal set-up times and equal job processing times. Computational complexity of this case was indicated to be open, however. I prove its NP-hardness.     

The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect

In this paper, we analyse the single machine maximum lateness minimization scheduling problem with the processing time based aging effect, where the processing time of each job is described by a non-decreasing function dependent on the sum of the normal processing times of preceded jobs. The computational complexity of this problem was not determined. However, we show it is strongly NP-hard by proving the strong NP-hardness of the single machine maximum completion time minimization problem with this aging model and job deadlines. Furthermore, we determine the boundary between polynomially solvable and NP-hard cases.     

Some notes on split Newton iterative algorithm

In this study, a parameterized split Newton method is derived by using the accelerating technique. Convergence and error estimates of the method are obtained. In practical application, the proposed method can give a better result in view of computational CPU time. Numerical examples on several partial differential equations are shown to illustrate our findings. Copyright © 2015 John Wiley & Sons, Ltd.     

需要安装时间的两台多功能机排序问题的计算复杂性

提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都相等的情况,给出一个多项式时间的最优算法-奇偶算法,从而证明此问题是多项式时间可解的.