A bisection method for the traveling salesman problem
A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays
In this paper we consider the problem of scheduling, on a two-machine flowshop, a set of unit-time operations subject to time delays with respect to the makespan. This problem is known to be x1d4a9;x1d4ab; -hard in the strong sense. We propose an algorithm based on a branch and bound enumeration scheme. This algorithm includes the implementation of new lower and upper bound procedures, and dominance rules. A computer simulation to measure the performance of the algorithm is provided for a wide...
A branch&bound algorithm for solving one-dimensional cutting stock problems exactly
Many numerical computations reported in the literature show only a small difference between the optimal value of the one-dimensional cutting stock problem (1CSP) and that of the corresponding linear programming relaxation. Moreover, theoretical investigations have proven that this difference is smaller than 2 for a wide range of subproblems of the general 1CSP.
A Branch-and-Bound method for solving Multi-Skill Project Scheduling Problem
This paper deals with a special case of Project Scheduling problem: there is a project to schedule, which is made up of activities linked by precedence relations. Each activity requires specific skills to be done. Moreover, resources are staff members who master fixed skill(s). Thus, each resource requirement of an activity corresponds to the number of persons doing the corresponding skill that must be assigned to the activity during its whole processing time. We search for an exact solution that...
A branch-and-cut algorithm for a resource-constrained scheduling problem
This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance,...
A branch-and-cut for the Non-Disjoint m-Ring-Star Problem
In this article we study the realistic network topology of Synchronous Digital Hierarchy (SDH) networks. We describe how providers fulfill customer connectivity requirements. We show that SDH Network design reduces to the Non-Disjoint m-Ring-Star Problem (NDRSP). We first show that there is no two-index integer formulation for this problem. We then present a natural 3-index formulation for the NDRSP together with some classes of valid inequalities that are used as cutting planes in a Branch-and-Cut...
A branch-and-price algorithm for the windy rural postman problem
In this paper, we propose an exact solution method for the windy rural postman problem (WRPP). The motivation to study this problem comes from some real-life applications, such as garbage collecting in a predefined sector with hills, where the traversing or the servicing speed can change following the direction. We present a Dantzig-Wolfe decomposition and a branch-and-price algorithm to solve the WRPP. To the best of our knowledge, Dantzig-Wolfe decomposition has never been used to solve that problem....
A BSSS algorithm for the location problem with minimum square error.
A bulk queueing system under -policy with bilevel service delay discipline and start-up time.
A chaos-based secure cluster protocol for wireless sensor networks
Security mechanisms for wireless sensor networks (WSN) face a great challenge due to the restriction of their small sizes and limited energy. Hence, many protocols for WSN are not designed with the consideration of security. Chaotic cryptosystems have the advantages of high security and little cost of time and space, so this paper proposes a secure cluster routing protocol based on chaotic encryption as well as a conventional symmetric encryption scheme. First, a principal-subordinate chaotic function...
A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
A Classification of Reverse Engineering Tools and Criteria for Their Evaluation and Selection
A combinatorial arc tolerance analysis for network flow problems.
A Comparative Analysis of the Dea-Ccr Model and the Vikor Method
A Concept of an Expert System for Spare Parts Inventory Classification
A concise survey of efficiently solvable special cases of the permutation flow-shop problem
A concurrency control problem in a time-sharing system with different job types
A DEA model for two-stage parallel-series production processes
Data envelopment analysis (DEA) has been widely used to measure the performance of the operational units that convert multiple inputs into multiple outputs. In many real world scenarios, there are systems that have a two-stage network process with shared inputs used in both stages of productions. In this paper, the problem of evaluating the efficiency of a set of specialized and interdependent components that make up a large DMU is considered. In these processes the first stage consists of two parallel...
A Decision Support System for Farm Regional Planning
A decision support system for regional hazardous waste management alternatives.