<oai_dc:dc xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd">
  <dc:creator>Bürgy, Reinhard</dc:creator>
  <dc:creator>Gröflin, Heinz</dc:creator>
  <dc:date>2013</dc:date>
  <dc:description xmlns:ns0="xml" ns0:lang="en">The no-wait job shop (NWJS) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is given. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The NWJS problem consists in finding a schedule that minimizes the makespan. We address here the so-called optimal job insertion problem (OJI) in the NWJS. While the OJI is NP-hard in the classical job shop, it was shown by Gröflin &amp; Klinkert to be solvable in polynomial time in the NWJS. We present a highly efficient algorithm with running time $\mathcal {O}(n^{2}\cdot\max\{n,m\})$ for this problem. The algorithm is based on a compact formulation of the NWJS problem and a characterization of all feasible insertions as the stable sets (of prescribed cardinality) in a derived comparability graph. As an application of our algorithm, we propose a heuristic for the NWJS problem based on optimal job insertion and present numerical results that compare favorably with current benchmarks</dc:description>
  <dc:format>application/pdf</dc:format>
  <dc:identifier>https://sonar.ch/global/documents/306766</dc:identifier>
  <dc:language>eng</dc:language>
  <dc:relation>info:eu-repo/semantics/altIdentifier/doi/10.1007/s10878-012-9466-y</dc:relation>
  <dc:rights>info:eu-repo/semantics/openAccess</dc:rights>
  <dc:rights>License undefined, Springer Science+Business Media, LLC, 2012</dc:rights>
  <dc:source>Journal of Combinatorial Optimization. - Springer US; http://www.springer-ny.com. - 2013, vol. 26, no. 2, p. 345-371</dc:source>
  <dc:subject>info:eu-repo/classification/udc/004</dc:subject>
  <dc:title xmlns:ns1="xml" ns1:lang="en">Optimal job insertion in the no-wait job shop</dc:title>
  <dc:type>http://purl.org/coar/resource_type/c_6501</dc:type>
</oai_dc:dc>
