The representation of partially-concurrent open shop problems

Tal Grinshpoun (), Hagai Ilani () and Elad Shufan ()
Additional contact information
Tal Grinshpoun: Ariel University
Hagai Ilani: SCE – Shamoon College of Engineering
Elad Shufan: SCE – Shamoon College of Engineering

Annals of Operations Research, 2017, vol. 252, issue 2, No 12, 455-469

Abstract: Abstract The partially-concurrent open shop scheduling problem is introduced. The standard open shop scheduling problem is generalized by allowing some operations to be processed concurrently. A schedule for the partially-concurrent problem is represented by a digraph. We show that the scheduling problem is equivalent to a problem of orienting a given undirected graph, called a conflict graph. The schedule digraph is then modeled by a matrix, generalizing the rank matrix representation. The problem is shown to be NP-hard. The representation can be used to generalize previously discussed standard open shop issues. It is demonstrated by generalizing the theoretical concept of reducibility and also by using standard open shop heuristic solutions to the partially-concurrent scenario. The presented problem is directly motivated from a real-life timetabling project of assigning technicians to airplanes in an airplane garage.

Keywords: Open shop scheduling; Concurrent machines; Technician timetabling; Matrix representation; Graph orientation; Reducibility (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-015-1934-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:annopr:v:252:y:2017:i:2:d:10.1007_s10479-015-1934-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-1934-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

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