Control and Cybernetics

Items from 1 to 11 out of 11 results

article

A timed Petri net framework to find optimal IRIS schedules

M. Werner

Control and Cybernetics > 2006 > Vol. 35, no 3 > 703-719

IRIS (increasing reward with increasing service) realtime scheduling appears frequently in real-time control applications such as heuristic control. IRIS requires not only meeting deadlines, but also finding the schedule with the best result (highest reward). In this paper, a framework is presented that uses Timed Petri nets (TPN) to transform an IRIS problem into a dynamic programming (DP) problem,...

article

The corridor method: a dynamic programming inspired metaheuristic

M. Sniedovich, S. Viß

Control and Cybernetics > 2006 > Vol. 35, no 3 > 551-578

This paper presents a dynamic programming inspired metaheuristic called Corridor Method. It can be classified as a method-based iterated local search in that it deploys method-based neighborhoods. By this we mean that the search for a new candidate solution is carried out by a fully-fledged optimization method and generates a global optimal solution over the neighborhood. The neighborhoods are thus...

article

DP2PN2Solver: A flexible dynamic programming solver software tool

H. Mauch

Control and Cybernetics > 2006 > Vol. 35, no 3 > 687-702

Dynamic programming (DP) is a very general optimization technique, which can be applied to numerous decision problems that typically require a sequence of decisions to be made. The solver software DP2PN2Solver presented in this paper is a general, flexible, and expandable software tool that solves DP problems. It consists of modules on two levels. A level one module takes the specification of a discrete...

article

Approximating the solution of a dynamic, stochastic multiple knapsack problem

J. C. Hartman, T. C. Perry

Control and Cybernetics > 2006 > Vol. 35, no 3 > 535-550

We model an environment where orders arrive probabilistically over time, with their revenues and capacity requirements becoming known upon arrival. The decision is whether to accept an order, receiving a reward and reserving capacity, or reject an order, freeing capacity for possible future arrivals. We model the dynamic, stochastic multiple knapsack problem (DSMKP) with stochastic dynamic programming...

article

Dijkstra's algorithm revisited: the dynamic programming connexion

M. Sniedovich

Control and Cybernetics > 2006 > Vol. 35, no 3 > 599-620

Dijkstra's Algorithm is one of the most popular algorithms in computer science. It is also popular in operations research. It is generally viewed and presented as a greedy algorithm. In this paper we attempt to change this perception by providing a dynamic programming perspective on the algorithm. In particular, we are reminded that this famous algorithm is strongly inspired by Bellman's Principle...

article

Dynamic programming in constrained Markov decision

A. B. Piunovskiy

Control and Cybernetics > 2006 > Vol. 35, no 3 > 645-660

We consider a discounted Markov Decision Process (MDP) supplemented with the requirement that another discounted loss must not exceed a specified value, almost surely. We show that he problem can be reformulated as a standard MDP and solved using the Dynamic Programming approach. An example on a controlled queue is presented. In the last section, we briefly reinforce the connection of the Dynamic...

article

Tabu search: global intensification using dynamic programming

C. Wilbaut, S. Hanafi, A. Fréville, S. Balev

Control and Cybernetics > 2006 > Vol. 35, no 3 > 579-598

Tabu search has proven highly successful in solving hard combinatorial optimization problems. In this paper, we propose a hybrid method that combines adaptive memory, sparse dynamic programming, and reduction techniques to reduce and explore the search space. Our approach starts with a bi-partition of the variables, involving a small core problem, which never exceeds 15 variables, solved using the...

article

Adaptive resource allocation to stochastic multimodal projects: a distributed platform implementation in Java

A. P. Tereso, J. R. Mota, R. J. Lameiro

Control and Cybernetics > 2006 > Vol. 35, no 3 > 661-686

This paper presents the implementation of the dynamic programming model (introduced in a previous paper) for the resolution of the adaptive resource allocation problem in stochastic multimodal project networks. A distributed platform using an Object Oriented language, Java, is used in order to take advantage of the available computational resources.

