Handling precedence constraints in scheduling problems by the sequence pair representation

In this paper, we show that sequence pair (SP) representation, primarily applied to the rectangle packing problems appearing in the VLSI industry, can be a solution representation of precedence constrained scheduling. We present three interpretations of sequence pair, which differ in complexity of schedule evaluation and size of a corresponding solution space. For each interpretation we construct an incremental precedence constrained SP neighborhood evaluation algorithm, computing feasibility of each solution in the insert neighborhood in an amortized constant time per examined solution, and prove the connectivity property of the considered neighborhoods. To compare proposed interpretations of SP, we construct heuristic and metaheuristic algorithms for the multiprocessor job scheduling problem, and verify their efficiency in the numerical experiment.     

Multi-neighborhood based path relinking for two-sided assembly line balancing problem

This paper presents a multi-neighborhood based path relinking algorithm (MN-PR) for solving the two-sided assembly line balancing problem. By incorporating an effective local search into a path relinking framework, the proposed MN-PR algorithm integrates a number of distinguishing features, such as a multi-neighborhood based local search procedure, a dedicated path relinking operator to generate new solutions and a strategy to fix an infeasible solution generated by the path relinking procedure to a feasible one. Our proposed MN-PR algorithm is tested on a set of totally 45 public instances widely used in the literature. Comparisons with other reference algorithms show the efficacy of the proposed algorithm in terms of the solution quality. Particularly, the proposed MN-PR algorithm is able to improve the best upper bounds for one instance with 65 tasks and 326 cycle time. This paper also presents an analysis to show the significance of the main components of the proposed algorithm.     

A hybrid algorithm based on variable neighbourhood for the strip packing problem

This paper addresses the strip packing problem, which has a wide range of real-world applications. Our proposed algorithm is a hybrid metaheuristic that combines an improved heuristic algorithm with a variable neighbourhood search. Different neighbourhoods are constructed based on the concept of block patterns. The proposed algorithm has three interesting features. First, a least-waste strategy is used to improve the constructive heuristics. Second, a better sorting sequence is selected to generate an initial solution. Finally, different neighbourhoods are constructed based on block patterns. The computational results from a diverse set of problem instances show that the proposed algorithm performs better than algorithms reported in the literature for most of the problem sets compared.     

Exact algorithms for scheduling programs with shared tasks

We study a scheduling problem where the jobs we have to perform are composed of one or more tasks. If two jobs sharing a non-empty subset of tasks are scheduled on the same machine, then these shared tasks have to be performed only once. This kind of problem is known in the literature under the names of VM-PACKING or PAGINATION. Our objective is to schedule a set of these objects on two parallel identical machines, with the aim of minimizing the makespan. This problem is NP-complete as an extension of the PARTITION problem. In this paper we present three exact algorithms with worst-case time-complexity guarantees, by exploring different branching techniques. Our first algorithm focuses on the relation between jobs sharing one or more symbols in common, whereas the two other algorithms branches on the shared symbols.

     

Multi-start iterated tabu search for the minimum weight vertex cover problem

The minimum weight vertex cover problem (MWVCP) is one of the most popular combinatorial optimization problems with various real-world applications. Given an undirected graph where each vertex is weighted, the MWVCP is to find a subset of the vertices which cover all edges of the graph and has a minimum total weight of these vertices. In this paper, we propose a multi-start iterated tabu search algorithm (MS-ITS) to tackle MWVCP. By incorporating an effective tabu search method, MS-ITS exhibits several distinguishing features, including a novel neighborhood construction procedure and a fast evaluation strategy. Extensive experiments on the set of public benchmark instances show that the proposed heuristic is very competitive with the state-of-the-art algorithms in the literature.     

A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem

This paper addresses a constrained two-dimensional (2D), non-guillotine restricted, packing problem, where a fixed set of small rectangles has to be placed into a larger stock rectangle so as to maximize the value of the rectangles packed. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose also a new fitness function to drive the optimization. The approach is tested on a set of instances taken from the literature and compared with other approaches. The experimental results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

Recoverable robust spanning tree problem under interval uncertainty representations

This paper deals with the recoverable robust spanning tree problem under interval uncertainty representations. A strongly polynomial time, combinatorial algorithm for the recoverable spanning tree problem is first constructed. This problem generalizes the incremental spanning tree problem, previously discussed in literature. The algorithm built is then applied to solve the recoverable robust spanning tree problem, under the traditional interval uncertainty representation, in polynomial time. Moreover, the algorithm allows to obtain several approximation results for the recoverable robust spanning tree problem under the Bertsimas and Sim interval uncertainty representation and the interval uncertainty representation with a budget constraint.     

Exact approaches for the pickup and delivery problem with loading cost

