Gröflin, Heinz Bürgy, Reinhard 2015-07-01 The no-wait job shop problem (NWJS-R) 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 prescribed. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The problem consists in finding a schedule that minimizes a general regular objective function. We study the so-called optimal job insertion problem in the NWJS-R and prove that this problem is solvable in polynomial time by a very efficient algorithm, generalizing a result we obtained in the case of a makespan objective. We then propose a large neighborhood local search method for the NWJS-R based on the optimal job insertion algorithm and present extensive numerical results that compare favorably with current benchmarks when available. application/pdf https://folia.unifr.ch/global/documents/304920 https://folia.unifr.ch/documents/304920/files/IWP15_02_diuf.pdf eng info:eu-repo/semantics/openAccess License undefined info:eu-repo/classification/udc/004 The no-wait job shop with regular objective : a method based on optimal job insertion http://purl.org/coar/resource_type/c_18ws