Search

In this paper, we investigate the use of a look-ahead strategy combined with path-relinking for tackling the problem of scheduling multiprocessor tasks on two dedicated processors. An instance of the problem is composed of a set of tasks divided into three subsets and two processors, where some tasks can be executed either on one processor or two processors. The goal of the problem is to schedule all tasks such that the execution of the last assigned task is minimized. First, the proposed method starts with a greedy feasible solution built by applying a knapsack rule related to a predefined sequence. Second, a series of local operators are added in order to drive the search process around a series of neighborhoods. Third, a first diversification strategy based upon drop and rebuild operators is employed. The second diversification/intensification strategy is used for highlighting the performance of the method; it incorporates a look-ahead strategy combined with the path-relinking. Finally, the performance of the proposed method is experimentally analyzed on a set of benchmark instances of the literature, where its provided results are compared to those achieved by more recent methods available in the literature. Its behavior is also evaluated by providing a statistical analysis using both the Sign test and the Wilcoxon signed-rank test.

In this paper, we propose a hybrid descent method for solving a special case of the well-known network design problem with relays; that is, the two-edge disjoint survivable network design problem with relays. Such a problem arises in several applications related to telecommunications and distribution networks. The proposed method can be viewed as a two-stage approach, where an intensification neighborhood search and a modified descent method are applied. The neighborhood search is used either for improving the quality of the solutions or merging two sub-solutions composed of partial and complementary ones. The descent method uses degrading and rebuilding strategies in order to reach a series of solutions. The performance of the method is evaluated on benchmark instances taken from the literature, where its provided results are compared to those reached by the best methods available in the literature. The obtained results show that such a method is able to provide new solutions.

This article investigates a new robust criterion for the vehicle routing problem with uncertainty on the travel time. The objective of the proposed criterion is to find a robust solution which displays better behaviour on a majority of scenarios, where each scenario represents a potential state of an uncertain event. In order to highlight the robustness of the proposed approach, the new robust criterion is compared with the classical robust criteria, such as best-case, worst-case and min-max deviation. Inspired from the mechanism developed by B. Roy for evaluating the robustness, this paper focuses on providing two robust conclusions for the new robust criterion: perfectly robust and pseudo robust. For the perfectly robust, the robust criterion is evaluated by using an exact method on a set of 480 small-scale instances generated from Solomon’s benchmark instances. For the pseudo robust, the robust criterion is evaluated by using a metaheuristic on a set of 54 medium-scale and large-scale instances. The numerical results show that the new approach is able to produce the robust solutions in a majority of cases.

In this paper, we consider the k-Depots Hamiltonian Path Problem (k-DHPP) of searching k paths in a graph G, starting from k fixed vertices and spanning all the vertices of G. We propose an approximation algorithm for solving the k-DHPP, where the underlying graph is cubic and 2-vertex-connected. Then, we prove the existence of a 5 3 -approximation algorithm that gives a solution with total cost at most 5 3 n - 4 k - 2 3 . In this case, the proposed method is based upon searching for a perfect matching, constructing an Eulerian graph and finally a k paths solution, following the process of removing/adding edges. We also present an approximation algorithm for finding a shortest tour passing through all vertices in a factor-critical and 2-vertex connected graph. The proposed algorithm achieves a 7 6 -approximation ratio where the principle of the method is based on decomposing the graph into a series of ears.

In this paper we propose a robust optimization strategy for the vehicle routing problem with time windows, where the travel time is considered as uncertain. The objective is to minimize the risk of delay related to the time windows constraint. We first present a robust model in which the uncertain travel time is related to a discrete set of scenarios: each scenario can be viewed as an observation of time required to complete a current route. Such a model is based upon a mixed-integer linear programming that can handle an optimal (solution) value related to the worst observation of the total travel time over all available scenarios. Second, in order to evaluate the effects on the scenario model, a guided neighborhood search-based heuristic is adapted for solving the model and tested on a variety of instances obtained by using Solomon’s standard generator, where a total of 5040 instances are considered. Finally, we study the behavior of the adapted algorithm to solve the robust model and highlight the interaction between the number of scenarios used which are based upon uncertain events and the uncertainty of the problem.

In this paper, we solve the two-staged two-dimensional cutting problem using a parallel algorithm. The proposed approach combines two main features: beam search (BS) and strip generation solution procedures (SGSP). BS employs a truncated tree-search, where a selected subset of generated nodes are retuned for further search. SGSP, a constructive procedure, combines a (sub)set of strips for providing both partial lower and complementary upper bounds. The algorithm explores in parallel a subset of selected nodes following the master-slave paradigm. The master processor serves to guide the search-resolution and each slave processor develops its proper way, trying a global convergence. The aim of such an approach is to show how the parallelism is able to efficiently solve large-scale instances, by providing new solutions within a consistently reduced runtime. Extensive computational testing on instances, taken from the literature, shows the effectiveness of the proposed approach.

In this paper, we discuss the circular open dimension problem (CODP); that is a problem of the cutting/packing family. In CODP, we are given an initial strip of fixed width W and unlimited length, as well as a finite set N of n circular pieces C i of known radius r i , i ∈ N. The objective is to find a global optimum corresponding to the minimum length of the initial strip containing the n pieces. We propose an augmented algorithm for solving the CODP which combines a beam search, a binary search and the well-known multi-start strategy. In addition, in order to increase the efficiency of the algorithm, we incorporate a separate-beams strategy instead of the pooled one. The performance of the proposed algorithm is evaluated on a set of benchmark instances: it improves several best known solutions of the literature.

The disjunctively constrained knapsack problem (DCKP) is a variant of the well-known single constrained knapsack problem with special disjunctive constraints. This paper investigates the use of the local branching techniques for solving large-scale DCKP. Three versions of the algorithm are considered. The first version is based on the standard local branching which uses a starting solution provided by a specialized rounding solution procedure. The second version applies a two-phase solution procedure embedded in the local branching. For each subtree, the procedure serves to construct the set of objects containing the assigned variables and a second set including the free variables. The first set provides a partial local solution to the DCKP, whereas, for the second set, a truncated exact tree-search is applied for completing the partial local feasible solution. Finally, a diversification strategy is considered constituting the third version of the algorithm. All versions of the proposed algorithm are computationally analyzed on a set of benchmark instances of the literature and the obtained solutions are compared to those provided by existing algorithms. Encouraging results have been obtained.

The problem of generating guillotine cutting patterns for a number of stock entities with a rectangular form is discussed. We present exact algorithms and heuristics for solving exactly and approximately the general two-dimensional guillotine cutting (with many stock entities) and a particular case called the two-dimensional guillotine cutting (which considers only one stock unit). For the particular problem, we use the graph representation of the problem which is commonly used in artificial intelligence, and also some lower and upper bounds obtained by using the operations research techniques. For the general problem, we show how we can solve it by using dynamic programming methods: the heuristic search is based upon a series of one-dimensional knapsack problems and the exact algorithm is based on two-dimensional knapsack problems. Further, some heuristics are considered, and computational results are presented on some instances taken from the literature as well as randomly generated instances.