In this paper, we propose a branch-and-cut algorithm and a branch-and-price algorithm to solve the pickup and delivery problem with loading cost (PDPLC), which is a new problem derived from the classic pickup and delivery problem (PDP) by considering the loading cost in the objective function. Applications of the PDPLC arise in healthcare transportation where the objective function is customer-centric or service-based. In the branch-and-price algorithm, we devise an ad hoc label-setting algorithm to solve the pricing problem and employ the bounded bidirectional search strategy to accelerate the label-setting algorithm. The proposed algorithms were tested on a set of instances generated by a common data generator in the literature. The computational results showed that the branch-and-price algorithm outperformed the branch-and-cut algorithm by a large margin, and can solve instances with 40 requests to optimality in a reasonable time frame.     

不完全信息下的一种信用分类方法

本文详细分析了一类典型的不完全信息的信用评价问题,即存在信用参考信息不完全或样本数据较少,以及某些指标数据为区间数等。文章首先考虑具有不完全信用参考信息的情况,在分析这类问题特性的基础上,基于数据包络分析理论(DEA),提出一种以拒绝案例集构造参考单元集的方法,并给出了相应的DEA模型。然后,进一步考虑带有较为复杂区间指标数据这类具有不完全指标信息的信用评价问题,并给出了相应的信用分析方法,最后采用算例说明本文提出方法的合理性。由于所提方法能有效地处理信用信息不完全和指标数据不完全的情况,故其具有较为广泛的实用性。     

Modeling the problem of locating collection areas for urban waste management. An application to the metropolitan area of Barcelona

Reverse logistics problems arising in municipal waste management are both wide-ranging and varied. The usual collection system in UE countries is composed of two phases. First, citizens leave their refuse at special collection areas where different types of waste (glass, paper, plastic, organic material) are stored in special refuse bins. Subsequently, each type of waste is collected separately and moved to its final destination (a recycling plant or refuse dump). The present study focuses on the problem of locating these collection areas. We establish the relationship between the problem, the set covering problem and the MAX-SAT problem and then go on to develop a genetic algorithm and a GRASP heuristic to, respectively, solve each formulation. Finally, the quality of the algorithms is tested in a computational experience with real instances from the metropolitan area of Barcelona, as well as a reduced set of set covering instances from the literature.     

Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm

The blocking flowshop scheduling problem has a strong industrial background but is under-represented in the research literature. In this study, a revised artificial immune system (RAIS) algorithm based on the features of artificial immune systems and the annealing process of simulated annealing algorithms was presented to minimize the makespan in a blocking flowshop. To validate the performance of the proposed RAIS algorithm, computational experiments and comparisons were conducted on the well-known benchmark problems of Taillard used in earlier studies. The experimental results show that the proposed RAIS algorithm outperforms the state-of-art algorithms on the same benchmark problem data set.     

Dynamic Programming and Hill-Climbing Techniques for Constrained Two-Dimensional Cutting Stock Problems

In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. The TDC problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. The proposed algorithm is a hybrid approach in which a depth-first search using hill-climbing strategies and dynamic programming techniques are combined. The algorithm starts with an initial (feasible) lower bound computed by solving a series of single bounded knapsack problems. In order to enhance the first-level lower bound, we introduce an incremental procedure which is used within a top-down branch-and-bound procedure. We also propose some hill-climbing strategies in order to produce a good trade-off between the computational time and the solution quality. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approach. The obtained results are compared to the results published by Alvarez-Valdés et al. (2002).     

Two new robust genetic algorithms for the flowshop scheduling problem

The flowshop scheduling problem (FSP) has been widely studied in the literature and many techniques for its solution have been proposed. Some authors have concluded that genetic algorithms are not suitable for this hard, combinatorial problem unless hybridization is used. This work proposes new genetic algorithms for solving the permutation FSP that prove to be competitive when compared to many other well known algorithms. The optimization criterion considered is the minimization of the total completion time or makespan (_Cmax$C_{\max }$). We show a robust genetic algorithm and a fast hybrid implementation. These algorithms use new genetic operators, advanced techniques like hybridization with local search and an efficient population initialization as well as a new generational scheme. A complete evaluation of the different parameters and operators of the algorithms by means of a Design of Experiments approach is also given. The algorithm's effectiveness is compared against 11 other methods, including genetic algorithms, tabu search, simulated annealing and other advanced and recent techniques. For the evaluations we use Taillard's well known standard benchmark. The results show that the proposed algorithms are very effective and at the same time are easy to implement.     

Efficient Job Scheduling Algorithms with Multi-Type Contentions

