Makespan minimization in online scheduling with machine eligibility

In this paper we provide a survey of online scheduling in parallel machine environments with machine eligibility constraints and the makespan as objective function. We first give a brief overview of the different parallel machine environments and then survey the various types of machine eligibility constraints, including tree-hierarchical processing sets, Grade of Service processing sets, interval processing sets, and nested processing sets. We furthermore describe the relationships between the various different types of processing sets. We proceed with describing two basic online scheduling paradigms, namely online over list and online over time. For each one of the two paradigms we survey all the results that have been recorded in the literature with regard to each type of machine eligibility constraints. We obtain also several extensions in various directions. In the concluding section we describe the most important open problems in this particular area.     

Makespan minimization in machine dominated flowshop

In a flowshop scheduling problem, a set of jobs is processed by a set of machines. The jobs follow the same sequence in all machines. We study the flowshop scheduling problem under a new case of machine dominance that is often found in the manufacturing of computers and electronic devices. We provide a formula for makespan value for a given sequence, show that the makespan value depends only on certain jobs in the sequence, and present an algorithm that finds a sequence with minimum makespan. Numerical examples of the solution approaches are provided.     

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.     

Makespan minimization for parallel machines scheduling with multiple availability constraints

The problem of makespan minimization for parallel machines scheduling with multiple planned nonavailability periods in the case of resumable jobs is considered. In the current state of the literature, there is a limited number of models and algorithms dealing with this problem and only for very small problem size, and nonavailability limited to some machines. The problem is first formulated as a mixed integer linear programming model and optimally solved using CPLEX for small to moderately large size problems with multiple availability constraints on all machines. An implicit enumeration algorithm using the lexicographic order is then designed to solve large-scale problems. Numerical results are obtained for several experiments and they show the validity and performance improvements procured by both the MILP model and the new enumeration algorithm.     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.     

机器和工人都有加工资质约束的平行机排序问题研究

研究一类新型的平行机排序问题, 即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下, 如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_max. 将研究工件加工时间均为单位时间的情况, 通过建立网络流模型以及采用二分搜索技术, 可以在多项式时间内精确地求解上述问题, 算法复杂度为O(n^{3}logn). 同时提供了一种基于双重动态柔性选择\,(DDFS)\,策略的启发式算法,可以获得较好的排序效果, 算法复杂度为O(n^{2}).     

An improved algorithm for online machine minimization

The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines — each job $j$ arrives at its release time $r_j$, has to be processed for $p_j$ time units, and must be completed by its deadline $d_j$. The goal is to minimize the number of machines the algorithm uses. We improve the $O(logm)$-competitive algorithm by Chen, Megow and Schewior (SODA 2016) and provide an $O\left(\frac{logm}{loglogm}\right)$-competitive algorithm.     

Makespan minimization for two parallel machines with an availability constraint

In this paper, we consider a two parallel machine problem where one machine is not available during a time period. The unavailable time period is fixed and known in advance. A machine is not available probably because it needs preventive maintenance or periodical repair. The objective of the problem is to minimize the makespan. For both nonresumable and resumable cases, we partition the problem into four sub-problems, each of which is solved optimally by an algorithm. Although all the algorithms have exponential time complexities, they are quite efficient in solving large-sized problems.     

具有机器适用限制的分布式置换流水车间问题的模型与算法

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.     

Scheduling with controllable release dates and processing times: Makespan minimization

The paper deals with the single-machine scheduling problem in which job processing times as well as release dates are controllable parameters and they may vary within given intervals. While all release dates have the same boundary values, the processing time intervals are arbitrary. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amount. The objective is to minimize the makespan together with the total compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(n²) algorithm for the case of equal release date compression costs and equal processing time compression costs. For the bicriteria version of the latter problem with agreeable processing times, we suggest an O(n²) algorithm that constructs the breakpoints of the efficient frontier.     

Scheduling unit-length jobs with machine eligibility restrictions

We consider uniform parallel machine scheduling problems with unit-length jobs where every job is only allowed to be processed on a specified subset of machines. We develop efficient methods to solve problems with various objectives, including minimizing a total tardiness function, a maximum tardiness function, total completion time, the number of tardy jobs, the makespan, etc.     

