PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 19

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  scheduling problem
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Optimizing the Job Shop Scheduling Problem with a no Wait Constraint by Using the Jaya Algorithm Approach
Bougloula Aimade Eddine
Management and Production Engineering Review
|
2023
|
Vol. 14, No. 3
148--155
EN
This work is interested to optimize the job shop scheduling problem with a no wait constraint. This constraint occurs when two consecutive operations in a job must be processed without any waiting time either on or between machines. The no wait job shop scheduling problem is a combinatorial optimization problem. Therefore, the study presented here is focused on solving this problem by proposing strategy for making Jaya algorithm applicable for handling optimization of this type of problems and to find processing sequence that minimizes the makespan (Cmax). Several benchmarks are used to analyze the performance of this algorithm compared to the best-known solutions.
2
Content available Iterated Local Search for Foundry Lot-sizing and Scheduling Problem with Setup Costs
Stawowy A., Duda J.
Archives of Foundry Engineering
|
2017
|
Vol. 17, iss. 4
161--164
EN
The paper presents a novel Iterated Local Search (ILS) algorithm to solve multi-item multi-family capacitated lot-sizing problem with setup costs independent of the family sequence. The model has a direct application to real production planning in foundry industry, where the goal is to create the batches of manufactured castings and the sequence of the melted metal loads to prevent delays in delivery of goods to clients. We extended existing models by introducing minimal utilization of furnace capacity during preparing melted alloy. We developed simple and fast ILS algorithm with problem-specific operators that are responsible for the local search procedure. The computational experiments on ten instances of the problem showed that the presence of minimum furnace utilization constraint has great impact on economic and technological conditions of castings production. For all test instances the proposed heuristic is able to provide the results that are comparable to state-of-the art commercial solver.
3
Content available The Classification Of Scheduling Problems Under Production Uncertainty
Wojakowski P., Warżołek D.
Research in Logistics & Production
|
2014
|
Vol. 4, No. 3
245--256
EN
One of the most important issue regarding scheduling problem is production uncertainty. From the standpoint of real-world scheduling problem, it is necessary to find solution of building the schedule which can be insensitive to production disruptions such as machine breakdowns, incorrectly estimated time interval of machines maintenance, absence of workers, unavailability of materials or tooling, production defects, variable processing times, etc. This research study is conducted to answer the question: how the researchers cope with the problem of production uncertainty taking into account the scheduling problem? Our investigation focuses on approaches developed for scheduling with production uncertainty consideration. Among these approaches the most popular ones are: reactive scheduling, proactive scheduling, predictive scheduling and robust predictive-reactive approaches. A brief explanation of individual approaches are presented. Further, models of uncertainty used in scheduling approaches are highlighted.
4
Content available remote Solving the International Timetabling Competition : a Deterministic Approach
Chavez-Bosquez O., Pozos-Parra P., Lengyel F.
Fundamenta Informaticae
|
2011
|
Vol. 113, nr 1
1-18
EN
The Course Timetabling Problem consists of the weekly scheduling of lectures of a collection of university courses, subject to certain constraints. The International Timetabling Competitions, ITC-2002 and ITC-2007, have been organized with the aim of creating a common formulation for comparison of solution proposals. This paper discusses the design and implementation of an extendable family of sorting-based mechanisms, called Sort Then Fix (STF) algorithms. ITC-2002 and ITC-2007 Post Enrolment based Course Timetabling problem instances were used in this study. The STF approach is deterministic, and does not require swapping or backtracking. Almost all solutions run in less than 10% of the ITC-2002 and less than 2% of the ITC-2007 benchmark times, respectively.
5
Content available remote On job models in power management problems
Różycki R., Węglarz J.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2009
|
Vol. 57, nr 2
147-151
EN
In the paper a model of job processing is presented where processing speed is related to the amount of power allotted to this job at a moment. Basic time-optimal results are showed assuming that energy is treated as a scarce doubly-constrained resource in a computer system. The proposed approach is applicable to the practical power management problems appearing in modem portable device systems.
6
Równoważenie obciążenia w problemach rozdziału zasobów dyskretnych - podejścia heurystyczne
Mika M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
73-78
PL
Rozważany jest problem rozdziału zasobów dyskretnych, w którym zasadniczym celem jest równoważenie obciążenia zasobowego. W problemie tym czynności projektu są szeregowane w taki sposób, by me naruszyć ograniczeń kolejnościowych i linii krytycznej dla całego projektu przy jednoczesnej minimalizacji funkcji celu odzwierciedlającej zmiany poziomu wykorzystania zasobów. Przedstawiono trzy klasy takich funkcji oraz zaproponowano pewne podejścia heurystyczne.
EN
Resource leveling problem is considered. The main objective of this problem is to minimize the fluctuations of the resource usage profiles. There are two types of constraints in this problem: a deadline for the entire project as well as precedence constraints between pairs of projects' activities. Three classes of objective functions are distinguished. Some heuristics are proposed to solve the problem.
7
Problem dystrybucji z terminami dostaw
Bożejko W., Walczyński M., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
25-30
PL
W pracy przedstawiono algorytm oparty na metodzie przeszukiwania z tabu, rozwiązywania problemu dystrybucji z terminami dostaw. Jest on równoważny pewnemu jednomaszynowemu problemowi szeregowania, który w literaturze jest oznaczany przez 1|sij|ΣwiTi i należy do klasy problemów silnie NP-trudnych. Wykonano obliczenia na reprezentatywnej grupie danych, a otrzymane wyniki porównano z najlepszymi znanymi w literaturze.
EN
A tabu search algorithm is proposed in the paper to solve a distribution problem with due dates. It is equivalent to a single machine scheduling problem, which is described by 1|sij|ΣwiTi in the literature and it belongs to strongly NP-hard class. Calculations were done on representative group of test instances, obtained results were compared to the best known solutions from the literature.
8
Planowanie pracy zespołu robotów wielofunkcyjnych w warunkach niepewności
Bocewicz G., Wójcik R., Banaszak Z.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
129-140
PL
Planowanie pracy zespołu robotów wielofunkcyjnych sprowadza się do problemów decyzyjnych związanych z rozstrzyganiem konfliktów zasobowych w sytuacjach, kiedy jednoczesne wykonanie różnych operacji wymaga dostępu do współdzielonych robotów - dyskretnych zasobów odnawialnych. Przyjęty model referencyjny problemu planowania pracy robotów dopuszcza występowanie zarówno ostrych, jak i rozmytych zmiennych decyzyjnych - czasów alokacji robotów.
EN
Scheduling of multi-robot in a multi-product flow shop can be seen as an allocation problem of shared renewable resources and then can be resolved in terms of constraint satisfaction problem. To make it possible a reference model of a constraint satisfaction problem is developed, and provided case illustrates its usability in an example taking into account both an accurate and an uncertain specification of robots operation time.
9
Nowe wykorzystanie metody blokowej w konstrukcji algorytmów heurystycznych dla ogólnego problemu przepływowego
Grabowski J., Pempera J.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
45-50
PL
Własności blokowe są z powodzeniem stosowane do usuwania ruchów nierokujących poprawy dla wielu otoczeń stosowanych w algorytmach popraw dla problemów szeregowania. W pracy, dla ogólnego problemu przepływowego, zaproponowano nowy sposób przeglądania otoczenia, który pozwala na eliminację znacznie większego zbioru ruchów. W celu sprawdzenia efektywności metody przeprowadzono eksperyment komputerowy na instancjach Taillarda.
EN
The block properties are successfully applied to a priory eliminate non promising moves from the neighborhood for many local search algorithm of solving scheduling problems. In this paper, for the general flowshop problem, it presents new method of searching the neighborhood, which gives rise to eliminate highly greater set of moves. To validate efficiency of the proposed method, computational experiment have been executed on a well-known Taillard's benchmarks.
10
Content available remote Zastosowanie środowisk deklaratywnych do wspomagania decyzji harmonogramowania produkcji
Sitek P., Wikarek J.
Pomiary Automatyka Robotyka
|
2008
|
R. 12, nr 2
274--283
PL
Problemy harmonogramowania pojawiają się na wielu poziomach problemów decyzyjnych dotyczących produkcji. Na ogół charakteryzują się dużą liczbą ograniczeń (kolejności wykonania zadań, dostępnych zasobów itp.). Ze względu na zło- żoność obliczeniową wynikającą z dużej liczby zmiennych decyzyjnych całkowitoliczbowych oraz charakteru problemów są klasyfikowane jako zadania NP-trudne. Z tego powodu tradycyjne podejścia do rozwiązania tych problemów opierające się na programowaniu matematycznym są często nieefektywne. W odróżnieniu od podejścia tradycyjnego gdzie modelowanie ograniczeń problemu zwykle jest sztuczne (użycie dodatkowych zmiennych 0-1) w środowisku programowania w logice z ograniczeniami (CLP – Constrain Logic Programming) modelowanie ograniczeń jest naturalne i wynika z paradygmatu na którym środowisko CLP zostało oparte. Środowisko CLP jest środowiskiem deklaratywnym. W pracy zaproponowano wykorzystanie środowisk deklaratywnych (CLP, SQL, HTML) do budowy systemu wspomagania decyzji harmonogramowania produkcji.
EN
Scheduling problems appear frequently at different levels of decisions. They are usually characterized by many types of constraints, which make them unstructured and difficult to solve (NP-complete). Traditional mathematical programming approaches are deficient because their representation of constraints is artificial (using 0-1 variables). Unlike traditional approaches, constraint logic programming (CLP) provides for a natural representation of heterogeneous constraints. In CLP we state the problem requirements by constraints; we do not need to specify how to meet these requirements. In this paper we propose a declarative framework for decision support system (DSS) for scheduling problems implemented by CLP and relational SQL database. We illustrate this concept by the implementation of a DSS for scheduling problems with external resources in different production organization environments.
11
Content available remote Określenie wpływu maksymalnej wielkości zlecenia produkcyjnego na czas realizacji wszystkich zleceń
Witek T., Witkowski T.
Pomiary Automatyka Robotyka
|
2008
|
R. 12, nr 2
320--329
PL
Artykuł przedstawia zastosowanie Teorii Ograniczeń (TOC) do rozwiązania problemu harmonogramowania z technologicznie zamiennymi maszynami. Przeanalizowano wpływ maksymalnej wielkości zlecenia produkcyjnego na czas realizacji zbioru wszystkich zleceń. Przeprowadzono eksperymenty komputerowe z użyciem oprogramowania typu APP oraz opisano wyniki i wnioski.
EN
The paper presents the application of the Theory of Constraints (TOC) which was used to solve flexible job-shop scheduling problem (FJSP). The influence of maximum order quantity for production order on total production time for jobs were investigated. The computer experiments with using APP software and achieved results and conclusions have been described.
12
Content available LCS Approach to Tasks Scheduling Problem in the Two Processor System
Wasielewska K., Seredyński F.
Studia Informatica : systems and information technology
|
2007
|
Vol. 2(9)
29--39
EN
In this paper we propose an approach to solve multiprocessor scheduling problem with use of rule-based learning machine - Learning Classifier System (LCS). LCS combines reinforcement learning and evolutionary computing to produce adaptive systems. We interpret the multiprocessor scheduling problem as multi-step problem, where a feedback is given after some number steps. We show that LCS is able to solve scheduling tasks of a parallel program in the two processor system.
13
Content available remote Harmonogramowanie zadań i rozdziału zasobów jako problem spełnienia ograniczeń
Sitek P., Wikarek J., Bocewicz G.
Pomiary Automatyka Robotyka
|
2007
|
R. 11, nr 2
PL
W referacie przedstawiono możliwość formalizacji zagadnienia harmonogramowania zadań i rozdziału obciążeń w postaci problemu spełnienia ograniczeń - Constraint Satisfation Problem (CSP). Omówiono podstawowy algorytm CSP oraz techniki propagacji ograniczeń i backtrackingu. Z wykorzystaniem środowiska programowania w logice z ograniczeniami - Constraint Logic Programming (CLP), którego podstawowym zagadnieniem jest CSP, dokonano implementacji systemu wspomagania decyzji harmonogramowania produkcji. System opracowano przy wykorzystaniu pakietu ECLiPSe. W artykule zamieszczono również przykład ilustracyjny wspomagania decyzji harmonogramowania produkcji typu gniazdowego (job-shop).
EN
Scheduling problems can be seen as a special type of Constraint Satisfaction Problem (CSP). This paper presents a formulating of scheduling problems as CSPs. To solve a CSP, different approaches have been developed. These approaches generally use constraint propagation to simplify the original problem and backtracking to directly search for possible solutions. To demonstrate flexibility of CSP approach, the implementation of decision support system for job-shop production based on Constraint Logic Programming (CLP) has been presented.
14
Content available remote A two-stage scheduling problem arising from locomotive dispatching in mine railway
Lin X., Wang X.
Foundations of Computing and Decision Sciences
|
2007
|
Vol. 32, No. 2
125-137
EN
A locomotive dispatching problem arose from a coal mining area in 1950's: 2n jobs are executed by a locomotive, where n preceding jobs J,: with deadlines di (1≤ i ≤ n] represent sending empty cars to n pits from the central station, while n successive jobs Jt- with release dates r( (1≤ i ≤ n] represent drawing back the loaded cars from n pits to the station; in order to reduce the detaining and increase the turnover rate of freight cars, we are asked to find a schedule of the locomotive so that the maximum flow-time is minimized. Here, the flow-time of a job is the difference between the deadline and the starting time (for a preceding job) or between the completion time and the release date (for a successive job). The present paper studies this two-stage single machine scheduling problem. The main result is a polynomial algorithm for solving it. Meanwhile, two variant models are discussed, one is easier and one is harder. The algorithms here can be regarded as generalizations of the EDD-ERD rule.
15
Content available remote Cellular automata approach to task scheduling
Święcicka A., Seredyński F.
Studia Informatica : systems and information technology
|
2003
|
Vol. 1(1)
37--46
EN
In this paper we propose using cellular automata (CAs) to perform distributed scheduling tasks of a parallel program in the two processor system. We consider a program graph as a CA with elementaty cells interacting locally according to a certain rule which must be found. Effective rules for a CA are discovered by a genetic algorithm (GA). With these rules, CA-based scheduler is able to find allocations which minimize the total execution time of the program in the two processor system. We also show a possibility of reusing knowledge gained during solving instances of the scheduling problem. Keywords: cellular automata, genetic algorithms, scheduling problem.
16
Content available remote Szeregowanie zadań w systemie z mobilnym realizatorem
Molga M., Smutnicki C.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
173-178
PL
W pracy rozważono pewien problem kompletowania części w systemie montażowym. Zagadnienie polega na optymalizacji trasy ruchu pracownika obsługującego napełnianie pojemników. Problem został sprowadzony do specyficznego przepływowego problemu szeregowania zadań. Problem ten może być także postrzegany jako problem szeregowania jedno- (jeden pracownik) lub wielomaszynowego (wielu pracowników) z przezbrojeniami. Omówiono różne przypadki realizacji praktycznej takiego systemu. Dla wybranego zagadnienia podano model matematyczny wraz z modelem grafowym. Wykorzystując jego właściwości, zaproponowano i przebadano algorytmy optymalizacji.
EN
The paper deals with the part commission problem in an assembly system. The problem consists in optimization of movement trajectory of the worker filling the bins. The problem has been converted to special flow-shop scheduling problem. This problem can be also perceived as special single- (single worker) and multi-machine (multiple workers) scheduling problem with setup times. Several practical cases of such system have been considered. For the selected case, there has been provided mathematical model and then a graph model. Using this model, there has been proposed and tested some optimisation algorithms.
17
Content available remote Harmonogramowanie zadań jako element procesu planowania wytwarzania
Ratka I.
Napędy i Sterowanie
|
2002
|
R. 4, nr 1
62--63
PL
[Harmonogramowanie polega na takim dopasowaniu wszystkich operacji do siebie, aby nie było żadnych przestojów wynikających z konieczności oczekiwania na materiały oraz aby zostały dotrzymane terminy zamówień. Harmonogramowanie zadań roboczych jest jedną z warstw szczebla planowania wytwarzania, gdzie każde zlecenie ma podawaną datę rozpoczęcia i realizacji danego zadania. Terminy rozpoczęcia i zakończenia mają również wszystkie operacje i procesy zewnętrzne, gdyż związane to jest ściśle z terminowością dostarczenia wszystkich potrzebnych materiałów na produkcję. W wyniku przeliczania czasów potrzebnych na realizację poszczególnych operacji ustala się terminy ich rozpoczęcia i zakończenia.]
18
Content available remote Szeregowanie wiadomości metodą EDF w rozproszonych systemach sterowania z magistralą miejscową
Żaba S.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
1999
|
T. 3, z. 2
431-459
PL
W ostatnim okresie opracowano wiele analitycznych metod szeregowania i sprawdzania spełnienia warunków czasu rzeczywistego dla środowiska scentralizowanego systemów operacyjnych czasu rzeczywistego. Jednocześnie podejmowane są działania mające na celu modyfikacje tych metod, w celu zastosowania ich do badania systemów rozproszonych czasu rzeczywistego. Badania te ograniczono do szeregowania wiadomości przesyłanych poprzez sieci przemysłowe, zwane również magistralami miejscowymi (fieldbus). W pierwszej części artykułu dokonano porównania szeregowania zadań przy pomocy metod ze statycznym przydziałem priorytetów i metod z dynamicznym przydziałem priorytetów. Następnie przedyskutowano model systemu rozproszonego, dla którego został przyjęty model strumieni wiadomości. Jako metodę szeregowania wybrano metodę EDF (Earliest Deadline First). Przedstawiono dla tej metody sposoby badania spełnienia warunków czasu rzeczywistego wiadomości przesyłanych poprzez magistrale miejscowe dla dwóch przypadków: jednakowych czasów przesyłania wiadomołci i różnych czasów przesyłania wiadomości. Powyższe rozważania zobrazowane zostały przykładem obliczeniowym dla magistrali InterBus-S.
EN
Recently, analytic methods for test compliance with real time requirements have been developed for centralised real time operating systems. At the same time attempts to modify these methods have been undertaken, so as to use them to examine distributed real time systems, especially for scheduling the messages transmitted through the network, especially through the fieldbus. In the first part of the paper a comparison is made between static and dynamic techniques to schedule task in real-time system. The model of distributed computer system for control is discussed. The message scheduling basing on EDF method is discussed for two cases: equal time of message transmission and different time of message transmission. An example illustrates method for checking of RT-constraint fulfilment for InterBus-S fieldbus.
19
Content available remote Szeregowanie metodą cen dualnych
Smutnicki C.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
1999
|
T. 3, z. 1
309-318
PL
W pracy przedstawiono pewne wyniki badawcze dotyczące zastosowania tzw. podejścia dualnego do rozwiązywania jedno-maszynowego problemu szeregowania z addytywną funkcją celu. Dzięki odpowiedniemu sformułowaniu matematycznemu problemu pierwotnego oraz pewnym jego własnościom, możliwe jest także efektywne rozwiązanie problemu dualnego. Podejście to prowadzi do dwupoziomowej procedury optymalizacyjnej ze specjalizowaną dyskretną wersją metody programowania dynamicznego na dolnym poziomie oraz procedurą poszukiwania maksimum funkcji wielu zmiennych na poziomie górnym. Przedstawiono pewne własności problemów, przedyskutowano złożoność obliczeniowej odpowiednich algorytmów, zanalizowano przydatność techniki sub-gradientowej do rozwiązania problemu górnego poziomu oraz podano ilustracyjne wyniki badań numerycznych. W wyniku zastosowania proponowanej metody możemy uzyskać: (a) dolne ograniczenie wartości funkcji celu (możliwe do wykorzystania w metodzie dokładnej, np. B&B), (b) rozwiązanie optymalne (przy spełnieniu pewnych dodatkowych warunków), (c) rozwiązanie przybliżone. Otrzymane wnioski badawcze mogą być zastosowane bezpośrednio przy modelowaniu i rozwiązywaniu bardziej złożonych zagadnień szeregowania, takich jak np. problem gniazdowy z addytywną funkcją celu.
EN
In this paper there are presented some results of the dual approach used in order to solve a single-machine scheduling problem with the additive goal function. Due to proper mathematical formulation of the primal problem and some its properties, the dual problem can be solved in an efficient way. The approach leads to two-level optimisation procedure with specialised discrete version of dynamic programming method on the lower level and a procedure of seeking maximum of multiple-variable function on the upper level. Some properties of problems there are presented, computational complexities of algorithms are discussed, application of sub-gradient technique to solve the upper level problem is analysed and some illustrative numerical examples are also given. The proposed method can provide: (a) lower bound of the optimal goal function value (for the use in an exact method, e.g. B&B), (b) optimal solution (if only some auxiliary condition hold), (c) approximate solution. Obtained research results can be applied immediately in modelling and solving more complex scheduling problems, as an example the job-shop problem with additive goal function.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.