In this paper, we consider an interesting generalization of the classic job scheduling problem in which each job needs to compete not only for machines but also for other types of resources. The contentions among jobs for machines and for resources could interfere with each other, which complicates the problem dramatically. We present a family of approximation algorithms for solving several variants of the problem by using a generic algorithmic framework. Our algorithms achieve a constant approximation ratio (i.e., 3) when there is only one type of resources or certain dependency relation exists among multiple types of resources. When the r resources are unrelated, the approximation ratio of our algorithm becomes k+2, where k≤ r is a constant depending on the problem instance. As an application, we also show that our techniques can be easily applied to optical burst switching (OBS) networks to design more efficient wavelength scheduling algorithms.This research was supported in part by an IBM faculty partnership award, and an IRCAF award from SUNY Buffalo.     

Exact solution method to solve large scale integer quadratic multidimensional knapsack problems

In this paper we develop a branch-and-bound algorithm for solving a particular integer quadratic multi-knapsack problem. The problem we study is defined as the maximization of a concave separable quadratic objective function over a convex set of linear constraints and bounded integer variables. Our exact solution method is based on the computation of an upper bound and also includes pre-procedure techniques in order to reduce the problem size before starting the branch-and-bound process. We lead a numerical comparison between our method and three other existing algorithms. The approach we propose outperforms other procedures for large-scaled instances (up to 2000 variables and constraints). A extended abstract of this paper appeared in LNCS 4362, pp. 456–464, 2007.     

An evaluation of flow-shop scheduling algorithms for makespan reduction in a stochastic environment

This paper addresses the problem of makespan reduction and improvement in related performance measures in the stochastic flow shop. The experimental design addresses the issues of the problem size in terms of the number of jobs and machines, the bottleneck location within the production facility, and the processing time distribution and sensitivity to variance. In other words, many of the assumptions that are typically made in the published literature are violated in favour of a more realistic production basis. Experiments are performed via simulation to examine the performance of several well known flow-shop scheduling algorithms and one new algorithm in this challenging environment. The authors conclude that distributional effects and bottleneck considerations can play a role in the performance of the various algorithms considered. This paper further indicates that the problem size also tends to drive the effectiveness of the scheduling strategies examined, and presents information regarding interesting interaction effects between the problem size and the other elements of experimental concern.     

A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang

This paper presents a quasi-human algorithm for the rectangular strip packing problem without guillotine constraint. The basic version of the algorithm works according to seven heuristic selection rules, which are designed to select a corner-occupying action. The strengthened version of the algorithm adopts a branching scheme in which the basic version of the algorithm is applied in a heuristic series of parallel branches. Computational tests carried on eight sets of well-known benchmark instances show that the algorithm is efficient for approximately solving the problem. In comparison with the best algorithms in the literature, the algorithm performs better for zero-waste instances and large scale non-zero-waste instances.     

A simulated annealing algorithm for job shop scheduling

In this paper, the job shop scheduling problem is considered with the objective of minimization of makespan time. We first reviewed the literature on job shop scheduling using meta-heuristics. Then a simulated annealing algorithm is presented for scheduling in a job shop. To create neighbourhoods, three perturbation schemes, viz. pairwise exchange, insertion, and random insertion are used, and the effect of them on the final schedule is also compared. The proposed simulated annealing algorithm is compared with existing genetic algorithms and the comparative results are presented. For comparative evaluation, a wide variety of data sets are used. The proposed algorithm is found to perform well for scheduling in the job shop.     

Modified differential evolution with self-adaptive parameters method

The differential evolution algorithm (DE) is a simple and effective global optimization algorithm. It has been successfully applied to solve a wide range of real-world optimization problem. In this paper, the proposed algorithm uses two mutation rules based on the rand and best individuals among the entire population. In order to balance the exploitation and exploration of the algorithm, two new rules are combined through a probability rule. Then, self-adaptive parameter setting is introduced as uniformly random numbers to enhance the diversity of the population based on the relative success number of the proposed two new parameters in a previous period. In other aspects, our algorithm has a very simple structure and thus it is easy to implement. To verify the performance of MDE, 16 benchmark functions chosen from literature are employed. The results show that the proposed MDE algorithm clearly outperforms the standard differential evolution algorithm with six different parameter settings. Compared with some evolution algorithms (ODE, OXDE, SaDE, JADE, jDE, CoDE, CLPSO, CMA-ES, GL-25, AFEP, MSAEP and ENAEP) from literature, experimental results indicate that the proposed algorithm performs better than, or at least comparable to state-of-the-art approaches from literature when considering the quality of the solution obtained.     

Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees

Given two rooted binary phylogenetic trees with identical leaf label-set, the maximum agreement forest (MAF) problem asks for a largest common subforest of the two trees. This problem has been studied extensively in the literature, and has been known to be NP-complete and MAX SNP-hard. The previously best ratio of approximation algorithms for this problem is 3. In this paper, we make full use of the special relations among leaves in phylogenetic trees and present an approximation algorithm with ratio 2.5 for the MAF problem on two rooted binary phylogenetic trees.