Makespan minimization in open shops: A polynomial time approximation scheme

In this paper, we demonstrate the existence of a polynomial time approximation scheme for makespan minimization in the open shop scheduling problem with an arbitrary fixed numberm of machines. For the variant of the problem where the number of machines is part of the input, it is known that the existence of an approximation scheme would implyP = NP. Hence, our result draws a precise separating line between approximable cases (i.e., withm fixed) and non-approximable cases (i.e., withm part of the input) of this shop problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by the DIMANET/PECO Program of the European Union.Supported by a research fellowship of the Euler Institute for Discrete Mathematics and its Applications. This research was done while Gerhard Woeginger was with the Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB Eindhoven, The Netherlands.     

Makespan minimization for two parallel machines scheduling with a periodic availability constraint: Mathematical programming model,average-case analysis,and anomalies

A mathematical programming model is proposed for the two parallel machines scheduling problem where one machine is periodically unavailable, jobs are non-preemptive, and the objective is minimizing the makespan. The model is established by transforming the two parallel machine setting into a single machine setting. Average-case analyses of the classical Longest Processing Time first (LPT) algorithm and the List Scheduling (LS) are presented. Computational experiments show that the LPT algorithm beats the LS algorithm in all the 96 combinations of two main parameters from an average-case error point of view and that the average-case error of the LPT algorithm is less than 2% when the number of jobs is greater than twenty. Unexpectedly, there also exist instances showing that the LS algorithm may beat the LPT algorithm from the average-case error point of view.     

FPTAS for half-products minimization with scheduling applications

A special class of quadratic pseudo-boolean functions called “half-products” (HP) has recently been introduced. It has been shown that HP minimization, while NP-hard, admits a fully polynomial time approximation scheme (FPTAS). In this note, we provide a more efficient FPTAS. We further show how an FPTAS can also be derived for the general case where the HP function is augmented by a problem-dependent constant and can justifiably be assumed to be nonnegative. This leads to an FPTAS for certain partitioning type problems, including many from the field of scheduling.     

Uniform machine scheduling with machine available constraints

1.IntroductionIntheclassicalparallelmachineschedulingareaweassumethatmachinesarealwaysavailable.However,aspointedin[1],inrealindustrysettingsthisassumptionmaynotbetrue.Forexample,machinesmaynotalwaysbeavailablebecauseoftheirpreventivemaintenanceduringtheschedulingperiod.Thatistosay,eachmachineiisunavailablefromsibuntilrib(05sib5rib),where0SkSm,withmbeingthenumberofunavailabilityperiodsformachineiduringtheplanninghorizon.Inotherwords,somepapersstatethatmachinesareavailableintimewindows,whichi…     

目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法

本文研究了两台机器带柔性维修时间限制的排序问题,其中第一台机器在固定的时间内必须进行维修,而第二台机器一直可用,目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题,我们给出了一个性能比为的近似算法,并证明了该性能比是紧的。     

Single machine scheduling with semi-resumable machine availability constraints

This paper considers the semi-resumable model of single machine scheduling with a non-availability period. The machine is not available for processing during a given time interval. A job cannot be completed before the non-availability period will have to partially restart after the machine has become available again. For the problem with objective of minimizing makespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed. For the problem with objective of minimizing total weighted completion time, an approximation algorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latter problem are also considered, and improved algorithms are given.     

Uniform parallel machine scheduling problems with fixed machine cost

This paper considers two uniform parallel machine scheduling problems with fixed machine cost under the background of cloud manufacturing. The goal is to minimize the makespan with a given budget of total cost, \(\hat{U}\). All the jobs are homogeneous, i.e., the processing times of the jobs are identical. Non-preemptive and preemptive problems are studied. For the non-preemptive problem, we give a \(2[1+1{/}(h-1)]\)-approximation algorithm, where h is the number of the machine which can not be selected the first time. For the preemptive problem, we give an algorithm whose worst-case bound equals to \(1+1{/}(h-1)\). Preliminary experimental results indicate that the proposed algorithms are reasonably accurate compared with the lower bounds.