Scheduling on uniform parallel machines with periodic unavailability constraints

Jihene Kaabi and Youssef Harrath

International Journal of Production Research, 2019, vol. 57, issue 1, 216-227

Abstract: Scheduling problems under unavailability constraints has become a popular research topic in the last few years. Despite it’s important application in the real world, the uniform parallel machine scheduling problem was the least studied due to its complexity. In this paper, we investigated the uniform parallel machine scheduling problem under deterministic availability constraints. Each machine is subject to one unavailability period. Different versions of the problem regarding the type of jobs (identical and non-identical) and the performance measures (the total completion times and the makespan) were studied. For the case of identical jobs and for both performance measures, we developed linear programming models and optimal algorithms to provide a solution to the problem. For the case of non-identical jobs, we proved that the problem is NP-hard and propose a quadratic program. Because, this later cannot solve problems with very large number of jobs and machines, a heuristic was developed to find near optimal solutions to the problem especially with very large number of jobs and machines. The computational results showed that the heuristic’s performance is very high regardless the dimensions of problem instances.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2018.1471242 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:57:y:2019:i:1:p:216-227

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2018.1471242

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().