An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint

We study the problem of scheduling n jobs in a two-machine flow shop where the second machine is not available for processing during a given time interval. A resumable scenario is assumed, i.e., if a job cannot be finished before the down period it is continued after the machine becomes available again. The objective is to minimize the makespan. The best fast approximation algorithm for this problem guarantees a relative worst-case error bound of 4/3. We present an improved algorithm with a relative worst-case error bound of 5/4.     

Polynomial time approximation algorithms for proportionate open‐shop scheduling

This paper deals with the presentation of polynomial time (approximation) algorithms for a variant of open‐shop scheduling, where the processing times are only machine‐dependent. This variant of scheduling is called proportionate scheduling and its applications are used in many real‐world environments. This paper develops three polynomial time algorithms for the problem. First, we present a polynomial time algorithm that solves the problem optimally if , where n and m denote the numbers of jobs and machines, respectively. If, on the other hand, , we develop a polynomial time approximation algorithm with a worst‐case performance ratio of that improves the bound existing for general open‐shops. Next, in the case of , we take into account the problem under consideration as a master problem and convert it into a simpler secondary approximation problem. Furthermore, we formulate both the master and secondary problems, and compare their complexity sizes. We finally present another polynomial time algorithm that provides optimal solution for a special case of the problem where .     

Flexible open shop scheduling problem to minimize makespan

This study investigates the static and dynamic versions of the flexible open shop scheduling problem with the goal of minimizing makespan. The asymptotic optimality of the general dense scheduling (GDS) algorithm is proven by the boundedness hypothesis. For large-scale problems, the GDS-based heuristic algorithms are presented to accelerate convergence. For moderate-scale problems, the differential evolution algorithm is employed to obtain high-quality solutions. A series of random experiments are conducted to demonstrate the effectiveness of the proposed algorithms.     

A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint

We study the problem of scheduling n preemptable jobs in a two-machine flow shop where the first machine is not available for processing during a given time interval. The objective is to minimize the makespan. We propose a polynomial-time approximation scheme for this problem. The approach is extended to solve the problem in which the second machine is not continuously available.     

Performance analysis of rotation schedule and improved strategy for open shop problem to minimise makespan

This article addresses the open shop scheduling problem with the objective to minimise the maximum completion time, or makespan. Both asymptotical analysis and worst case analysis are conducted for the heuristic, rotation schedule (RS) algorithm. In the asymptotical analysis, we prove that the RS algorithm is asymptotically equal to the optimal solution when the problem size is large enough. In the worst case analysis, we show that the tight worst case performance ratio of RS algorithm is equal to the machine number m. To accelerate the convergence of the RS algorithm for medium size problems, the improved version of the heuristic, the modified RS (MRS) algorithm is presented. At the end of this article, the asymptotical optimality of the RS algorithm and the practical effectiveness of the MRS algorithm are shown by numerical simulations.     

Efficient approximation algorithms for shortest cycles in undirected graphs

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k+2 for odd k, in time . Thus, in general, it yields a approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,…,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n²logn(logn+logM)).     

批量流水线调度问题的混合差分进化算法

针对E/T指标的批量流水线调度问题,提出了差分进化调度算法。该算法采用基于实数的编码方式,利用最优目标个体的扰动产生变异个体,通过变异个体与目标个体的交叉产生试验个体,提高了最优目标个体信息共享,并结合模拟退火算法给出了两种混合求解策略。仿真试验表明了所得算法的可行性和高效性。     

Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization

This paper proposes two constructive heuristics, i.e. HPF1 and HPF2, for the blocking flow shop problem in order to minimize the total flow time. They differ mainly in the criterion used to select the first job in the sequence since, as it is shown, its contribution to the total flow time is not negligible. Both procedures were combined with the insertion phase of NEH to improve the sequence. However, as the insertion procedure does not always improve the solution, in the resulting heuristics, named NHPF1 and NHPF2, the sequence was evaluated before and after the insertion to keep the best of both solutions. The structure of these heuristics was used in Greedy Randomized Adaptive Search Procedures (GRASP) with variable neighborhood search in the improvement phase to generate greedy randomized solutions. The performance of the constructive heuristics and of the proposed GRASPs was evaluated against other heuristics from the literature. Our computational analysis showed that the presented heuristics are very competitive and able to improve 68 out of 120 best known solutions of Taillard’s instances for the blocking flow shop scheduling problem with the total flow time criterion.     

On approximation algorithms for the terminal Steiner tree problem

The terminal Steiner tree problem is a special version of the Steiner tree problem, where a Steiner minimum tree has to be found in which all terminals are leaves. We prove that no polynomial time approximation algorithm for the terminal Steiner tree problem can achieve an approximation ratio less than (1−o(1))lnn unless NP has slightly superpolynomial time algorithms. Moreover, we present a polynomial time approximation algorithm for the metric version of this problem with a performance ratio of 2ρ, where ρ denotes the best known approximation ratio for the Steiner tree problem. This improves the previously best known approximation ratio for the metric terminal Steiner tree problem of ρ+2.     

A genetic algorithm for the proportionate multiprocessor open shop

