Using column generation to solve parallel machine scheduling problems with minmax objective functions

In this paper we consider the parallel machine scheduling problem of minimizing an objective function of the minmax type, like maximum lateness, subject to release dates, deadlines, and/or generalized precedence constraints. We use a destructive strategy to compute a lower bound. Here we test the feasibility of a decision problem by applying column generation to compute a bound on the number of machines that we need to feasibly accommodate all jobs. After having derived the lower bound, we try to find a matching upper bound by identifying a feasible schedule with objective function value equal to this lower bound. Our computational results show that our lower bound is so strong that this is almost always possible. We are able to solve problems with up to 160 jobs and 10 machines in 10 minutes on average.     

Polynomial-time approximation schemes for scheduling problems with time lags

We identify two classes of machine scheduling problems with time lags that possess Polynomial-Time Approximation Schemes (PTASs). These classes together, one for minimizing makespan and one for minimizing total completion time, include many well-studied time lag scheduling problems. The running times of these approximation schemes are polynomial in the number of jobs, but exponential in the number of machines and the ratio between the largest time lag and the smallest positive operation time. These classes constitute the first PTAS results for scheduling problems with time lags.     

Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects

In this paper, we study an unrelated parallel machine scheduling problem with setup time and learning effects simultaneously. The setup time is proportional to the length of the already processed jobs. That is, the setup time of each job is past-sequence-dependent. The objectives are to minimize the total absolute deviation of job completion times and the total load on all machines, respectively. We show that the proposed problem is polynomially solvable. We also discuss two special cases of the problem and show that they can be optimally solved by lower order algorithms.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

A new ILS algorithm for parallel machine scheduling problems

This paper addresses the non-preemptive scheduling problem of scheduling jobs on identical parallel machines to minimize the maximum completion time or makespan. The problem has been proved to be NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a new methodology to obtain near-optimal solutions. We formulate the problem as an integer programming and then propose a new iterated local search (ILS) algorithm based on a variable number of cyclic exchanges to solve it. The properties of the solutions are derived and the results are used to improve the computational efficiency of our algorithm. Computational experiments show that the cyclic exchange neighborhood embedded in an iterated local search framework is effective for solving the scheduling problems with up to 1000 jobs and 40 machines within a reasonable amount of computation time. Received: April 2005 / Accepted: January 2006     

含换模时间的平行机调度问题研究

在工厂实际生产中,模具的换模时间在生产调度中不可忽略。为了更合理地研究平行机车间调度问题,本文将存在序依赖的换模时间考虑进调度模型之中,同时以最小完工时间和最小拖期时间为目标,在经典遗传算法的基础上,对算法选择算子以及交叉变异概率进行改进,避免早熟现象的发生。通过计算结果的比较,证明本文中调度模型更符合实际生产情况,改进后的算法能够得出更高质量的解,且求解效率更高。     

启发式列生成算法求解带恶化效应的同构并行机调度问题

针对实际生产中广泛存在的一类带恶化效应的同构并行机调度问题,以最小化最大完工时间为优化目标,构建该问题的整数规划模型,并提出一种启发式列生成算法(HCGA)进行求解.在HCGA中,首先,利用Dantzig-Wolfe分解方法,将原问题分解为一个主问题(MP)和多个子问题;然后,设计启发式算法获得初始列,其中每列为一台机器上的一个调度方案,基于初始列构建限制主问题(RMP)模型;接着,设计快速有效的动态规划算法求解子问题,以得到需添加至RMP的列集,同时,考虑传统列生成算法收敛速度较慢,设计一系列方法来加速列生成过程;最后,基于所获取的MP线性松弛解,设计深潜启发式算法确定原问题的整数解.HCGA与商用求解器GUROBI的对比实验结果表明,HCGA可在较短时间内获得更优的解.     

heuristics for parallel machine scheduling with delivery times

A parallel machine scheduling problem is considered in which each job has a processing time and a delivery time. The objective is to find a schedule which minimizes the time by which all jobs are delivered. For a single machine this problem is easily solved in polynomial time, form2 machines it becomes NP-hard. Several heuristics using list scheduling as a subroutine are proposed and a tight worst-case analysis is given. The best one of our heuristics has a worst-case performance guarantee of 2–2/(m+1). For the on-line case we give a heuristic with the (best possible) worst-case performance of two.This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.     

Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems

This research compares the performance of various heuristics and one metaheuristic for unrelated parallel machine scheduling problems. The objective functions to be minimized are makespan, total weighted completion time, and total weighted tardiness. We use the least significant difference (LSD) test to identify robust heuristics that perform significantly better than others for a variety of parallel machine environments with these three performance measures. Computational results show that the proposed metaheuristic outperforms other existing heuristics for each of the three objectives when run with a parameter setting appropriate for the objective.     

Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems

Mixed integer programming (MIP) formulations for scheduling problems can be classified based on the decision variables upon which they rely. In this paper, four different MIP formulations based on four different types of decision variables are presented for various parallel machine scheduling problems. The goal of this research is to identify promising optimization formulation paradigms that can subsequently be used to either (1) solve larger practical scheduling problems of interest to optimality and/or (2) be used to establish tighter lower solution bounds for those under study. We present the computational results and discuss formulation efficacy for total weighted completion time and maximum completion time problems for the identical parallel machine case.     

Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times

