Publication detail
An Implementation View on Job Shop Scheduling Based on CPM
ŠEDA, M.
Czech title
Implementační pohled na rozvrhování zakázkové výroby založený na metodě CPM
English title
An Implementation View on Job Shop Scheduling Based on CPM
Type
conference paper
Language
en
Original abstract
The scheduling of manufacturing processes aims to find sequences of jobs on given machines optimal by a selected criterion, e.g. minimal completion time of all operations. With respect to NP-hardness of these problems and the necessity to solve them by heuristic methods, the problem representation and the effectiveness of their procedures is substantial for computations to be completed in a reasonable amount of time. In this paper, we deal with job shop scheduling problem (JSSP) in a disjunctive graph-based representation. Turning all undirected edges into directed ones, the problem is transformed to a problem solvable by the Critical Path Method (CPM). We propose an original implementation of the CPM that makes it possible to decrease its time complexity and thus also the running time of all JSSP iterations.
Czech abstract
V rozvrhování výrobních procesů je cílem nalezení optimálního pořadí úloh tvořených skupinou operací na jednotlivých výrobních zařízeních (strojích) vzhledem k zvolenému kritériu optimality. Vzhledem k tomu, že tyto problémy jsou NP-těžké a nutnosti řešit je heuristickými metodami, je reprezentace problému a efektivita jeho procedur je podstatná pro dokončení výpočtu v rozumném čase. V tomto příspěvku se zabýváme rozvrhováním zakázkové (nebo také kusové) výroby a jeho reprezentací disjunktivním grafem. Jestliže zvolíme orientaci pro neorientované hrany, pak problém se transformuje na problém řešitelný metodou kritické cesty. Navrhujeme originální implementaci této metody, která umožňuje snížit její časovou složitost a tím čas výpočtu všech iterací výpočtu rozvrhu zakázkové výroby.
English abstract
The scheduling of manufacturing processes aims to find sequences of jobs on given machines optimal by a selected criterion, e.g. minimal completion time of all operations. With respect to NP-hardness of these problems and the necessity to solve them by heuristic methods, the problem representation and the effectiveness of their procedures is substantial for computations to be completed in a reasonable amount of time. In this paper, we deal with job shop scheduling problem (JSSP) in a disjunctive graph-based representation. Turning all undirected edges into directed ones, the problem is transformed to a problem solvable by the Critical Path Method (CPM). We propose an original implementation of the CPM that makes it possible to decrease its time complexity and thus also the running time of all JSSP iterations.
Keywords in Czech
výrobní proces, rozvrhování zakázkové výroby, NP-těžký problém, disjunktivní graf, CPM
Keywords in English
manufacturing process, job shop scheduling, NP-hard problem, disjunctive graph, CPM
RIV year
2007
Released
01.07.2007
Publisher
WSEAS Press
Location
Crete Island (Greece)
ISBN
978-960-8457-92-8
Book
Proceedings of the 11th WSEAS International Conference on Computers
Pages from–to
540–545
Pages count
6
BIBTEX
@inproceedings{BUT23385,
author="Miloš {Šeda},
title="An Implementation View on Job Shop Scheduling Based on CPM",
booktitle="Proceedings of the 11th WSEAS International Conference on Computers",
year="2007",
month="July",
pages="540--545",
publisher="WSEAS Press",
address="Crete Island (Greece)",
isbn="978-960-8457-92-8"
}