article

Time Petri nets state space reduction using dynamic programming

L. Popova-Zeugmann

Control and Cybernetics > 2006 > Vol. 35, no 3 > 721-748

In this paper a parametric description for the state space of an arbitrary TPN is given. An enumerative procedure for reducing the state space is introduced. The reduction is defined as a truncated multistage decision problem and solved recursively. A reachability graph is denned in a discrete way by using the reachable integer-states of the TPN.

article

Dynamic Programming: an overview

M. Sniedovich

Control and Cybernetics > 2006 > Vol. 35, no 3 > 513-533

Dynamic programing is one of the major problem-solving methodologies in a number of disciplines such as operations research and computer science. It is also a very important and powerful tool of thought. But not all is well on the dynamic programming front. There is definitely lack of commercial software support and the situation in the classroom is not as good as it should be. In this paper we take...

article

Canonical greedy algorithms and dynamic programming

A. Lew

Control and Cybernetics > 2006 > Vol. 35, no 3 > 621-643

There has been little work on how to construct greedy algorithms to solve new optimization problems efficiently. Instead, greedy algorithms have generally been designed on an ad hoc basis. On the other hand, dynamic programming has a long history of being a useful tool for solving optimization problems, but is often inefficient. We show how dynamic programming can be used to derive efficient greedy...

Filter options

Volume:
Vol. 35, no 3
Year:
2006

Publication date

Set your own date range

Keywords

DYNAMIC PROGRAMMING (9)
PROGRAMOWANIE DYNAMICZNE (9)
CURSE OF DIMENSIONALITY (2)
GREEDY ALGORITHM (2)
PRINCIPLE OF OPTIMALITY (2)
SUCCESSIVE APPROXIMATION (2)
TRAVELING SALESMAN PROBLEM (2)
ACTIVITY NETWORKS (1)
ALGORYTM DIJKSTRY (1)
APPROXIMATE DYNAMIC PROGRAMMING (1)
BADANIA OPERACYJNE (1)
BELLMAN NET (1)
CLUSTER (1)
COMPUTER SCIENCE (1)
CONSTRAINTS (1)
CORRIDOR METHOD (1)
CRITICAL PATH (1)
DIJKSTRA (1)
DIJKSTRA'S ALGORITHM (1)
DISTRIBUTED PLATFORM (1)
DUALITY (1)
DUALNOŚĆ (1)
GLOBAL INTENSIFICATION (1)
GLOBAL OPTIMIZATION (1)
INCREASING REWARD WITH INCREASING SERVICE (1)
INTEGER STATE (1)
IRIS (1)
KLASTER (1)
LINEAR PROGRAMMING (1)
MARKOV DECISION PROCESS (MDP) (1)
MATRIX CHAIN MULTIPLICATION PROBLEM (1)
METAHEURISTICS (1)
METHOD-BASED (1)
MODEL SIECI PETRI (1)
MOVE-BASED (1)
MULTIDIMENSIONAL 0-1 KNAPSACK PROBLEM (1)
MYOPIC CONTROL STRATEGY (1)
OPERATIONS RESEARCH (1)
OPTIMIZATION (1)
OPTIMIZATION SOFTWARE (1)
OPTYMALIZACJA (1)
PETRI NET MODEL (1)
PROGRAMOWANIE LINIOWE (1)
PULL (1)
PUSH (1)
QUEUING SYSTEM (1)
REACHABILITY GRAPH (1)
REAL TIME (1)
RESOURCE ALLOCATION (1)
SCHEDULING (1)
SIEĆ BELLMANA (1)
STATE SPACE REDUCTION (1)
STOCHASTIC DYNAMIC PROGRAMMING (1)
SYSTEM KOLEJEK (1)
TABU SEARCH (1)
TIME PETRI NET (1)
TIMED PETRI NETS (1)
VERY LARGE NEIGHBORHOODS (1)
more

INFONA - science communication portal

Control and Cybernetics

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options