共查询到20条相似文献,搜索用时 15 毫秒
1.
《European Journal of Operational Research》1996,93(2):331-345
In this paper two types of neurons, the maximum selection neuron and the maximum cut-off neuron are introduced. They are used to construct a neural network to represent and solve the stable matching problem. The neural network approach allows the matching to be processed dynamically in a distributed parallel processing environment. 相似文献
2.
《Discrete Applied Mathematics》1987,16(3):217-222
Using a lemma of J.S. Hwang we obtain a generalization of a theorem of Dubins and Freedman. It is shown that the core of the matching game is non-manipulable in a suitable sense by coalitions consisting of both men and women. A further strong stability property of the core is derived. 相似文献
3.
Jimmy J. M. Tan 《BIT Numerical Mathematics》1990,30(4):631-640
The stable roommates problem is that of matchingn people inton/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called a complete stable matching. It is known that a complete stable matching may not exist. Irving proposed anO(n
2) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present anO(n
2) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching.This research was supported by National Science Council of Republic of China under grant NSC 79-0408-E009-04. 相似文献
4.
The stable matching problem is that of matching two sets of agents in such a manner that no two unmatched agents prefer each other to their mates. We establish three results on properties of these matchings and present two short proofs of a recent theorem of Dubins and Freedman. 相似文献
5.
The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new heuristic algorithm for the JSSP that effectively combines the classical shifting bottleneck procedure (SBP) with a dynamic and adaptive neighborhood search procedure. Our new search method, based on a filter-and-fan (F&F) procedure, uses the SBP as a subroutine to generate a starting solution and to enhance the best schedules produced. The F&F approach is a local search procedure that generates compound moves by a strategically abbreviated form of tree search. Computational results carried out on a standard set of 43 benchmark problems show that our F&F algorithm performs more robustly and effectively than a number of leading metaheuristic algorithms and rivals the best of these algorithms. 相似文献
6.
The number of hospitals in Japan exceeds 10,000, and every month nurses are scheduled to shifts in about 30,000 units in total. There is serious demand for automating this scheduling task. In this paper, we introduce a mathematical programming formulation of the nurse scheduling problem in Japan, and develop a meta-heuristic approach to solve the problem. This scheduling problem is a hard combinatorial problem due to tight constraints involving such factors as the skill level of a team, the need to balance workload among nurses, and the consideration of nurses' preferences, even though the number of the nurses to be scheduled is not large, at between 20 and 40. The performance of our approach is demonstrated by the successful solution of data taken from actual scheduling problems. The proposed model and approach can be adapted for the majority of hospitals in Japan, as well as for some hospitals in other countries, and is likely applicable to many other scheduling problems in the fields of business and logistics.
Key words.nurse scheduling – block-angular problem – subproblem – integer programming – relaxation – tabu search – branch-and-boundMathematics Subject Classification (1991):20E28, 20G40, 20C20 相似文献
7.
A combined branch-and-bound and genetic algorithm based approach for a flowshop scheduling problem 总被引:3,自引:0,他引:3
In this paper, we study the application of a meta-heuristic to a two-machine flowshop scheduling problem. The meta-heuristic uses a branch-and-bound procedure to generate some information, which in turn is used to guide a genetic algorithm's search for optimal and near-optimal solutions. The criteria considered are makespan and average job flowtime. The problem has applications in flowshop environments where management is interested in reducing turn-around and job idle times simultaneously. We develop the combined branch-and-bound and genetic algorithm based procedure and two modified versions of it. Their performance is compared with that of three algorithms: pure branch-and-bound, pure genetic algorithm, and a heuristic. The results indicate that the combined approach and its modified versions are better than either of the pure strategies as well as the heuristic algorithm. 相似文献
8.
Heuristic algorithms for scheduling tasks with multiple modes and minimizing the schedule length involve in general two distinct
phases, task mode assignment and then task scheduling. We propose a novel approach where these two features are managed in an integrated mechanism with mode assignment embedded
in scheduling. The problem is first reformulated as a special single-mode task scheduling problem, and then is modeled as
a graph interval T-coloring. Finally, a tabu-like metaheuristic is proposed for this latter graph coloring problem, and the performance of our
approach is compared to known multi-mode scheduling heuristics. 相似文献
9.
A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process 总被引:1,自引:0,他引:1
One of the largest bottlenecks in iron and steel production is the steelmaking-continuous casting (SCC) process, which consists of steel-making, refining and continuous casting. The SCC scheduling is a complex hybrid flowshop (HFS) scheduling problem with the following features: job grouping and precedence constraints, no idle time within the same group of jobs and setup time constraints on the casters. This paper first models the scheduling problem as a mixed-integer programming (MIP) problem with the objective of minimizing the total weighted earliness/tardiness penalties and job waiting. Next, a Lagrangian relaxation (LR) approach relaxing the machine capacity constraints is presented to solve the MIP problem, which decomposes the relaxed problem into two tractable subproblems by separating the continuous variables from the integer ones. Additionally, two methods, i.e., the boundedness detection method and time horizon method, are explored to handle the unboundedness of the decomposed subproblems in iterations. Furthermore, an improved subgradient level algorithm with global convergence is developed to solve the Lagrangian dual (LD) problem. The computational results and comparisons demonstrate that the proposed LR approach outperforms the conventional LR approaches in terms of solution quality, with a significantly shorter running time being observed. 相似文献
10.
Hanen Akrout Bassem Jarboui Patrick Siarry Abdelwaheb Reba? 《Computational Optimization and Applications》2012,51(1):411-435
When handling combinatorial optimization problems, we try to get the optimal arrangement of discrete entities so that the
requirements and the constraints are satisfied. These problems become more and more important in various industrial and academic
fields. So, over the past years, several techniques have been proposed to solve them. In this paper, we are interested in
the single machine scheduling problem with Sequence-Dependent Setup Times, which can be solved through different approaches.
We present a hybrid algorithm which combines Greedy Randomized Adaptive Search Procedure and Differential Evolution for tackling
this problem. Our algorithm is tested on benchmark instances from the literature. The computational experiments prove the
efficiency of this algorithm. 相似文献
11.
《European Journal of Operational Research》1999,113(2):435-449
In this paper we address the problem of minimizing makespan and sum of completion times simultaneously in a two-machine flow shop environment. We formulate the problem as a bicriteria scheduling problem, and develop a branch-and-bound procedure that iteratively solves restricted single objective scheduling problems until the set of efficient solutions is completely enumerated. We report computational results, and explore certain properties of the set of efficient solutions. We then discuss their implications for the Decision Maker. 相似文献
12.
Ulrike Schneider 《Central European Journal of Operations Research》2011,19(4):467-493
We apply a tabu search method to a scheduling problem of a company producing cables for cars: the task is to determine on
what machines and in which order the cable jobs should be produced in order to save production costs. First, the problem is
modeled as a combinatorial optimization problem. We then employ a tabu search algorithm as an approach to solve the specific
problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate
how these different implementations improve the results. Moreover, we show how the computational cost in each iteration of
the algorithm can be reduced drastically from O(n
3) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders). 相似文献
13.
A “pure” Constraint Programming approach for the Resource-Constrained Project Scheduling Problem (RCPSP) is presented. Our
basic idea was to substitute the resource constraints by a set of “sub-constraints” generated as needed. Each of these sub-constraints
corresponds to a set of tasks that cannot be executed together without violating one of the resource constraints. A filtering
algorithm for these sub-constraints has been developed. When applied to the initial resource constraints together with known
filtering algorithms, this new filtering algorithm provides very good numerical results. 相似文献
14.
Jeff Kahn 《Proceedings of the American Mathematical Society》2002,130(2):371-378
For -regular, -vertex bipartite graphs with bipartition , a precise bound is given for the sum over independent sets of the quantity . (In other language, this is bounding the partition function for certain instances of the hard-core model.) This result is then extended to graded partially ordered sets, which in particular provides a simple proof of a well-known bound for Dedekind's Problem given by Kleitman and Markowsky in 1975.
15.
《European Journal of Operational Research》1988,34(3):372-383
The problem of scheduling final exams at a large university can be viewed as a three phase process. The first phase consists of grouping the exams into sets called exam blocks. The second phase deals with the assignment of exam blocks to exam days and the third phase consists of arranging the exam days and also arranging the blocks within days.In this paper, we present new integer programming formulations for the second phase of the scheduling problem. We present an integer program with a single objective of minimizing the number of students with two or more exams per day. We then present a Lagrangian relaxation based solution procedure to solve this problem. Further, we present a bicriterion integer programming formulation to minimize the number of students with two exams per day and the number of students with three exams per day. Finally, we present some computational experience using randomly generated problems as well as real world data obtained from the State University of New York at Buffalo. 相似文献
16.
Michael J. Shaw 《Annals of Operations Research》1988,15(1):353-376
Scheduling in flexible manufacturing systems (FMS) must take into account the shorter lead time, the multiprocessing environment, and the dynamically changing states. In this paper, a pattern-directed approach is presented which incorporates a nonlinear planning method developed in the artificial intelligence field. The scheduling system described here is knowledge-based and utilizes both forward-and backward-chaining for generating schedules (treated as state-space plans). The pattern-directed approach is dynamically adjustable and thus can handle scheduling requirements unique to the FMS environment, such as dynamic scheduling, failure-recovery scheduling, or prioritized scheduling for meeting deadlines. 相似文献
17.
18.
We show that certain manpower scheduling problems can be modeled as the following constrained matching problem. Given an undirected graphG = (V,E) with edge weights and a digraphD = (V,A). AMaster/Slave-matching (MS-matching) ofG with respect toD is a matching ofG such that for each arc (u, v) A for which the nodeu is matched, the nodev is matched, too. TheMS-Matching Problem is the problem of finding a maximum-weight MS-matching. Letk(D) be the maximum size of a (weakly) connected component ofD. We prove that MS-matching is an NP-hard problem even ifG is bipartite andk(D) 3. Moreover, we show that in the relevant special case wherek(D) 2, the MS-Matching Problem can be transformed to the ordinary Matching Problem.This research was supported by Grant 03-KL7PAS-6 of the German Federal Ministry of Research and Technology. 相似文献
19.
《European Journal of Operational Research》1996,93(1):61-67
In this paper we propose a simulated annealing approach for solving the single machine mean tardiness scheduling problem. The results of a simulation experiment indicate that the proposed method provides much better solutions than two heuristics that gave good results in previous studies. More importantly, the solutions obtained are within less than 1% of optimal solutions. 相似文献
20.
《European Journal of Operational Research》1999,112(2):347-366
We describe a simple breadth-first tree search scheme for minimizing the makespan of a project consisting of a partially ordered network of activities under multiple resource constraints. The method compares quite favourably with existing techniques that employ depth-first or best-first search; in particular, it is able to solve optimally on a Pentium PC running SCO UNIX the entire set of 680 benchmark problems (First Lot: 480, Second Lot: 200) generated by Kolisch et al., 1995. The new algorithm has also been checked out experimentally on additional random test problems at graded levels of difficulty that were generated using two parameters: the threshold, which determined the predecessors of an activity, and the total resource availability of each resource type. The breadth-first scheme can be modified quite readily to do best-first search or to minimize measures other than makespan such as mean flow time and maximum tardiness. 相似文献