共查询到20条相似文献,搜索用时 15 毫秒
1.
Truncated branch-and-bound,schedule-construction,and schedule-improvement procedures for resource-constrained project scheduling 总被引:2,自引:0,他引:2
We present heuristic procedures for approximately solving large project scheduling problems with general temporal and resource
constraints. In particular, we propose several truncated branch-and-bound techniques, priority-rule methods, and schedule-improvement
procedures of types tabu search and genetic algorithm. A detailed experimental performance analysis compares the different
heuristics devised and shows that large problem instances with up to 1000 activities and several resources can efficiently
be solved with sufficient accuracy.
Received: July 26, 2000 / Accepted: May 15, 2001 相似文献
Received: July 26, 2000 / Accepted: May 15, 2001 相似文献
2.
For many applications of project scheduling to real-life problems, it is necessary to take into account calendars specifying
time intervals during which some resources such as manpower or machines are not available. Whereas the execution of certain
activities like packaging may be suspended during breaks, other activities cannot be interrupted due to technical reasons.
Minimum and maximum time lags between activities may depend on calendars, too. In this paper, we address the problem of scheduling
the activities of a project subject to calendar constraints. We devise efficient algorithms for computing earliest and latest
start and completion times of activities. Moreover, we sketch how to use these algorithms for developing priority-rule methods
coping with renewable-resource constraints and calendars.
Received: July 26, 2000 / Accepted: May 15, 2001 相似文献
Received: July 26, 2000 / Accepted: May 15, 2001 相似文献
3.
Roland Heilmann 《OR Spectrum》2001,23(3):335-357
This paper presents a heuristic solution procedure for a very general resource–constrained project scheduling problem. Here,
multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum
time lags between different activities may be given. The objective is to determine a mode and a start time for each activity
such that the temporal and resource constraints are met and the project duration is minimized. Project scheduling problems
of this type occur e.g. in process industries. The heuristic is a multi–pass priority–rule method with backplanning which
is based on an integration approach and embedded in random sampling. Its performance is evaluated within an experimental performance
analysis for problem instances of real–life size with 100 activities and up to 5 modes per activity.
Received: September 22, 2000 / Accepted: May 18, 2001 相似文献
Received: September 22, 2000 / Accepted: May 18, 2001 相似文献
4.
An Advanced Planning System (APS) offers support at all planning levels along the supply chain while observing limited resources.
We consider an APS for process industries (e.g. chemical and pharmaceutical industries) consisting of the modules network
design (for long–term decisions), supply network planning (for medium–term decisions), and detailed production scheduling
(for short–term decisions). For each module, we outline the decision problem, discuss the specifi cs of process industries,
and review state–of–the–art solution approaches. For the module detailed production scheduling, a new solution approach is
proposed in the case of batch production, which can solve much larger practical problems than the methods known thus far.
The new approach decomposes detailed production scheduling for batch production into batching and batch scheduling. The batching
problem converts the primary requirements for products into individual batches, where the work load is to be minimized. We
formulate the batching problem as a nonlinear mixed–integer program and transform it into a linear mixed–binary program of
moderate size, which can be solved by standard software. The batch scheduling problem allocates the batches to scarce resources
such as processing units, workers, and intermediate storage facilities, where some regular objective function like the makespan
is to be minimized. The batch scheduling problem is modelled as a resource–constrained project scheduling problem, which can
be solved by an efficient truncated branch–and–bound algorithm developed recently. The performance of the new solution procedures
for batching and batch scheduling is demonstrated by solving several instances of a case study from process industries. 相似文献
5.
In this paper we study a production system consisting of a group of parallel machines producing multiple job types. Each
machine has its own queue and it can process a restricted set of job types only. On arrival a job joins the shortest queue
among all queues capable of serving that job. Under the assumption of Poisson arrivals and identical exponential processing
times we derive upper and lower bounds for the mean waiting time. These bounds are obtained from so-called flexible bound
models, and they provide a powerful tool to efficiently determine the mean waiting time. The bounds are used to study how
the mean waiting time depends on the amount of overlap (i.e. common job types) between the machines.
Received: February 8, 2000 / Accepted: November 28, 2000 相似文献
Received: February 8, 2000 / Accepted: November 28, 2000 相似文献
6.
A Theory of Complexity, Periodicity and the Design Axioms 总被引:2,自引:1,他引:1
Nam P. Suh 《Research in Engineering Design》1999,11(2):116-132
One of the topics that has received the attention of mathematicians, scientists and engineers is the notion of complexity.
The subject is still being debated, as it lacks a common definition of complexity, concrete theories that can predict complex
phenomena, and the mathematical tools that can deal with problems involving complexity. In axiomatic design, complexity is
defined only when specific functional requirements or the exact nature of the query are defined. Complexity is defined as
a measure of uncertainty in achieving a set of specific functions or functional requirements. Complexity is related to information,
which is defined in terms of the probability of success of achieving the Functional Requirements (FRs). There are two classes
of complexity: time-dependent complexity and time-independent complexity. There are two orthogonal components of time-independent
complexity, i.e., real complexity and imaginary complexity. The vector sum is called absolute complexity. Real complexity of coupled design is larger than that of uncoupled or decoupled designs. Imaginary complexity can be reduced
when the design matrix is known. As an example of time-independent imaginary complexity, the design of a printing machine
based on xerography is discussed. There are two kinds of time-dependent real complexity: time-dependent combinatorial complexity and time-dependent periodic complexity. Using a robot-scheduling problem as an example, it is shown that a coupled design with a combinatorial complexity can be
reduced to a decoupled design with periodic complexity. The introduction of periodicity simplifies the design by making it
deterministic, which requires much less information. Whenever a combinatorial complexity is converted to a periodic complexity,
complexity and uncertainty is reduced and design simplified. 相似文献
7.
The paper deals with batch scheduling problems in process industries where final products arise from several successive chemical
or physical transformations of raw materials using multi–purpose equipment. In batch production mode, the total requirements
of intermediate and final products are partitioned into batches. The production start of a batch at a given level requires
the availability of all input products. We consider the problem of scheduling the production of given batches such that the
makespan is minimized. Constraints like minimum and maximum time lags between successive production levels, sequence–dependent
facility setup times, finite intermediate storages, production breaks, and time–varying manpower contribute to the complexity
of this problem. We propose a new solution approach using models and methods of resource–constrained project scheduling, which
(approximately) solves problems of industrial size within a reasonable amount of time.
Received: October 15, 1999 / Accepted: March 21, 2000 相似文献
8.
Planning and scheduling in the process industry 总被引:15,自引:0,他引:15
Josef Kallrath 《OR Spectrum》2002,24(3):219-250
Since there has been tremendous progress in planning and scheduling in the process industry during the last 20 years, it
might be worthwhile to give an overview of the current state-of-the-art of planning and scheduling problems in the chemical
process industry. This is the purpose of the current review which has the following structure: we start with some conceptional
thoughts and some comments on special features of planning and scheduling problems in the process industry. In Section 2 the
focus is on planning problems while in Section 3 different types of scheduling problems are discussed. Section 4 presents
some solution approaches especially those applied to a benchmark problem which has received considerable interest during the
last years. Section 5 allows a short view into the future of planning and scheduling. In the appendix we describe the Westenberger-Kallrath
problem which has already been used extensively as a benchmark problem for planning and scheduling in the process industr
y. 相似文献
9.
A scheduling method for Berth and Quay cranes 总被引:12,自引:2,他引:10
This paper discusses a method for scheduling Berth and Quay cranes, which are critical resources in port container terminals.
An integer programming model is formulated by considering various practical constraints. A two-phase solution procedure is
suggested for solving the mathematical model. The first phase determines the Berthing position and time of each vessel as
well as the number of cranes assigned to each vessel at each time segment. The subgradient optimization technique is applied
to obtain a near-optimal solution of the first phase. In the second phase, a detailed schedule for each Quay crane is constructed
based on the solution found from the first phase. The dynamic programming technique is applied to solve the problem of the
second phase. A numerical experiment was conducted to test the performance of the suggested algorithms.
RID="*"
ID="*" This research has been supported in part by Brain Korea 21 Program (1999–2002).
Correspondence to: Y.-M. Park 相似文献
10.
Mohamed Abdel-Basset Ahmed Sleem Asmaa Atef Yunyoung Nam Mohamed Abouhawwash 《计算机、材料和连续体(英文)》2022,70(1):847-874
Project scheduling is a key objective of many models and is the proposed method for project planning and management. Project scheduling problems depend on precedence relationships and resource constraints, in addition to some other limitations for achieving a subset of goals. Project scheduling problems are dependent on many limitations, including limitations of precedence relationships, resource constraints, and some other limitations for achieving a subset of goals. Deterministic project scheduling models consider all information about the scheduling problem such as activity durations and precedence relationships information resources available and required, which are known and stable during the implementation process. The concept of deterministic project scheduling conflicts with real situations, in which in many cases, some data on the activity' s durations of the project and the degree of availability of resources change or may have different modes and strategies during the process of project implementation for dealing with multi-mode conditions surrounded by projects and their activity durations. Scheduling the multi-mode resource-constrained project problem is an optimization problem whose minimum project duration subject to the availability of resources is of particular interest to us. We use the multi-mode resource allocation and scheduling model that takes into account the dynamicity features of all parameters, that is, the scheduling process must be flexible to dynamic environment features. In this paper, we propose five priority heuristic rules for scheduling multi-mode resource-constrained projects under dynamicity features for more realistic situations, in which we apply the proposed heuristic rules (PHR) for scheduling multi-mode resource-constrained projects. Five projects are considered test problems for the PHR. The obtained results rendered by these priority rules for the test problems are compared by the results obtained from 10 well-known heuristics rules rendered for the same test problems. The results in many cases of the proposed priority rules are very promising, where they achieve better scheduling dates in many test case problems and the same results for the others. The proposed model is based on the dynamic features for project topography. 相似文献
11.
One of the major planning issues in large scale automated transportation systems is so-called empty vehicle management, the timely supply of vehicles to terminals in order to reduce cargo waiting times. Motivated by a Dutch pilot project on
an underground cargo transportation system using Automated Guided Vehicles (AGVs), we developed several rules and algorithms
for empty vehicle management, varying from trivial First-Come, First-Served (FCFS) via look-ahead rules to integral planning.
For our application, we focus on attaining customer service levels in the presence of varying order priorities, taking into
account resource capacities and the relation to other planning decisions, such as terminal management. We show how the various
rules are embedded in a framework for logistics control of automated transportation networks. Using simulation, the planning
options are evaluated on their performance in terms of customer service levels, AGV requirements and empty travel distances.
Based on our experiments, we conclude that look-ahead rules have significant advantages above FCFS. A more advanced so-called
serial scheduling method outperforms the look-ahead rules if the peak demand quickly moves amongst routes in the system.
Received: June 21, 2000 / Accepted: January 22, 2001 相似文献
12.
We consider a single-stage single-product production system. Produced units may be non-defective, reworkable defective, or
non-reworkable defective. The system switches between production and rework. After producing a fixed number (N) of units, all reworkable defective units are reworked. Reworkable defectives are perishable or can become technologically
obsolete. We assume that the rework time and the rework cost increase linearly with the time that a unit is held in stock.
Therefore, N should not be too large. On the other hand, N should not be too small either, since there are set-up times and costs associated with switching between production and rework.
For a given N, we derive an explicit expression for the average profit (sales revenue minus costs). Using this expression, the optimal
value for N can be determined numerically. Moreover, it is easy to perform a sensitivity analysis, as we illustrate.
RID="*"
ID="*"The research of Dr. Ruud H. Teunter has been made possible by a fellowship of the Royal Netherlands Academy of Arts
and Sciences. The research presented in this paper is part of the research on re-use in the context of the EU sponsored TMR
project REVersed LOGistics (ERB 4061 PL 97-5650) in which take part the Otto-von-Guericke Universitaet Magdeburg (D), the
Erasmus University Rotterdam (NL), the Eindhoven University of Technology (NL), INSEAD (F), the Aristoteles University of
Thessaloniki (GR), and the University of Piraeus (GR). We thank the anonymous referees for their many helpful comments.
Correspondence to: R. H. Teunter 相似文献
13.
Batch process industries are characterized by complex precedence relationships between operations, which renders the estimation
of an acceptable workload very difficult. A detailed schedule based model can be used for this purpose, but for large problems
this may require a prohibitive large amount of computation time. We propose a regression based model to estimate the makespan
of a set of jobs. We extend earlier work based on deterministic processing times by considering Erlang-distributed processing
times in our model. This regression-based model is used to support customer order acceptance. Three order acceptance policies
are compared by means of simulation experiments: a scheduling policy, a workload policy and a regression policy. The results
indicate that the performance of the regression policy can compete with the performance of the scheduling policy in situations
with high variety in the job mix and high uncertainty in the processing times.
Correspondence to: C.V. Ivanescu 相似文献
14.
Many fast moving consumers good manufacturing companies produce a moderate number of intermediates that are combined in many
different ways to generate an enormous variety of end products. To do that, such companies usually run continuous production
plants in a make-to-stock environment. The process structure includes a fabrication area yielding basic intermediates that
are stocked in a large middle storage space, and a packing sector where finished products usually comprising several intermediates
are manufactured. Intermediates all undergo the same sequence of processing stages and the production of any campaign is sequentially
allocated to an ordered set of end products. An MILP continuous time scheduling problem formulation handling independently
assignment and sequencing decisions and considering sequence-dependent setup times and specific due dates for export orders
has been developed. The problem objective is to meet all end-product demands at minimum make-span. The proposed model is able
to account for assorted products, multiple campaigns for a particular intermediate even at the same unit and the consecutive
allocation of an intermediate campaign to different finished products. Moreover, it can easily embed powerful preordering
rules to yielding reduced MILP formulations so as to tackle real-world industrial problems at low computational cost. The
approach has been successfully applied to large-scale industrial examples.
RID="*"
ID="*" The authors acknowledge financial support from FONCYT under Grant 14-07004, and from “Universidad Nacional del Litoral”
under CAI+D 121.
Correspondence to: J. Cerdá 相似文献
15.
We present results of a benchmark test evaluating the resource allocation capabilities of the project management software
packages Acos Plus.1 8.2, CA SuperProject 5.0a, CS Project Professional 3.0, MS Project 2000, and Scitor Project Scheduler
8.0.1. The tests are based on 1560 instances of precedence– and resource–constrained project scheduling problems. For different
complexity scenarios, we analyze the deviation of the makespan obtained by the software packages from the best feasible makespan
known. Among the tested software packages, Acos Plus.1 and Project Scheduler show the best resource allocation performance.
Moreover, our numerical analysis reveals a considerable performance gap between the implemented methods and state–of–the–art
project scheduling algorithms, especially for large–sized problems. Thus, there is still a significant potential for improving
solutions to resource allocation problems in practice.
相似文献
16.
Karl-Heinz Küfer Alexander Scherrer Michael Monz Fernando Alonso Hans Trinkaus Thomas Bortfeld Christian Thieke 《OR Spectrum》2003,25(2):223-249
Abstract. Radiation therapy planning is often a tight rope walk between dangerous insufficient dose in the target volume and life threatening
overdosing of organs at risk. Finding ideal balances between these inherently contradictory goals challenges dosimetrists
and physicians in their daily practice. Todays inverse planning systems calculate treatment plans based on a single evaluation
function that measures the quality of a radiation treatment plan. Unfortunately, such a one dimensional approach cannot satisfactorily
map the different backgrounds of physicians and the patient dependent necessities. So, too often a time consuming iterative
optimization process between evaluation of the dose distribution and redefinition of the evaluation function is needed. In
this paper we propose a generic multi-criteria approach based on Pareto's solution concept. For each entity of interest –
target volume or organ at risk – a structure dependent evaluation function is defined measuring deviations from ideal doses
that are calculated from statistical functions. A reasonable bunch of clinically meaningful Pareto optimal solutions are stored
in a data base, which can be interactively searched by physicians. The system guarantees dynamic planning as well as the discussion
of tradeoffs between different entities. Mathematically, we model the inverse problem as a multi-criteria linear programming
problem. Because of the large scale nature of the problem it is not possible to solve the problem in a 3D-setting without
adaptive reduction by appropriate approximation schemes. Our approach is twofold: First, the discretization of the continuous
problem results from an adaptive hierarchical clustering process which is used for a local refinement of constraints during
the optimization procedure. Second, the set of Pareto optimal solutions is approximated by an adaptive grid of representatives
that are found by a hybrid process of calculating extreme compromises and interpolation methods.
Correspondence to: K.-H. Küfer 相似文献
17.
Plant co-ordination in pharmaceutics supply networks 总被引:3,自引:0,他引:3
The production of active ingredients in the chemical-pharmaceutical industry involves numerous production stages with cumulative
lead times of up to two years. Mainly because of rigorous purity requirements and the need of extensive cleaning of the equipment
units, production is carried out in campaigns, i.e. multiple batches of the same product type are produced successively before
changing to another product type. Each campaign requires a specific configuration of equipment units according to the recipes
of the particular chemical process. In the chemical-pharmaceutical industry, production stages are often assigned to different
locations, even different countries. Hence the co-ordination of plant operations within the resulting multi-national supply
network is of major importance. A key issue is the co-ordination of campaign schedules at different production stages in the
various plants. In practice, it is almost impossible to determine exact optimal solutions to the corresponding complex supply
network problem with respect to overall logistics costs. In order to reduce the required computational effort, we introduce
several aggregation schemes and a novel MILP model formulation which is based on a continuous representation of time. Moreover,
we propose an iterative near-optimal solution procedure which can be successfully applied to even exceptionally large real
life problem instances. The applicability of the approach suggested is shown using a case study from industry.
Correspondence to: H.-O. Günther 相似文献
18.
Antonio Gómez-Corral 《OR Spectrum》2001,23(3):395-409
In the design of waiting facilities for the units in a retrial queue, it is of interest to know probability distributions
of extreme values of the orbit length. The purpose of this paper is to investigate the asymptotic behavior of the maximum
orbit length in the queue with constant retrial rate, as the time interval increases. From the classical extreme value theory, we observe that,
under standard linear normalizations, the maximum orbit length up to the nth time the positive recurrent queue becomes empty does not have a limit distribution. However, by allowing the parameters
to vary with n, we prove the convergence of maximum orbit lengths to three possible limit distributions when the traffic intensity approaches 1 from below and n approaches infinity.
Received: October 7, 1999 / Accepted: November 21, 2000 相似文献
Received: October 7, 1999 / Accepted: November 21, 2000 相似文献
19.
Guido Berning Marcus Brandenburg Korhan Gürsoy Vipul Mehta Franz-Josef Tölle 《OR Spectrum》2002,24(4):371-401
This paper considers a complex scheduling problem in the chemical process industry involving batch production. The application
described comprises a network of production plants with interdependent production schedules, multi-stage production at multi-purpose
facilities, and chain production. The paper addresses three distinct aspects: (i) a scheduling solution obtained from a genetic algorithm based optimizer, (ii) a mechanism for collaborative planning among the involved plants, and (iii) a tool for manual updates and schedule changes. The tailor made optimization algorithm simultaneously considers alternative
production paths and facility selection as well as product and resource specific parameters such as batch sizes, and setup
and cleanup times. The collaborative planning concept allows all the plants to work simultaneously as partners in a supply
chain resulting in higher transparency, greater flexibility, and reduced response time as a whole. The user interface supports
monitoring production schedules graphically and provides custom-built utilities for manual changes to the production schedule,
investigation of various what-if scenarios, and marketing queries.
RID="*"
ID="*" The authors would like to thank Hans-Otto Günther and Roland Heilmann for helpful comments on draft versions of this
paper. 相似文献
20.
MULTI-PROJECT SCHEDULING WITH EXPLICIT LATENESS COSTS 总被引:5,自引:0,他引:5
We propose a heuristic procedure for planning and scheduling multiple projects subject to limited resource availabilities. We depart from previous research in that explicit lateness costs for each project are considered. Our procedure involves aggregate analysis using linear programming to determine target resource loading profiles for each project that optimize trade-offs of lateness costs among projects, followed by detailed multi-project scheduling consistent with the target profiles. Target profiles and detailed schedules are iteratively modified through N iterations, where N is the number of projects. The procedure can be used to jointly schedule previously committed and newly proposed projects, as well as to assign due dates to proposed projects. We compare the performance of our procedure to that of the traditional minimum slack heuristic, as well to a simple extension of the minimum slack rule that accounts for lateness costs. On a set of 60 multi-project test problems adapted from the Patterson set of single-project problems, results are very favorable for our proposed algorithm. 相似文献