ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
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
    Series parallel composition of greedy linear programming problems (1993)
    Springer
    Mathematical programming 62 (1993), S. 1-14 
    Details
    ISSN: 1436-4646
    Keywords: Greedy algorithm ; Monge arrays ; series parallel graphs ; linear programming ; network flow ; transportation problem ; integrality ; convexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the concept of series and parallel composition of linear programming problems and show that greedy properties are inherited by such compositions. Our results are inspired by earlier work on compositions of flow problems. We make use of certain Monge properties as well as convexity properties which support the greedy method in other contexts.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585157
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Dualität zwischen Kategorien topologischer Räume und Kategorien von K-Verbänden (1972)
    Springer
    Monatshefte für Mathematik 76 (1972), S. 385-397 
    Details
    ISSN: 1436-5081
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01297302
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Tabu-search for the multi-mode job-shop problem (1998)
    Springer
    OR spectrum 20 (1998), S. 21-28 
    Details
    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
    URL: http://dx.doi.org/10.1007/s002910050048
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A branch & bound method for the general-shop problem with sequence dependent setup-times (1996)
    Springer
    OR spectrum 18 (1996), S. 145-161 
    Details
    ISSN: 1436-6304
    Keywords: General-shop problem ; sequence dependent setup-times ; branch & bound method ; block approach ; immediate selection ; job-shop ; open-shop ; disjunctive graph model ; Allgemeine Shop-Probleme ; reihenfolgeabhängige Rüstzeiten ; Branch- und Bound-Verfahren ; Blockansatz ; Immediate-Selection ; Jop-Shop ; Open-Shop ; disjunktiver Graph
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Es wird ein Branch & Bound-Algorithmus für ein sehr allgemeines Scheduling Problem mitn Jobs undm Maschinen vorgestellt. Jeder Job besteht aus einer Menge von Operationen, die auf einer ausgewählten Maschine bearbeitet werden müssen. Zwischen den Operationen sind beliebige Vorrangbeziehungen möglich. Ferner werden die Operationen in Gruppen aufgeteilt. Wenn auf einer Maschine eine Operation der GruppeG g unmittelbar nach einer Operation der GruppeG f bearbeitet wird, ist eine Rüstzeit vons fg Zeiteinheiten notwendig. Wir setzen voraus, daßs fg=0 fürf=g und daß dies fg die Dreiecksungleichung erfüllen. Sowohl für dieses allgemeine Problem als auch für Spezialfälle wie das Job-Shop Problem und das Open-Shop Problem werden Rechenergebnisse vorgestellt.
    Notes: Abstract A branch & bound algorithm is presented for a very general scheduling problem withn jobs andm machines. Each job consists of a set of operations. Each operation has to be processed on a dedicated machine. There may be arbitrary precedence relations between the operations. The set of all operations is partitioned into groups. If on a machine an operation belonging to groupG g is processed immediately after an operation belonging to groupG f there is a setup ofs fg time units. We assume thats fg=0 iff=g and that thes fg satisfy the triangle inequality. Computational results for this general problem as well as for special cases like the job-shop problem and the open-shop problem are reported.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01539706
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    On the complexity of two machine job-shop scheduling with regular objective functions (1997)
    Springer
    OR spectrum 19 (1997), S. 5-10 
    Details
    ISSN: 1436-6304
    Keywords: Job-shop ; polynomial algorithm ; Job-Shop ; polynomialer Algorithmus
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Für das Zweimaschinen-Job-Shop-Problem ohne Arbeitsunterbrechnungen und den Zielfunktionen Σf i bzw. maxf i , wobei dief i monotone Funktionen der Fertigstellungszeiten der Jobsi sind, werden für den Fall fester Jobanzahlen polynomiale Algorithmen angegeben. Dies beantwortet insbesondere die bislang offene Frage nach dem Komplexitätsstatus des obigen Problems für die ZielfunktionenL max, Σw i U i , und Σw i U. Schließlich zeigen wir, daß das Problem mit beliebiger regulärer Zielfunktion ebenfalls polynomial lösbar ist.
    Notes: Abstract For the nonpreemptive two machine job-shop scheduling problem with a fixed number of jobs and objective functions Σf i and maxf i , wheref i are nondecreasing functions of the finish times of jobsi, polynomial algorithms are presented. This answers previous open questions about the complexity status of the corresponding problems with objective functionsL max, Σw i U i , and Σw i U. We generalize these results by showing that the problem with any regular criterion can be solved in polynomial time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01539799
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    On the complexity of two machine job-shop scheduling with regular objective functions (1997)
    Springer
    OR spectrum 19 (1997), S. 5-10 
    Details
    ISSN: 1436-6304
    Keywords: Key words: Job-shop ; polynomial algorithm ; Schlüsselwörter: Job-Shop ; polynomialer Algorithmus
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung. Für das Zweimaschinen-Job-Shop-Problem ohne Arbeitsunterbrechnungen und den Zielfunktionen Σf i bzw. max f i , wobei die f i monotone Funktionen der Fertigstellungszeiten der Jobs i sind, werden für den Fall fester Jobanzahlen polynomiale Algorithmen angegeben. Dies beantwortet insbesondere die bislang offene Frage nach dem Komplexitätsstatus des obigen Problems für die Zielfunktionen L max, Σw i U i , und Σw i T i . Schließlich zeigen wir, daß das Problem mit beliebiger regulärer Zielfunktion ebenfalls polynomial lösbar ist.
    Notes: Abstract. For the nonpreemptive two machine job-shop scheduling problem with a fixed number of jobs and objective functions Σf i and max f i , where f i are nondecreasing functions of the finish times of jobs i, polynomial algorithms are presented. This answers previous open questions about the complexity status of the corresponding problems with objective functions L max, Σw i U i , and Σw i T i . We generalize these results by showing that the problem with any regular criterion can be solved in polynomial time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01539799
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    The job-shop problem and immediate selection (1994)
    Springer
    Annals of operations research 50 (1994), S. 73-114 
    Details
    ISSN: 1572-9338
    Keywords: Job-shop scheduling ; immediate selection ; disjunctive graph model
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The job-shop problem is one of the most difficult NP-hard scheduling problems. A 10×10-problem published in 1963 has been solved only recently by Carlier and Pinson using a branch and bound method. Other branch and bound algorithms have been developed recently. The efficiency of all these branch and bound methods relies on the concept of immediate selection which allows to introduce order relations on the setI of all operations to be processed on the same machine before branching. We present new algorithms for immediate selection. Among them are • anO(max {n logn,f})-algorithm for fixing all disjunctions induced by cliques; • anO(n 2)-algorithm based on concepts which are different from those used by Carlier and Pinson. Here,n is the number of operations inI andf is the number of induced order relations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02085636
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Shop scheduling problems with multiprocessor tasks on dedicated processors (1995)
    Springer
    Annals of operations research 57 (1995), S. 13-27 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The computational complexity of shop scheduling problems with multiprocessor tasks on dedicated processors is investigated. The objective is makespan minimization. Preemption of tasks is not allowed. For open and flow-shop problems with three stages, complete classifications into polynomial solvable and NP-hard problems are given. These classifications depend on the compatibility structures of the problems. Furthermore, results for open-shop problems with unit processing times are derived. Finally, it is shown that most of the special cases of the job-shop problem which are polynomially solvable remain polynomially solvable in the multiprocessor task situation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02099688
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Batch scheduling with deadlines on parallel machines (1998)
    Springer
    Annals of operations research 83 (1998), S. 23-40 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The problem of scheduling G groups of jobs on m parallel machines is considered. Each group consists of several identical jobs. We have to find splittings of groups into batches (i.e. sets of jobs to be processed contiguously) and to schedule the batches on the machines. It is possible for different batches of the same group to be processed concurrently on different machines. However, at any time, a batch can be processed on at most one machine. A sequence-independent machine set-up time is required immediately before a batch of a group is processed. A deadline is associated with each group. The objective is to find a schedule which is feasible with respect to deadlines. The problem is shown to be NP-hard even for the case of two identical machines, unit processing times, unit set-up times and a common deadline. It is strongly NP-hard if machines are uniform, the number of jobs in each group is equal and processing times, set-up times and deadlines are unit. Special cases which are polynomially solvable are discussed. For the general problem, a family {DPɛ} of approximation algorithms is constructed. A new dynamic rounding technique is used to develop DP ɛ. For any ɛ 〉 0, DP ɛ delivers a schedule in which the completion time of each group is at most (1 + ɛ) times the value of its deadline if there exists a schedule which is feasible with respect to the deadlines. The time complexity of DP ɛ is O(G 2m+1/ɛ2m).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1018912114491
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Complexity of scheduling problems with multi-purpose machines (1997)
    Springer
    Annals of operations research 70 (1997), S. 57-73 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In a multi-purpose machine scheduling problem, jobs or operations can be processed by any machine of prespecified subsets of the machine set. In this paper, we study the computational complexity of such scheduling problems. We study scheduling problems with identical and uniform machines as well as problems with shop characteristics.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1018950911030
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...