排序方式: 共有31条查询结果,搜索用时 15 毫秒
1.
2.
In this paper, we present a hybrid genetic algorithm for the well-known nurse scheduling problem (NSP). The NSP involves the
construction of roster schedules for nursing staff in order to maximize the quality of the roster schedule subject to various
hard constraints. In the literature, several genetic algorithms have been proposed to solve the NSP under various assumptions.
The contribution of this paper is twofold. First, we extensively compare the various crossover operators and test them on
a standard dataset in a solitary approach. Second, we propose several options to hybridize the various crossover operators. 相似文献
3.
In this paper, we study the multi-machine scheduling problem with earliness and tardiness penalties and sequence dependent
setup times. This problem can be decomposed into two subproblems—sequencing and timetabling. Sequencing focuses on assigning
each job to a fixed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling
focuses on finding an executable schedule from the semi-schedule via idle-time insertion. Sequencing is strongly NP-hard in
general. Although timetabling is polynomial-time solvable, it can become a computational bottleneck if the procedure is executed
many times within a larger framework. This paper makes two contributions. We first propose a quantum improvement to the computational
efficiency of the timetabling algorithm. We then apply it within a squeaky wheel optimization framework to solve the sequencing
and overall problem. Finally, we demonstrate the strength of our proposed algorithms by experiments. 相似文献
4.
In this paper, we propose an algorithm named BDS (Bound-Driven Search) that combines features of exact and approximate methods.
The proposed procedure may be seen as a local search algorithm that systematically explores (in a branch-and bound sense)
the most promising nodes, thus preventing solutions from being reevaluated. Additionally, it can be regarded as an exact method
as it may be able to guarantee that the solution found is optimal. We present the application of this new algorithm to a specific
problem domain: the permutation flow shop scheduling problem with makespan objective. The subsequent computational experiments
are encouraging, as the algorithm is able to yield exact or near exact solutions to most instances of the problem. Furthermore,
the algorithm outperforms one of the best state-of-the-art algorithms for the problem. 相似文献
5.
Thibaut Vidal Teodor Gabriel Crainic Michel Gendreau Christian Prins 《European Journal of Operational Research》2013
The attributes of vehicle routing problems are additional characteristics or constraints that aim to better take into account the specificities of real applications. The variants thus formed are supported by a well-developed literature, including a large variety of heuristics. This article first reviews the main classes of attributes, providing a survey of heuristics and meta-heuristics for Multi-Attribute Vehicle Routing Problems (MAVRP). It then takes a closer look at the concepts of 64 remarkable meta-heuristics, selected objectively for their outstanding performance on 15 classic MAVRP with different attributes. This cross-analysis leads to the identification of “winning strategies” in designing effective heuristics for MAVRP. This is an important step in the development of general and efficient solution methods for dealing with the large range of vehicle routing variants. 相似文献
6.
A self-adaptive global best harmony search algorithm for continuous optimization problems 总被引:3,自引:0,他引:3
This paper presents a self-adaptive global best harmony search (SGHS) algorithm for solving continuous optimization problems. In the proposed SGHS algorithm, a new improvisation scheme is developed so that the good information captured in the current global best solution can be well utilized to generate new harmonies. The harmony memory consideration rate (HMCR) and pitch adjustment rate (PAR) are dynamically adapted by the learning mechanisms proposed. The distance bandwidth (BW) is dynamically adjusted to favor exploration in the early stages and exploitation during the final stages of the search process. Extensive computational simulations and comparisons are carried out by employing a set of 16 benchmark problems from literature. The computational results show that the proposed SGHS algorithm is more effective in finding better solutions than the state-of-the-art harmony search (HS) variants. 相似文献
7.
Ramiro Varela Camino R. Vela Jorge Puente María Sierra Inés González-Rodríguez 《Annals of Operations Research》2009,166(1):125-146
We confront a practical cutting stock problem from a production plant of plastic rolls. The problem is a variant of the well-known
one dimensional cutting stock, with particular constraints and optimization criteria defined by the experts of the company.
We start by giving a problem formulation in which optimization criteria have been considered in linear hierarchy according
to expert preferences, and then propose a heuristic solution based on a GRASP algorithm. The generation phase of this algorithm
solves a simplified version which is rather similar to the conventional one dimensional cutting stock. To do that, we propose
a Sequential Heuristic Randomized Procedure (SHRP). Then in the repairing phase, the solution of the simplified problem is
transformed into a solution to the real problem. For experimental study we have chosen a set of problem instances of com-mon
use to compare SHRP with another recent approach. Also, we show by means of examples, how our approach works over instances
taken from the real production process.
All authors are supported by MEC-FEDER Grant TIN2007-67466-C02-01 and by contract CN-05-127 of the University of Oviedo and
the company ERVISA, and by FICYT under grant BP04-021. 相似文献
8.
While there have been many adaptations of some of the more popular meta-heuristics for continuous multi-objective optimisation problems, Tabu Search has received relatively little attention, despite its suitability and effectiveness on a number of real-world design optimisation problems. In this paper we present an adaptation of a single-objective Tabu Search algorithm for multiple objectives. Further, inspired by path relinking strategies common in discrete optimisation problems, we enhance our algorithm to allow it to handle problems with large numbers of design variables. This is achieved by a novel parameter selection strategy that, unlike a full parametric analysis, avoids the use of objective function evaluations, thus keeping the overall computational cost of the procedure to a minimum. We assess the performance of our two Tabu Search variants on a range of standard test functions and compare it to a leading multi-objective Genetic Algorithm, NSGA-II. The path relinking-inspired parameter selection scheme gives a clear performance improvement over the basic multi-objective Tabu Search adaptation and both variants perform comparably with the NSGA-II. 相似文献
9.
This study addresses a class of single-machine scheduling problems involving a common due date where the objective is to minimize
the total job earliness and tardiness penalties. A genetic algorithm (GA) approach and a simulated annealing (SA) approach
utilizing a greedy local search and three well-known properties in the area of common due date scheduling are developed. The
developed algorithms enable the starting time of the first job not at zero and were tested using a set of benchmark problems.
From the viewpoints of solution quality and computational expenses, the proposed approaches are efficient and effective for
problems involving different numbers of jobs, as well as different processing time, and earliness and tardiness penalties. 相似文献
10.
This paper presents a new optimization algorithm called GHS + LEM, which is based on the Global-best Harmony Search algorithm (GHS) and techniques from the learnable evolution models (LEM) to improve convergence and accuracy of the algorithm. The performance of the algorithm is evaluated with fifteen optimization functions commonly used by the optimization community. In addition, the results obtained are compared against the original Harmony Search algorithm, the Improved Harmony Search algorithm and the Global-best Harmony Search algorithm. The assessment shows that the proposed algorithm (GHS + LEM) improves the accuracy of the results obtained in relation to the other options, producing better results in most situations, but more specifically in problems with high dimensionality, where it offers a faster convergence with fewer iterations. 相似文献