Library

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Mathematische Annalen 187 (1970), S. 77-84 
    ISSN: 1432-1807
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Computing 27 (1981), S. 367-370 
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Es wird einO (nlogn)-Algorithmus beschrieben, der das Zweimaschinen-, Job-Shop-Scheduling-Problem mit insgesamtn Teiltätigkeiten für den Fall löst, daß man die maximale Verspätung zu minimieren hat. Der Algorithmus ist eine wesentliche Verallgemeinerung eines Ergebnisses von Hefetz und Adiri, die das gleiche Problem in Verbindung mit der einfachen Zielfunktion „Projektdauer” gelöst haben.
    Notes: Abstract AnO (nlogn)-algorithm is given for the two-machine, job-shop scheduling problem withn unit-time tasks in which maximum lateness is to be minimized. This algorithm generalizes recent results by Hefetz and Adiri for the corresponding makespan problem.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Computing 42 (1989), S. 309-313 
    ISSN: 1436-5057
    Keywords: 90C05 ; 90C35 ; Linear programming ; network flows ; tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Kern [1986] entwicklete einenO(nm+n logn)-Algorithmus zur Lösung von linearen Programmen der Form max{cx/l≤Ax≤b, L≤x≤U}, wobeil, b, L, U nichtnegativ sind undA eine 0-1-Matrix der Dimensionm x n mit der Eigenschaft, daß der Träger jeder Zeile vonA im Träger jeder der nachfolgenden Zeilen enthalten ist, darstellt. Wir zeigen, daß eine allgemeinere Klasse von linearen Programmen sich mit einem Aufwand vonO (n logn), lösen läßt.
    Notes: Abstract AnO(nm+nlogn)-algorithm was developed by Kern, [1986] to solve linear programs of the form max{cx/l≤Ax≤b, L≤x≤U} wherel, b, L, U are nonnegative andA is a 0-1-matrix of dimensionm x n with the property that the support of each row is contained in the support of every subsequent row. We will show that a more general class of linear programs can be solved inO(n logn)-time.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Computing 52 (1994), S. 97-122 
    ISSN: 1436-5057
    Keywords: 90B35 ; Interval scheduling ; circular are graph ; k-coloring ; longest path problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Dask-Track Zuordnungsproblem ist ein Schedulingproblem mitn Jobs undk Maschinen. Jede Maschine hat dabei eine bestimmte Prozeßzeit [a j ,b j [, genanntTrack. Jeder Jobi hat einen spezifischen Startzeitpunkts i und einen spezifischen Beendigungszeitpunktt i . Ein Plan ist eine Zuordnung von gewissen Jobs zu den Maschinen derart, daß die derselben Maschinej zugeordneten Zeitintervalle [s i ,t i [ nich überlappen und innerhalb des Tracks [a j ,b j [ liegen. Gesucht ist ein Plan, der die Zahl der zugeordneten Jobs maximiert. Zur Lösung dieses Problems wird einO(n k−1 k!k k+1 )-Algorithmus vorgestellt. Außerdem wird gezeigt, daß das allgemeinere Problem, in dem in jedem Track nur eine gegebene Teilmenge von Jobs einplanbar ist, mit einem Aufwand vonO(n k k!k k ) gelöst werden kann.
    Notes: Abstract Thek-track assignment problem is a scheduling problem withn jobs andk machines. Each machinej has a certain operational period (track) which starts at timea j and ends at timeb j . Each jobi has a specific start times i and a specific finish timet i . A schedule is an assignment of certain jobs to machines such that the intervals [s i ,t i [assigned to the same machinej do not overlap and fit into track [a j ,b j [. We are interested in a schedule which maximizes the number of assigned jobs. AO(n k−1 k!k k+1 )-algorithm which solves this problem is presented. Furthermore it is shown that the more general problem, in which for each track only a given set of jobs can be scheduled on that track, can be solved inO(n k k!k k )-time.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Computing 63 (1999), S. 299-316 
    ISSN: 1436-5057
    Keywords: AMS Subject Classifications:90B35. ; Key words.Complexity results, time-lags, single machine, flow-shop problem.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract. In a single-machine problem with time-lags a set of jobs has to be processed on a single machine in such a way that certain timing restrictions between the finishing and starting times of the jobs are satisfied and a given objective function is minimized. We consider the case of positive finish-start time-lags $l_{ij}$ which mean that between the finishing time of job i and the starting time of job j the minimal distance $l_{ij}$ has to be respected. New complexity results are derived for single-machine problems with constant positive time-lags $l_{ij}=l$ which also lead to new results for flow-shop problems with unit processing times and job precedences.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Computing 40 (1988), S. 353-359 
    ISSN: 1436-5057
    Keywords: 90B35 ; Job-shop scheduling ; shortest path
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Es ist bekannt, daß sich Job-Shop-Scheduling-Probleme mit zwei Jobs als kürzeste Wege-Probleme mit Hindernissen darstellen lassen. Gezeigt wird, daß sich ein solches Problem mit einem Aufwand vonO (n logn) auf ein normales kürzestes Wege-ProblemP reduzieren läßt, wennn die Anzahl der Hindernisse ist.P läßt sich überdies mit einem Aufwand vonO (n) lösen.
    Notes: Abstract It is well known that job-shop scheduling problems with two jobs can be formulated as shortest path problems with obstacles in the plane. A reduction of this problem to an unrestricted shortest path problem in a special networkN is constructed inO (n logn) steps wheren is the number of obstacles. The shortest path inN can be found in timeO (n).
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Computing 45 (1990), S. 369-375 
    ISSN: 1436-5057
    Keywords: 90 B 35 ; Job-Shop scheduling ; flexible manufacturing ; shortest path
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Folgende Verallgemeinerung des klassischen Job-Shop Scheduling Problems wird untersucht. Jeder Operation eines Jobs sei eine Menge von Maschinen zugeordnet. Wählt man für jede Operation genau eine Maschine aus dieser Menge aus, so erhält man ein klassisches Job-Shop Problem, dessen minimale Gesamtbearbeitungszeitf(μ) von dieser Zuordnung μ abhängt. Gesucht ist eine Zuordnung μ, dief(μ) minimiert. Für zwei Jobs wird ein polynomialer Algorithmus entwickelt, der dieses Problem löst.
    Notes: Abstract Consider the following generalization of the classical job-shop scheduling problem in which a set of machines is associated with each operation of a job. The operation can be processed on any of the machines in this set. For each assignment μ of operations to machines letP(μ) be the corresponding job-shop problem andf(μ) be the minimum makespan ofP(μ). How to find an assignment which minimizesf(μ)? For problems with two jobs a polynomial algorithm is derived.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    Computing 10 (1972), S. 271-283 
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Abstract Floyd developed a matrix algorithm to find all shortest paths in a network. If we modify the algebraic structure of the network the same algorithm can be applied to large number of other problems. A general theory for these algorithms is developed and applied to numerous problems.
    Notes: Zusammenfassung Floyd entwickelte einen Matrixalgorithmus zur Bestimmung der Längen aller kürzesten Wege in einem Netzwerk. In der vorliegenden Arbeit wird gezeigt, daß, falls man den Begriff des Netzwerkes etwas verallgemeinert, sich mit Hilfe des gleichen Verfahrens eine Fülle von grundverschiedenen Problemen lösen läßt. Es wird eine entsprechende Theorie entwickelt und an Beispielen erläutert.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 9
    Electronic Resource
    Electronic Resource
    Springer
    Computing 38 (1987), S. 341-345 
    ISSN: 1436-5057
    Keywords: Approximation ; n-dimensional grid
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Es wird ein Verfahren zur Bestimmung einer Translation eines rechtwinkeligen Gitters mit der Eigenschaft, daß eine endliche Punktmenge des ℝN möglichst gut durch Gitterpunkte approximiert wird, angegeben.
    Notes: Abstract A procedure is given for translating a rectangular grid in such a way that a finite set of points in ℝN is approximated as good as possible by points of the translated grid.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical methods of operations research 28 (1984), S. 29-40 
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Es wird einO (n+r logn)-Algorithmus vorgestellt, der LP-Rucksackprobleme mitn Variablen undr verallgemeinerten oberen Schranken für die Variablen löst. Grundlage des Verfahrens ist ein parametrischer Ansatz kombiniert mit bekannten Methoden zur Konstruktion von Algorithmen mit linearer Laufzeit. Der vorgestellte Algorithmus verbessertO (n logn)-Verfahren vonGlover/Klingman [1979] undZemel [1980].
    Notes: Abstract AnO (n+r logn) algorithm is presented for the linear programming knapsack problem withr generalized upper bounds andn variables. This result which is based on parametric programming and well-known ideas for the design of linear-time algorithms improvesO (n logn) algorithms given byGlover/Klingman [1979] andZemel [1980].
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...