An Implementation View on Job Shop Scheduling Based on CPM

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F07%3APU69335" target="_blank" >RIV/00216305:26210/07:PU69335 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

An Implementation View on Job Shop Scheduling Based on CPM

Original language description

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 name

Implementační pohled na rozvrhování zakázkové výroby založený na metodě CPM

Czech description

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.

Type

D - Article in proceedings

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 11th WSEAS International Conference on Computers

ISBN

978-960-8457-92-8

ISSN

—

e-ISSN

—

Number of pages

6

Pages from-to

540-545

Publisher name

WSEAS Press

Place of publication

Crete Island (Greece)

Event location

Crete

Event date

Jul 26, 2007

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—