Approximation algorithms for scheduling unrelated parallel machines

We consider the following scheduling problem. There arem parallel machines andn independent jobs. Each job is to be assigned to one of the machines. The processing of jobj on machinei requires timep _ij . The objective is to find a schedule that minimizes the makespan.Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints.In contrast to our main result, we prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unlessP = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times.A preliminary version of this paper appeared in theProceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science (Computer Society Press of the IEEE, Washington, D.C., 1987) pp. 217–224.     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

A novel parallel quantum genetic algorithm for stochastic job shop scheduling

In this paper, a Novel Parallel Quantum Genetic Algorithm (NPQGA) is proposed for the stochastic Job Shop Scheduling Problem with the objective of minimizing the expected value of makespan, where the processing times are subjected to independent normal distributions. Based on the parallel evolutionary idea and some concepts of quantum theory, we simulate a model of parallel quantum computation. In this frame, there are some demes (sub-populations) and some universes (groups of populations), which are structured in super star-shaped topologies. A new migration scheme based on penetration theory is developed to control migration rate and direction adaptively between demes, and a novel quantum crossover strategy is devised among universes. The quantum evolution is executed in every deme by applying some improvement operators (the coding mechanism aiming at job shop, the new quantum rotation angle and the catastrophe operator). Experiment results show NPQGA's effectiveness and applicability.     

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound

A stochastic branch-and-bound technique for the solution of stochastic single-machine-tardiness problems with job weights is presented. The technique relies on partitioning the solution space and estimating lower and upper bounds by sampling. For the lower bound estimation, two different types of sampling (“within” and “without” the minimization) are combined. Convergence to the optimal solution (with probability one) can be demonstrated. The approach is generalizable to other discrete stochastic optimization problems. In computational experiments with the single-machine-tardiness problem, the technique worked well for problem instances with a relatively small number of jobs; due to the enormous complexity of the problem, only approximate solutions can be expected for a larger number of jobs. Furthermore, a general precedence rule for the single-machine scheduling of jobs with uncertain processing times has been derived, essentially saying that “safe” jobs are to be scheduled before “unsafe” jobs.     

Multi-resource allocation in stochastic project scheduling

We propose a resource allocation model for project scheduling. Our model accommodates multiple resources and decision-dependent activity durations inspired by microeconomic theory. First, we elaborate a deterministic problem formulation. In a second stage, we enhance this model to account for uncertain problem parameters. Assuming that the first and second moments of these parameters are known, the stochastic model minimises an approximation of the value-at-risk of the project makespan. As a salient feature, our approach employs a scenario-free formulation which is based on normal approximations of the activity path durations. We extend our model to situations in which the moments of the random parameters are ambiguous and describe an iterative solution procedure. Extensive numerical results are provided.     

Optimal policies in stochastic shop scheduling

In this paper a survey is presented of some of the recent results in stochastic open shop, flow shop and job shop scheduling. The distributions of the processing times of the jobs are known in advance, but the actual processing times are not known in advance. The jobs may have due dates. Optimal preemptive and nonpreemptive policies are determined for the minimization of various objective functions, such as the expected makespan, the expected flow time and the expected number of late jobs. The effect of various degrees of dependence between the processing times of any given job on the various machines is investigated. Under given conditions bounds are obtained for the expected makespan in the different models.Partially supported by the National Science Foundation (NSF), under grant ECS-8115344 with the Georgia Institute of Technology.     

Approximation of the supply scheduling problem

The supply scheduling problem consists in finding a minimum cost delivery plan from a set of providers to a manufacturing unit, subject to given bounds on the shipment sizes and subject to the demand at the manufacturing unit. We provide a fully polynomial time approximation scheme for this problem.     

Approximation theorems for set-valued stochastic integrals

The article is devoted to new properties of Aumann, Lebesgue, and Itô set-valued stochastic integrals considered in papers [1 Kisielewicz, M. (2014). Properties of generalized set-valued stochastic integrals. Discuss. Math. (DICO) 34:131–147. [Google Scholar],2 Kisielewicz, M., Michta, M. (2017). Integrably bounded set-valued stochastic integrals. J. Math. Anal. Appl. 449:1893–1910.[Crossref], [Web of Science ®] , [Google Scholar]]. In particular, it contains some approximation theorems for Aumann and Itô set-valued stochastic integrals. Hence, in particular, it follows that Aumann and Lebesgue set-valued stochastic integrals cover a.s., both for measurable and IF-nonanticipative integrably bounded set-valued stochastic processes.     

