共查询到20条相似文献,搜索用时 0 毫秒
1.
Filip Deblaere Erik Demeulemeester Willy Herroelen 《European Journal of Operational Research》2011,214(2):308-316
The resource-constrained project scheduling problem involves the determination of a schedule of the project activities, satisfying the precedence and resource constraints while minimizing the project duration. In practice, activity durations may be subject to variability. We propose a stochastic methodology for the determination of a project execution policy and a vector of predictive activity starting times with the objective of minimizing a cost function that consists of the weighted expected activity starting time deviations and the penalties or bonuses associated with late or early project completion. In a computational experiment, we show that our procedure greatly outperforms existing algorithms described in the literature. 相似文献
2.
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. 相似文献
3.
Jürgen Weishaupt 《Mathematical Methods of Operations Research》1994,40(1):75-89
Stochastic scheduling problems are considered by using discounted dynamic programming. Both, maximizing pure rewards and minimizing linear holding costs are treated in one common Markov decision problem. A sufficient condition for the optimality of the myopic policy for finite and infinite horizon is given. For the infinite horizon case we show the optimality of an index policy and give a sufficient condition for the index policy to be myopic. Moreover, the relation between the two sufficient conditions is discussed. 相似文献
4.
In this article, we analyze the precedence diagramming method, the only published algorithm for time-only project scheduling with activity splitting allowed. The criteria used in this method (forward and backward pass computations) for deciding when an activity has to be interrupted are shown to be invalid in some situations. We look into the causes of these failures and propose new formulae that always provide feasible solutions. The new algorithm has been tested on 240 randomly generated problems ranging up to 600 activities and 7,200 precedence relationships, resulting in an average deviation from optima of less than 1 percent. 相似文献
5.
Christian Prins 《Mathematical Methods of Operations Research》2000,52(3):389-411
For more than two machines, and when preemption is forbidden, the computation of minimum makespan schedules for the open-shop
problem is NP-hard. Compared to the flow-shop and the job-shop, the open-shop has free job routes which lead to a much larger
solution space, to smaller gaps between the optimal makespan and the lower bounds, and to disappointing results for the algorithms
based on the disjunctive graph model. For instance, the best existing branch and bound method cannot solve some 7 ×7 hard
instances to optimality, and all published metaheuristics (working by reversing some disjunctions already fixed) do not better
than some greedy or steepest-descent heuristics which need a much smaller computational effort. In this context, the intrinsic
parallelism of genetic algorithms (GAs) seems well adapted, for detecting global optima disseminated among many quasi-optimal
schedules. This paper presents several GAs for the open-shop problem. It is shown that even simple and fast versions can compete
with the best known heuristics and metaheuristics, thanks to two key-features: a population in which each individual has a distinct makespan, and a special procedure which reorders every new chromosome. Using problem-specific heuristics, it is possible to design more powerful GAs which give excellent results, even on the
hardest benchmarks of the literature: for instance, all hard open instances from Taillard are broken, except one for which
the best known solution is improved. 相似文献
6.
Activity list representation for a generalization of the resource-constrained project scheduling problem 总被引:1,自引:0,他引:1
Most of the real life scheduling problems include several constraints in addition to the precedence and resource constraints considered in the resource-constrained project scheduling problem (RCPSP ). In this paper, we define a generalization of the (RCPSP) with a wide class of additional constraints, including (but not limited to): a pair of activities must be separated by at least a given duration; a subset of activities cannot be processed simultaneously; an activity cannot start before a particular period; an activity cannot be scheduled in a particular time window; there are resource constraints with varying required and available quantities. We show that for this generalization the activity list and the activity set list representations can be used as efficiently as in the (RCPSP) and that by using these representations the optimal solution can always be reached. 相似文献
7.
This paper deals with resource-constrained project scheduling problem under the weighted late work criterion. Late work objective functions estimate the quality of a schedule based on durations of late parts of activities, not taking into account the amount of delay for fully late activities. It is assume that a project contains activities interrelated by finish-to-start type precedence relations with time lag of zero, which require one or more constrained renewable resources. The objective is to schedule each activity such that the total weighted late work is minimized. The problem has been formulated using a linear integer programming model and solved by the CPLEX. Also, a set of priority rules have been designed to quickly generate a set of initial solutions. In order to solve the problem optimally, a depth-first branch-and-bound algorithm is applied based on idea of minimal delaying alternatives. The branching order of nodes that belong to the same level of the search tree is determined on the basis of the developed priority rules. This results in generation six different versions of the branch-and-bound algorithm. Computational results on randomly generated problem sets are provided to analyze the efficiency of the priority rules and the branch-and-bound algorithm. 相似文献
8.
N. Krivulin 《Optimization》2017,66(2):205-224
We consider a project that consists of activities to be performed in parallel under various temporal constraints, which include start-start, start-finish and finish-start precedence relationships, release times, deadlines and due dates. Scheduling problems are formulated to find optimal schedules for the project with respect to different objective functions to be minimized, such as the project makespan, the maximum deviation from the due dates, the maximum flow-time and the maximum deviation of finish times. We represent these problems as optimization problems in terms of tropical mathematics, and then solve them by applying direct solution methods of tropical optimization. As a result, new direct solutions of the scheduling problems are obtained in a compact vector form, which is ready for further analysis and practical implementation. The solutions are illustrated by simple numerical examples. 相似文献
9.
A polyhedral approach to single-machine scheduling problems 总被引:2,自引:0,他引:2
J.M. van den Akker C.P.M. van Hoesel M.W.P. Savelsbergh 《Mathematical Programming》1999,85(3):541-572
We report new results for a time-indexed formulation of nonpreemptive single-machine scheduling problems. We give complete
characterizations of all facet inducing inequalities with integral coefficients and right-hand side 1 or 2 for the convex
hull of the set of feasible partial schedules, i.e., schedules in which not all jobs have to be started. Furthermore, we identify
conditions under which these facet inducing inequalities are also facet inducing for the original polytope, which is the convex
hull of the set of feasible complete schedules, i.e., schedules in which all jobs have to be started. To obtain insight in
the effectiveness of these classes of facet-inducing inequalities, we develop a branch-and-cut algorithm based on them. We
evaluate its performance on the strongly NP-hard single machine scheduling problem of minimizing the weighted sum of the job
completion times subject to release dates.
Received March 24, 1994 / Revised version received February 13, 1997
Published online June 28, 1999 相似文献
10.
A branch-and-bound algorithm for the resource-constrained project scheduling problem 总被引:7,自引:0,他引:7
We describe a time-oriented branch-and-bound algorithm for the resource-constrained project scheduling problem which explores
the set of active schedules by enumerating possible activity start times. The algorithm uses constraint-propagation techniques
that exploit the temporal and resource constraints of the problem in order to reduce the search space. Computational experiments
with large, systematically generated benchmark test sets, ranging in size from thirty to one hundred and twenty activities
per problem instance, show that the algorithm scales well and is competitive with other exact solution approaches. The computational
results show that the most difficult problems occur when scarce resource supply and the structure of the resource demand cause
a problem to be highly disjunctive. 相似文献
11.
An improved heuristic is proposed for one-machine scheduling problem with delay constraints, thus an open problem raised by
Wikumet al. is solved. The heuristic solves the corresponding unit-execution-time problem optimally. 相似文献
12.
A stochastic programming model using an endogenously determined worst case risk measure for dynamic asset allocation 总被引:2,自引:0,他引:2
We present a new approach to asset allocation with transaction costs. A multiperiod stochastic linear programming model is
developed where the risk is based on the worst case payoff that is endogenously determined by the model that balances expected
return and risk. Utilizing portfolio protection and dynamic hedging, an investment portfolio similar to an option-like payoff
structure on the initial investment portfolio is characterized. The relative changes in the expected terminal wealth, worst
case payoff, and risk aversion, are studied theoretically and illustrated using a numerical example. This model dominates
a static mean-variance model when the optimal portfolios are evaluated by the Sharpe ratio.
Received: August 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000 相似文献
13.
This paper presents a genetic algorithm for solving the resource-constrained project scheduling problem. The innovative component of the algorithm is the use of a magnet-based crossover operator that can preserve up to two contiguous parts from the receiver and one contiguous part from the donator genotype. For this purpose, a number of genes in the receiver genotype absorb one another to have the same order and contiguity they have in the donator genotype. The ability of maintaining up to three contiguous parts from two parents distinguishes this crossover operator from the powerful and famous two-point crossover operator, which can maintain only two contiguous parts, both from the same parent. Comparing the performance of the new procedure with that of other procedures indicates its effectiveness and competence. 相似文献
14.
Metric regularity and quantitative stability in stochastic programs with probabilistic constraints 总被引:2,自引:0,他引:2
Received January 24, 1996 / Revised version received December 24, 1997 Published online October 21, 1998 相似文献
15.
Gongyun Zhao 《Mathematical Programming》2001,90(3):507-536
An algorithm incorporating the logarithmic barrier into the Benders decomposition technique is proposed for solving two-stage
stochastic programs. Basic properties concerning the existence and uniqueness of the solution and the underlying path are
studied. When applied to problems with a finite number of scenarios, the algorithm is shown to converge globally and to run
in polynomial-time.
Received: August 1998 / Accepted: August 2000?Published online April 12, 2001 相似文献
16.
We consider a call center with two classes of impatient customers: premium and regular classes. Modeling our call center as a multiclass GI/GI/s+M queue, we focus on developing scheduling policies that satisfy a target ratio constraint on the abandonment probabilities of premium customers to regular ones. The problem is inspired by a real call center application in which we want to reach some predefined preference between customer classes for any workload condition. The motivation for this constraint comes from the difficulty of predicting in a quite satisfying way the workload. In such a case, the traditional routing problem formulation with differentiated service levels for different customer classes would be useless. For this new problem formulation, we propose two families of online scheduling policies: queue joining and call selection policies. The principle of our policies is that we adjust their routing rules by dynamically changing their parameters. We then evaluate the performance of these policies through a numerical study. The policies are characterized by simplicity and ease of implementation. 相似文献
17.
Alan J. King 《Mathematical Programming》2002,91(3):543-562
The hedging of contingent claims in the discrete time, discrete state case is analyzed from the perspective of modeling the
hedging problem as a stochastic program. Application of conjugate duality leads to the arbitrage pricing theorems of financial
mathematics, namely the equivalence of absence of arbitrage and the existence of a probability measure that makes the price
process into a martingale. The model easily extends to the analysis of options pricing when modeling risk management concerns
and the impact of spreads and margin requirements for writers of contingent claims. However, we find that arbitrage pricing
in incomplete markets fails to model incentives to buy or sell options. An extension of the model to incorporate pre-existing
liabilities and endowments reveals the reasons why buyers and sellers trade in options. The model also indicates the importance
of financial equilibrium analysis for the understanding of options prices in incomplete markets.
Received: June 5, 2000 / Accepted: July 12, 2001?Published online December 6, 2001 相似文献
18.
Well known extensions of the classical transportation problem are obtained by including fixed costs for the production of
goods at the supply points (facility location) and/or by introducing stochastic demand, modeled by convex nonlinear costs,
at the demand points (the stochastic transportation problem, [STP]). However, the simultaneous use of concave and convex costs
is not very well treated in the literature. Economies of scale often yield concave cost functions other than fixed charges,
so in this paper we consider a problem with general concave costs at the supply points, as well as convex costs at the demand
points. The objective function can then be represented as the difference of two convex functions, and is therefore called
a d.c. function. We propose a solution method which reduces the problem to a d.c. optimization problem in a much smaller space,
then solves the latter by a branch and bound procedure in which bounding is based on solving subproblems of the form of [STP].
We prove convergence of the method and report computational tests that indicate that quite large problems can be solved efficiently.
Problems up to the size of 100 supply points and 500 demand points are solved.
Received October 11, 1993 / Revised version received July 31, 1995 Published online November 24, 1998 相似文献
19.
Received July 24, 1997 / Revised version received August 9, 1998 Published online January 20, 1999 相似文献
20.
Joanna Józefowska Marek Mika Rafał Różycki Grzegorz Waligóra Jan Weglarz 《Mathematical Methods of Operations Research》2000,52(3):489-499
In this paper a discrete-continuous project scheduling problem is considered. In this problem activities simultaneously require
discrete and continuous resources. The processing rate of each activity depends on the amount of the continuous resource allotted
to this activity at a time. All the resources are renewable ones. The activities are nonpreemtable and the objective is to
minimize the makespan. Discretization of this problem leading to a classical (i.e. discrete) project scheduling problem in
the multi-mode version is presented. A simulated annealing (SA) approach to solving this problem is described and tested computationally
in two versions: with and without finding an optimal continuous resource allocation for the final schedule. In the former
case a nonlinear solver is used for solving a corresponding convex programming problem. The results are compared with the
results obtained using SA for the discrete-continuous project scheduling problem where the nonlinear solver is used for exact
solving the continuous part in each iteration. The results of a computational experiment are analyzed and some conclusions
are included. 相似文献