This paper considers ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Two objects of minimizing the latest job completion time and minimizing the latest machine completion time are studied. For the first objective, we present the optimal algorithms for m = 2, 3, 4 machine cases. For m ≥ 5, we propose an algorithm with competitive ratio 2 - 1/(m - 1) while the lower bound is 5/3. For the second objective, the optimal algorithm is also given. Furthermore, for a special case, an algorithm with significantly improved competitive ratio is given.     

An exact algorithm for parallel machine scheduling with conflicts

We consider an extension of classic parallel machine scheduling where a set of jobs is scheduled on identical parallel machines and an undirected conflict graph is part of the input. Each node in the graph represents a job, and an edge implies that its two jobs are conflicting, meaning that they cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time (makespan) is minimized. We present an exact algorithm based on branch and price that combines methods from bin packing, scheduling, and graph coloring, with appropriate modifications. The algorithm has a good computational performance even for parallel machine scheduling without conflicting jobs.     

Approximation schemes for single machine scheduling with non-renewable resource constraints

In this paper we discuss exact and approximation algorithms for scheduling a single machine with additional non-renewable resource constraints. Given the initial stock levels of some non-renewable resources (e.g., raw materials, fuel, money), and time points along with replenishment quantities, a set of resource consuming jobs has to be scheduled on the machine such that there are enough resources for starting each job, and the makespan is minimized. We show that the problem admits a pseudo-polynomial time algorithm when the number of replenishments is not part of the input, and also present an FPTAS when there is only a single resource, and it is replenished only once. We also describe a PTAS for the problem with a constant number of replenishments.     

Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability

This article considers the unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times and machine-dependent processing times. Furthermore, the machine has a production availability constraint to each job. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the total completion time. To solve the problem, a mathematical model for the optimal solution is derived, and hybrid genetic algorithms with three dispatching rules are proposed for large-sized problems. To assess the performance of the algorithms, computational experiments are conducted and evaluated using several randomly generated examples.     

Search tree based approaches for parallel machine scheduling

This article compares two branching schemes for the parallel machine scheduling problem with release dates and tails. Both branching schemes can be used for either complete or incomplete search tree based algorithms. In particular, our study aims to prove the robustness of each of them for several search methods. We experimentally compare the efficiency of the two branching schemes when they are used in a branch-and-bound (BnB) method, in a limited discrepancy search, in a branch-and-greed (BnG) method or in a beam search (BS).     

到达时间依赖于资源分配的单机排序问题*

研究了具有线性退化及学习效应作用下的单机排序问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下最大完工时间极小化问题,给出了相应的最优算法;也考虑了满足工件最大完工时间限制的条件下极小化资源消耗的总量问题,提出最优资源分配方案。     

Multiobjective pseudo‐variable neighborhood descent for a bicriteria parallel machine scheduling problem with setup time

A multiobjective variable neighborhood descent (VND) based heuristic is developed to solve a bicriteria parallel machine scheduling problem. The problem considers two objectives, one related to the makespan and the other to the flow time, where the setup time depends on the sequence, and the machines are identical. The heuristic has a set of neighborhood structures based on swap, remove, and insertion moves. We propose changing the local search inside the VND to a sequential search through the neighborhoods to obtain nondominated points for the Pareto‐front quickly. In the numerical tests, we consider a single‐objective version of the heuristic, comparing the results on 510 benchmark instances to show that it is quite effective. Moreover, new instances are generated in accordance with the literature for the bicriteria problem, showing the ability of the proposed heuristic to return an efficient set of nondominate solutions compared with the well‐known nondominated sorting genetic algorithm II.     

The optimal on-line parallel machine scheduling

This paper investigates on-line parallel machine scheduling problems. We show the optimality of the classical LS algorithm.     

A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity

This paper proposes a two-stage stochastic programming model for the parallel machine scheduling problem where the objective is to determine the machines' capacities that maximize the expected net profit of on-time jobs when the due dates are uncertain. The stochastic model decomposes the problem into two stages: The first (FS) determines the optimal capacities of the machines whereas the second (SS) computes an estimate of the expected profit of the on-time jobs for given machines' capacities. For a given sample of due dates, SS reduces to the deterministic parallel weighted number of on-time jobs problem which can be solved using the efficient branch and bound of M’Hallah and Bulfin [16]. FS is tackled using a sample average approximation (SAA) sampling approach which iteratively solves the problem for a number of random samples of due dates. SAA converges to the optimum in the expected sense as the sample size increases. In this implementation, SAA applies a ranking and selection procedure to obtain a good estimate of the expected profit with a reduced number of random samples. Extensive computational experiments show the efficacy of the stochastic model.     

A hybrid genetic algorithm for parallel machine scheduling with setup times

Journal of Intelligent Manufacturing - This paper addresses the unrelated parallel machine scheduling problem with sequence and machine dependent setup times and machine eligibility constraints....