Approximation algorithms for problems in scheduling with set-ups

In this paper, we present new approximation results for the offline problem of single machine scheduling with sequence-independent set-ups and item availability, where the jobs to be scheduled are independent (i.e., have no precedence constraints) and have a common release time.We present polynomial-time approximation algorithms for two versions of this problem. In the first version, the input includes a weight for each job, and the goal is to minimize the total weighted completion time. On any input, our algorithm produces a schedule whose total weighted completion time is within a factor 2 of optimal for that input.In the second version, the input includes a due date for each job, and the goal is to minimize the maximum lateness of any job. On any input, our algorithm produces a schedule with the following performance guarantee: the maximum lateness of a job is at most the maximum lateness of the optimal schedule on a machine that runs at half the speed of our machine.     

Approximation of eigencharacteristics in nearly-completely decomposable stochastic systems

We analyse the accuracy with which the eigensystem of a nearly-completely decomposable stochastic matrix may be expressed as a function of the eigensystems of its principal submatrices and of the maximum degree of coupling between these submatrices.     

Assignment and scheduling in parallel matrix factorization

We consider the problem of factoring a dense n×n matrix on a network consisting of P MIMD processors, with no shared memory, when the network is smaller than the number of elements in the matrix (P<n²). The specific example analyzed is a computational network that arises in computing the LU, QR, or Cholesky factorizations. We prove that if the nodes of the network are evenly distributed among processors and if computations are scheduled by a round-robin or a least-recently-executed scheduling algorithm, then optimal order of speedup is achieved. However, such speedup is not necessarily achieved for other scheduling algorithms or if the computation for the nodes is inappropriately split across processors, and we give examples of these phenomena. Lower bounds on execution time for the algorithm are established for two important node-assignment strategies.     

Stochastic programming approaches to stochastic scheduling

Practical scheduling problems typically require decisions without full information about the outcomes of those decisions. Yields, resource availability, performance, demand, costs, and revenues may all vary. Incorporating these quantities into stochastic scheduling models often produces diffculties in analysis that may be addressed in a variety of ways. In this paper, we present results based on stochastic programming approaches to the hierarchy of decisions in typical stochastic scheduling situations. Our unifying framework allows us to treat all aspects of a decision in a similar framework. We show how views from different levels enable approximations that can overcome nonconvexities and duality gaps that appear in deterministic formulations. In particular, we show that the stochastic program structure leads to a vanishing Lagrangian duality gap in stochastic integer programs as the number of scenarios increases.This author's work was supported in part by the National Science Foundation under Grants ECS 88-15101, ECS 92-16819, and SES 92-11937.This author's work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-5489 and by the UK Engineering and Physical Sciences Research Council under Grants J90855 and K17897.     

Coordination mechanisms for parallel machine scheduling

We consider coordination mechanisms for the distributed scheduling of n jobs on m parallel machines, where each agent holding a job selects a machine to process his/her own job. Without a central authority to construct a schedule, each agent acts selfishly to minimize his/her own disutility, which is either the completion time of the job or the congestion time (defined as the load of the machine on which the job is scheduled). However, the overall system performance is measured by a central objective which is quite different from the agents’ objective. In the literature, makespan is often considered as the central objective. We, however, investigate problems with other central objectives that minimize the total congestion time, the total completion time, the maximum tardiness, the total tardiness, and the number of tardy jobs. The performance deterioration of the central objective by a lack of central coordination, referred to as the price of anarchy, is typically measured by the maximum ratio of the objective function value of a Nash equilibrium schedule versus that of an optimal, coordinated schedule. In this paper we give bounds for the price of anarchy for the above objectives. For problems with due date related objectives, the price of anarchy may not be defined since the optimal value may be zero. In this case, we consider the maximum difference between the objective function value of an equilibrium schedule and the optimal value. We refer to this metric as the absolute price of anarchy and analyze its lower and upper bounds.     

Minimizing earliness and tardiness costs in stochastic scheduling

We address the single-machine stochastic scheduling problem with an objective of minimizing total expected earliness and tardiness costs, assuming that processing times follow normal distributions and due dates are decisions. We develop a branch and bound algorithm to find optimal solutions to this problem and report the results of computational experiments. We also test some heuristic procedures and find that surprisingly good performance can be achieved by a list schedule followed by an adjacent pairwise interchange procedure.