Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
  • 1
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Für eine große Anzahl von diskreten Optimierungsproblemen wie das Traveling Salesman Problem, das quadratische Zuordnungsproblem, das allgemeine Flowshop Problem, das Rucksackproblem usw. haben alle bisherigen Lösungsansätze die unangenehme Eigenschaft, daß der Rechenumfang der entsprechenden Algorithmen exponentiell mit dem Umfang der Probleme wächst. Alle Bemühungen polynomial beschränkte Verfahren für solche Probleme zu finden waren bislang ergebnislos. Neuere Ergebnisse der Komplexitätstheorie besagen, daß diese Probleme zu den Klassen derNP-vollständigen bzw.NP-schwierigen Probleme gehören und somit nach allgemein verbreiteter Auffassung wohl niemals polynomial lösbar sein werden. Die Anwendung von heuristischen Verfahren oder approximativen Algorithmen scheint der einzige Ausweg in dieser Situation. Ziel der Arbeit ist es, einen einführenden Uberblick über die Theorie derNP-vollständigen undNP-schwierigen Probleme sowie über approximative Verfahren zu geben. Alle in der Arbeit einge-führten Begriffe werden an einfach verständlichen Beispielen erläutert, die eng mit dem Rucksack-problem verwandt sind. Für weitere Probleme, die den Unternehmensforscher interessieren, findet der Leser ausführliche Literaturübersichten.
    Notes: Abstract For a large number of discrete optimization problems like the traveling salesman problem, the quadratic assignment problem, the general flow-shop problem, the knapsack problem etc. all known algorithms have the discouraging property that their (worst-case) running times on a computer grow exponentially with the size of the problem. All efforts to find polynomial bounded algorithms for these problems have failed. Recent results in complexity theory show that these problems belong to the classes ofNP-complete orNP-hard problems. It is a common belief that for problems belonging to these classes no polynomial bounded algorithms exist. Heuristics or approximation algorithms should be applied to these problems. The aim of this tutorial paper is to give a survey onNP-complete andNP-hard problems and on approximation algorithms. All concepts introduced are illustrated by examples which are closely related to the knapsack problem and can be understood easily. References to most other problems of interest to operations researchers are given.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 2
    ISSN: 1432-5217
    Keywords: Key words: Job-shop problem ; scheduling ; NP-hard
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract. It is shown that the two machine preemptive job-shop problem with mean flow-time or makespan objective function and three jobs is NP-hard. This contrasts the fact that the nonpreemptive versions of these problems are polynomially solvable if the number of jobs is arbitrary but fixed. It is also shown that the preemptive problems can be solved pseudopolynomially if both the number of machines and the number of jobs is fixed.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 3
    ISSN: 1432-5217
    Keywords: single machine batch scheduling ; weighted number of late jobs ; fully polynomial approximation scheme
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The single machine batch scheduling problem to minimize the weighted number of late jobs is studied. In this problem,n jobs have to be processed on a single machine. Each job has a processing time, a due date and a weight. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of this batch is processed. The completion time of each job in the batch coincides with the completion time of the last job in this batch. A job is late if it is completed after its due date. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find a schedule which minimizes the weighted number of late jobs. This problem isNP-hard even if all due dates are equal. For the general case, we present a dynamic programming algorithm which solves the problem with equal weights inO(n 3) time. We formulate a certain scaled problem and show that our dynamic programming algorithm applied to this scaled problem provides a fully polynomial approximation scheme for the original problem. Each algorithm of this scheme has a time requirement ofO(n 3/ɛ +n 3 logn). A side result is anO(n logn) algorithm for the problem of minimizing the maximum weight of late jobs.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 4
    ISSN: 1432-5217
    Keywords: Key words: scheduling, unit execution time tasks, concurrency, identical parallel processors, complexity, approximation algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract. Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 5
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 6
    ISSN: 1432-5217
    Keywords: Open shop scheduling ; parallel machine scheduling ; polynomial algorithm ; NP-hard problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We show that them-machine open shop problem in which all operations have unit processing times can be polynomially transformed to a special preemptive scheduling problem onm identical parallel machines. Many results published recently as well as some new results are derived by using this transformation. The new results include solutions of open problems mentioned in a recent paper by Kubiak et al. p]A similar relationship is derived between no-wait open shop problems with unit time operations andm-machine problems with jobs having unit processing times.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 7
    ISSN: 1432-5217
    Keywords: Key words: Scheduling ; uniform machines ; identical jobs ; chain precedence constraints
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract. The problem of scheduling identical jobs with chain precedence constraints on two uniform machines is considered. It is shown that the corresponding makespan problem can be solved in linear time.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 8
    ISSN: 1436-6304
    Keywords: Two machine job-shop ; polynomial algorithm ; Zwei-Maschinen-Flow-Shop ; polynomialer Algorithmus
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Es wird gezeigt, daß das Job-Shop ProblemJ2¦n=k¦C max bei fester Anzahl von Jobs polynomial lösbar ist. Da das ProblemJ3¦n=3¦C max NP-schwierig ist (Sotskov und Shakhlevich 1993) und sichJ¦n=2¦C max ebenfalls polynomial lösen läßt, erhält man durch dieses Ergebnis eine vollständige Antwort auf die Frage nach der Komplexität von Job-Shop Problemen mit fester Anzahl von Maschinen und Jobs.
    Notes: Abstract It is shown that the job-shop problem with two machines and a fixed number ofk jobs with makespan criterionJ2¦n=k¦C max is polynomially solvable. Sotskov and Shakhlevich (1993) have shown that problemJ3¦n=3¦C maxisNP-hard. Furthermore it is well known that J¦n=2¦C maxin polynomially solvable. Thus, our result settles the remaining open question concerning the complexity status of job-shop problems with fixed numbers of jobs and machines.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 9
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 20 (1998), S. 21-28 
    ISSN: 1436-6304
    Keywords: Tabu-search ; multi-mode job-shop ; multiprocessor-task job-shop ; multi-purpose-machine job-shop ; Tabu-Suche ; Mehrmodus-Job-Shop ; Mehrprozessoroperationen-Job-Shop ; Mehrzweckmaschinen-Job-Shop
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In einem Multi-Processor-Task Job-Shop Problem (MPTJSP) wird jeder Operation eine Maschinenmenge zugeordnet. Für die Bearbeitung einer Operation werden dabei während des gesamten Bearbeitungszeitraums alle Maschinen benötigt. Ziel ist es nun, einen Bearbeitungsplan zu bestimmen, in dem die Gesamtbearbeitungsdauer minimal ist. In einem Multi-Mode Job-Shop Problem (MMJSP) wird jeder Operation eine Menge von Maschinenmengen zugeordnet. Hierbei muß jeder Operation eine Maschinenmenge zugewiesen werden und das sich daraus ergebene MPTJSP mit dem Ziel der Minimierung der Gesamtbearbeitungsdauer gelöst werden. Für das MMJSP wird ein Tabu-Suche Algorithmus vorgestellt. Außerdem werden die erhaltenen Rechenergebnisse aufgeführt.
    Notes: Abstract In a multi-processor-tasks job-shop problem (MPTJSP) there is a machine set associated with each operation. All machines are needed for the whole processing period to process the operation. The objective is to find a schedule which minimizes the makespan. In a multi-mode job-shop problem (MMJSP) there is a set of machine sets associated with each operation. One has to assign a machine set to each operation and to solve the resulting MPTJSP such that the resulting makespan is minimized. For the MMJSP a tabu-search algorithm is presented. Computational results are reported.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 20 (1998), S. 21-28 
    ISSN: 1436-6304
    Keywords: Key words:Tabu-search, multi-mode job-shop, multi-processor-task job-shop, multi-purpose-machine job-shop ; Schlüsselwörter: Tabu-Suche, Mehrmodus-Job-Shop, Mehrprozessoroperationen-Job-Shop, Mehrzweckmaschinen-Job-Shop
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung. In einem Multi-Processor-Task Job- Shop Problem (MPTJSP) wird jeder Operation eine Maschinenmenge zugeordnet. Für die Bearbeitung einer Operation werden dabei während des gesamten Bearbeitungszeitraums alle Maschinen benötigt. Ziel ist es nun, einen Bearbeitungsplan zu bestimmen, in dem die Gesamtbearbeitungsdauer minimal ist. In einem Multi-Mode Job-Shop Problem (MMJSP) wird jeder Operation eine Menge von Maschinenmengen zugeordnet. Hierbei muß jeder Operation eine Maschinenmenge zugewiesen werden und das sich daraus ergebene MPTJSP mit dem Ziel der Minimierung der Gesamtbearbeitungsdauer gelöst werden. Für das MMJSP wird ein Tabu-Suche Algorithmus vorgestellt. Außerdem werden die erhaltenen Rechenergebnisse aufgeführt.
    Notes: Abstract. In a multi-processor-tasks job-shop problem (MPTJSP) there is a machine set associated with each operation. All machines are needed for the whole processing period to process the operation. The objective is to find a schedule which minimizes the makespan. In a multi-mode job-shop problem (MMJSP) there is a set of machine sets associated with each operation. One has to assign a machine set to each operation and to solve the resulting MPTJSP such that the resulting makespan is minimized. For the MMJSP a tabu-search algorithm is presented. Computational results are reported.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...