排序方式: 共有31条查询结果,搜索用时 15 毫秒
1.
Analysis of Static Simulated Annealing Algorithms 总被引:1,自引:0,他引:1
Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms to address intractable discrete optimization problems. This paper introduces a measure for determining the expected number of iterations to visit a predetermined objective function level, given that an inferior objective function level has been reached in a finite number of iterations. A variation of simulated annealing (SA), termed static simulated annealing (S2A), is analyzed using this measure. S2A uses a fixed cooling schedule during the algorithm execution. Though S2A is probably nonconvergent, its finite-time performance can be assessed using the finite-time performance measure defined in this paper. 相似文献
2.
Sheldon?H.?JacobsonEmail author Shane?N.?Hall Laura?A.?McLay Jeffrey?E.?Orosz 《Methodology and Computing in Applied Probability》2005,7(2):183-201
Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Measures for assessing the finite-time performance of GHC algorithms have been developed using this framework, including the expected number of iterations to visit a predetermined objective function value level. This paper analyzes how the expected number of iterations to visit a predetermined objective function value level can be estimated for cyclical simulated annealing. Cyclical simulated annealing uses a cooling schedule that cycles through a set of temperature values. Computational results with traveling salesman problem instances taken from TSPLIB show how the expected number of iterations to visit solutions with predetermined objective function levels can be estimated for cyclical simulated annealing.AMS 2000 Subject Classification 90-08 Computational Methods: Local Search, 90C59 Heuristics: Simulated Annealing 相似文献
3.
《Operations Research Letters》2020,48(3):209-216
Many sports leagues first announce the games to be played in each round and then determine their matchdays as the season progresses. This study focuses on the fairness criterion of minimizing the total rest difference among opposing teams to find the matchdays for an announced schedule. We show that the problem is decomposable into optimizing the rounds separately. We also provide a polynomial-time exact algorithm for canonical schedules. 相似文献
4.
HOW GOOD IS A DENSE SHOP SCHEDULE? 总被引:6,自引:0,他引:6
In this paper, we study a class of simple and easy-to-construct shop schedules, known as dense schedules. We present tight
bounds on the maximum deviation in makespan of dense flow-shop and job-shop schedules from their optimal ones. For dense open-shop
schedules, we do the same for the special case of four machines and thus add a stronger supporting case for proving a standing
conjecture.
Support for the research by the first author is provided by the Management Research Fellowship of the ESRC (Economic & Social
Research Council) of U.K., and this research is also partially supported by the National Natural Science Foundation of China. 相似文献
5.
6.
The paper proposes a new classification of schedules for resource-constrained project scheduling problems with minimum and
maximum time lags between project activities and regular and different types of nonregular objective functions. The feasible
region of the scheduling problems represents a (generally disconnected) union of polytopes. In addition to the well-known
concepts of active and semiactive schedules, pseudoactive and quasiactive as well as stable, semistable, pseudostable, and
quasistable schedules are introduced. The (quasi-, pseudo-, semi-)active schedules are related to different types of left-shifts
of sets of activities and correspond to minimal points of certain subsets of the feasible region. The (quasi-, pseudo-, semi-)stable
schedules do not allow oppositely directed shifts and correspond to extreme points of certain subsets of the feasible region.
The different sets of schedules contain optimal schedules for project scheduling problems which differ in their objective
functions. The correspondence between those sets of schedules and vertices of specific polyhedral subsets of the feasible
region can be exploited for analyzing schedule generation schemes which have been developed recently for finding solutions
to the different classes of project scheduling problems. 相似文献
7.
HE Cheng LIN Hao DO U Jun-mei MU Yun-dong 《数学季刊》2014,(2):159-166
It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b≥n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O(n3) time. 相似文献
8.
The formula for the blocking probability for the finite capacity M/G/1/K in terms of the steady state occupancy probability distribution of M/G/1 and the system utilization is known [Keilson, J. Royal Statistical Soc. Serie B, 28 (1966) 190–201]. The validity of this relationship is demonstrated for a broad class of state dependent M/G/1 vacation systems and priority systems. New methods are employed which may also be of interest in their own right.This research was conducted while J. Keilson was a Senior Staff Scientist at GTE Laboratories Incorporated. 相似文献
9.
This paper develops a method for finding the whole set of efficient points of a multiobjective linear problem. Two algorithms are presented; the first one describes the set of all efficient vertices and all efficient rays of the constraint polyhedron, while the second one generates the set of all efficient faces. The method has been tested on several examples for which numerical results are reported.The authors are grateful to Professor W. Stadler and an anonymous referee for their helpful comments and corrections. 相似文献
10.
We study semi-convex frontier (SCF) optimization problems where objective functions can be semi-convex and constraint sets can be non-polyhedron, which stem from a growing range of optimization applications such as frontier analysis, multi-objective programming in economics. The new findings of this paper can be summarized as follows: (1) We characterize non-dominated points of a non-polyhedron optimal solution set of a semi-convex frontier program. (2) We obtain optimality conditions of a constant modulus SCF program, of which the objective function is semi-convex with a constant semiconvexity modulus. (3) We obtain a non-smooth Hölder stability of the optimal solutions of a semiconvex frontier program. (4) We use generalized differentiability to establish sensitivity analysis of the optimal value function of a semi-convex frontier program. 相似文献