## THE COMPLEXITY OF ONE-MACHINE BATCHING PROBLEMS

Autor(en): | ALBERS, S BRUCKER, P |

Stichwörter: | BATCHING; Mathematics; Mathematics, Applied; NP-HARD; POLYNOMIAL ALGORITHM; SHORTEST PATH PROBLEM; SINGLE |

Erscheinungsdatum: | 1993 |

Herausgeber: | ELSEVIER SCIENCE BV |

Journal: | DISCRETE APPLIED MATHEMATICS |

Volumen: | 47 |

Ausgabe: | 2 |

Startseite: | 87 |

Seitenende: | 107 |

Zusammenfassung: | Batching problems are combinations of sequencing and partitioning problems. For each job sequence JS there is a partition of JS into batches with optimal value opt(JS) and one has to find a job sequence which minimizes this optimal value. We show that in many situations opt(JS) is the solution of a shortest path problem in some network. An algorithm solving this special shortest path problem in linear time with respect to the number of vertices is presented. Using this algorithm some new batching results are derived. Furthermore. it is shown that most of the batching problems which are known to be polynomially solvable turn into NP-hard problems when modified slightly. |

Beschreibung: | NATO Advanced Study Institute on New Frontiers in the Theory and Practice of Combinatorial Optimization: Applications in Manufacturing and VLSI Design, BILKENT UNIV ANKARA, ANKARA, TURKEY, JUL 16-28, 1990 |

ISSN: | 0166218X |

DOI: | 10.1016/0166-218X(93)90085-3 |

Show full item record