Detail publikace

An Implementation View on Job Shop Scheduling Based on CPM

ŠEDA, M.

Originální název

An Implementation View on Job Shop Scheduling Based on CPM

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

manufacturing process, job shop scheduling, NP-hard problem, disjunctive graph, CPM

Autoři

ŠEDA, M.

Rok RIV

2007

Vydáno

1. 7. 2007

Nakladatel

WSEAS Press

Místo

Crete Island (Greece)

ISBN

978-960-8457-92-8

Kniha

Proceedings of the 11th WSEAS International Conference on Computers

Strany od

540

Strany do

545

Strany počet

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",
  pages="540--545",
  publisher="WSEAS Press",
  address="Crete Island (Greece)",
  isbn="978-960-8457-92-8"
}