A Permutation-Based Neighborhood for the Blocking Job-Shop Problem with Total Tardiness Minimization

Julia Lange () and Frank Werner ()
Additional contact information
Julia Lange: Otto-von-Guericke-Universität Magdeburg
Frank Werner: Otto-von-Guericke-Universität Magdeburg

A chapter in Operations Research Proceedings 2017, 2018, pp 581-586 from Springer

Abstract: Abstract The consideration of blocking constraints refers to the absence of buffers in a production system. A job-shop scheduling problem with a total tardiness objective is NP-hard even without blocking constraints and mathematical programming results indicate the necessity of heuristics. The neighborhood is one of its main components. In contrast to classical job-shop scheduling, a permutation of operations does not necessarily define a feasible schedule. A neighbor is determined by an adjacent pairwise interchange (API) of two operations on a machine and the resulting permutation of operations is modified to regain feasibility while maintaining the given API. The neighborhood is implemented in a simulated annealing and tested on train-scheduling-inspired problems as well as benchmark instances. The heuristic method obtains optimal and near-optimal solutions for small instances and outperforms a given MIP formulation for some of the larger ones.

Keywords: Job-shop scheduling; Blocking; Simulated annealing (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-89920-6_77

Ordering information: This item can be ordered from
http://www.springer.com/9783319899206

DOI: 10.1007/978-3-319-89920-6_77

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().