Wyniki wyszukiwania - BazTech

1

Scheduling for Multi-modal Cyclic Transport Systems

Bocewicz G., Banaszak Z.

Pomiary Automatyka Robotyka

|

2012

|

R. 16, nr 2

106-113

EN

This paper concerns the domain of the multimodal transportation systems composed of buses, trains, trams and subways lines and focuses on the scheduling problems encountered in these systems. Transportation Network Infrastructure (TNI) can be modeled as a network of lines providing cyclic routes for particular kinds of stream-like moving transportation means. Lines are connected by common shared change stations. Depending on TNI timetabling the time of the trip of passengers following different itineraries may dramatically differ, e.g. the same distances along the north-south, and east-west directions may require different travel time. So, the mine question regards of TNI schedulability, e.g. the guarantee the same distances in arbitrarily assumed directions will require approximate traveled time. Considered timetabling problem belongs to NP-hard ones. The declarative model of TNI enabling to formulate cyclic scheduling problem in terms of the constraint satisfaction one is our main contribution. At last, the simulated results manifest the promising properties of the proposed model.

PL

W artykule podejmowana jest problematyka harmonogramowania marszrut pasażerskich realizowanych w multimodalnych systemach komunikacji (MSK) miejskiej obejmujących linie autobusowe, tramwajowe, pociągowe, a także linie metra i linie promowe. MSK modelowany jest jako sieć linii komunikacji miejskiej realizujących swoje cykliczne marszruty transportowe zadaną liczba odpowiednich środków transportu pasażerskiego, tzn. autobusów, tramwajów, pociągów itp. Przyjmuje się, że linie te umożliwiają przesiadanie się pasażerów na wspólnie dzielonych stacjach przesiadkowych. Rozważany problem dotyczy doboru takiej struktury i organizacji ruchu poszczególnych linii, które zapewnią podobne czasy przejazdu (na podobnych dystansach) podróżnych przemieszczających się w różnych kierunkach. Problem ten należy do problemów NP-trudnych. Proponowane w pracy rozwiązanie przyjmuje model deklaratywny MSK sprowadzając rozważany problem harmonogramowania do postaci deterministycznego problemu spełniania ograniczeń. Zamieszczone przykłady implementacji tego problemu w języku programowania z ograniczeniami potwierdzają użyteczność zaproponowanego modelu harmonogramowania MSK.

2

Planowanie przepływu produkcji z wykorzystaniem metod programowania z ograniczeniami

Bzdyra K., Pisz I., Banaszak Z.

Prace Naukowe Instytutu Technologii Maszyn i Automatyzacji Politechniki Wrocławskiej. Konferencje

|

2003

|

Vol. 84, nr 41

145-150

PL

W problemach zarządzania produkcją coraz większą role odgrywa czas podejmowania decyzji. Istnieje konieczność opracowania nowych narzędzi umożliwiających szybkie wariantowanie produkcji obejmujące problemy harmonogramowania marszmtowania i porcjowania. W artykule zaproponowano użycie technik Programowania w Logice Ograniczeń do rozwiązania problemu planowania przepływu produkcji. Wykorzystano język programowania Mozart.

EN

A time require for decision undertaking play an increasing role in production management. It mean there is a need for a new class of DSS enabling to prototype admissible solutions in the case of complex decision problems seen as integration of batching, routing, and scheduling subproblems. The CLP based approach is than proposed as modelling framework. Illustrative example based on Mozart language implementation is presented.

3

Porównanie metod optymalizacji procesów dyskretnych na przykładzie uogólnionego zadania przydziału

Pieńkosz K.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

1999

|

T. 3, z. 1

281-287

PL

W pracy rozpatrywane są różne podejścia do rozwiązywania uogólnionego zadania przydziału w sposób dokładny. W uogólnionym zadaniu przydziału rozpatruje się zbiór zadań do wykonania oraz zbiór zasobów (maszyn) o ograniczonych dostępnościach. Każdemu zadaniu należy przydzielić jeden z wybranych zasobów rezerwując wymaganą ilość czasu jego dostępności. Celem jest takie przydzielenie zadań do zasobów, aby nie przekroczyć dostępności poszczególnych zasobów i minimalizować (bądź maksymalizować) sumaryczne koszty przydziału. Przedstawione zagadnienie jest problemem 7VP-trudnym i nawet przy umiarkowanej liczbie zadań i zasobów pojawiają się trudności z jego rozwiązywaniem. Rozwiązując uogólnione zadanie przydziału badano efektywność stosunkowo nowego podejścia optymalizacji dyskretnej jakim jest programowanie w logice ograniczeń (ang. constraint logie programming). Użyto do tego celu oprogramowania firmy ILOG. Otrzymane rezultaty i czasy rozwiązywania porównano z klasycznymi metodami optymalizacji, tzn. specjalizowaną metodą podziału i oszacowań oraz całkowitoliczbo-wym programowaniem liniowym. Eksperymenty obliczeniowe i porównania metod zostały przeprowadzone na danych zaczerpniętych z literatury.

EN

Different approaches to the exact solution of the generalised assignment problem are considered in the paper. The generalised assignment problem is the problem of finding an assignment of a set of capacity constrained resources (machines) to a set of jobs such that each job is assigned to exactly one resource. The objective is to minimise (or maximise) the total costs of assignment subject to the capacities of the resources. The problem is known to be NP-hard, and it is hard form a computational point of view even for a moderate number of jobs and resources. The efficiency of the constraint logic programming which is a relatively new approach to discrete optimisation has been examined by solving the generalised assignment problem. ILOG software has been applied for these experiments. Results of computations have been compared with the classical optimisation methods, i.e. a specialised branch and bound method and integer programming. Computational experiments and comparison has been performed on the test problems taken from the literature.