The multiprocessor open shop (MPOS) scheduling problem is NP-complete, a category of hard combinatorial optimization problems that have not received much attention in the literature. In this work, a special MPOS—a proportionate one—is introduced for the first time. Two original mixed integer programming formulations for the proportionate MPOS are developed and their complexity is discussed. Due to the complexity of the MPOS, this paper develops a compu-search methodology (a genetic algorithm (GA)) to schedule the shop with the objective of minimizing the makespan. In this novel GA, a clever chromosome representation of a schedule is developed that succinctly encodes a schedule of jobs across multiple stages. The innovative design of this chromosome enables any permutation of its genes to yield a feasible solution. This simple representation of an otherwise very complex schedule enables the genetic operators of crossover and mutation to easily manipulate a schedule as the algorithm iteratively searches for better schedules. A testbed of difficult instances of the problem are created to evaluate the performance of the GA. The solution for each instance is compared with a derived lower bound. Computational results reveal that the algorithm performs extremely well, demonstrating its potential to efficiently schedule MPOS problems. More importantly, successful experiments on large-scale problem instances suggest the readiness of the GA for industrial use.     

Constructive heuristic algorithms for the open shop problem

In this paper we consider constructive heuristic algorithms for the open shop problem with minimization of the schedule length. By means of investigations of the structure of a feasible solution two types of heuristic algorithms are developed: construction of a rank-minimal schedule by solving successively weighted maximum cardinality matching problems and construction of an approximate schedule by applying insertion techniques combined with beam search. All presented algorithms are tested on benchmark problems from the literature. Our computational results demonstrate the excellent solution quality of our insertion algorithm, especially for greater job and machine numbers. For 29 of 30 benchmark problems with at least 10 jobs and 10 machines we improve the best known values obtained by tabu search.     

Improved approximation algorithms for the Max Edge-Coloring problem

The Max Edge-Coloring problem asks for a proper edge-coloring of an edge-weighted graph minimizing the sum of the weights of the heaviest edges in the color classes. In this paper we present a PTAS for trees and a 1.74-approximation algorithm for bipartite graphs; we also adapt the last algorithm to one for general graphs of the same, asymptotically, approximation ratio.     

A new particle swarm optimization for the open shop scheduling problem

This paper presents a new particle swarm optimization (PSO) for the open shop scheduling problem. Compared with the original PSO, we modified the particle position representation using priorities, and the particle movement using an insert operator. We also implemented a modified parameterized active schedule generation algorithm (mP-ASG) to decode a particle position into a schedule. In mP-ASG, we can reduce or increase the search area between non-delay schedules and active schedules by controlling the maximum delay time allowed. Furthermore, we hybridized our PSO with beam search. The computational results show that our PSO found many new best solutions of the unsolved problems.     

Heuristic algorithms for two machine re-entrant flow shop

This paper focuses on a two machine re-entrant flow shop scheduling problem with the objective of minimizing makespan. In the re-entrant flow shop considered here, each job has the processing route (M₁, M₂, M₁, M₂, …, M₁, M₂). We present heuristic algorithms, some are modified from existing algorithms and some are newly developed. Extensive computational experiments are performed to evaluate the performance of the heuristics. Results of the experiments show that the performance of heuristics is significantly affected by the distribution of workloads on machines and some of them are excellent.     

On single-walk parallelization of the job shop problem solving algorithms

New parallel objective function determination methods for the job shop scheduling problem are proposed in this paper, considering makespan and the sum of jobs execution times criteria, however, the methods proposed can be applied also to another popular objective functions such as jobs tardiness or flow time. Parallel Random Access Machine (PRAM) model is applied for the theoretical analysis of algorithm efficiency. The methods need a fine-grained parallelization, therefore the approach proposed is especially devoted to parallel computing systems with fast shared memory (e.g. GPGPU, General-Purpose computing on Graphics Processing Units).     

Multiterminal global routing: A deterministic approximation scheme

We consider the problem of routing multiterminal nets in a two-dimensional gate-array. Given a gate-array and a set of nets to be routed, we wish to find a routing that uses as little channel space as possible. We present a deterministic approximation algorithm that uses close to the minimum possible channel space. We cast the routing problem as a new form of zero-one multicommodity flow, an integer-programming problem. We solve this integer program approximately by first solving its linear-program relaxation and then rounding any fractions that appear in the solution to the linear program. The running time of the rounding algorithm is exponential in the number of terminals in a net but polynomial in the number of nets and the size of the array. The algorithm is thus best suited to cases where the number of terminals on each net is small.This work was done while the authors were with the Computer Science Division, University of California at Berkeley. The work of Prabhakar Raghavan was supported by an IBM Doctoral Fellowship, and the work of Clark Thompson was supported by a California State MICRO grant (AT&T Foundation).     

Solving the flow shop problem by parallel programming

The matter of using scheduling algorithms in parallel computing environments is discussed in this paper. There are proposed methods of parallelizing the criterion function calculations for a single solution and a group of concentrated solutions (local neighborhood) dedicated to being used in metaheuristic approaches. Also a parallel scatter-search metaheuristic is proposed as a multiple-thread approach. Computational experiments are done for the flow shop, the classic NP-hard problem of the combinatorial optimization.     

求解批量流水线调度问题的和声算法

针对以最大完工时间和总流经时间为目标的批量流水线调度问题,提出了改进的和声调度算法。该算法采用基于最大位置值(LPV)规则的编码方式,使具有连续性质的和声算法应用于求解调度问题;提出新的初始化方法,应用了多种群进化的思想更新和声库,并结合和声算法和模拟退火算法各自的特点,给出了两种混合调度算法。仿真实验表明所提算法的可行性和有效性。