Premium
Optimality of Jackson's permutations with respect to limited machine availability
Author(s) -
Braun Oliver,
Leshchenko Natalja M.,
Sotskov Yuri N.
Publication year - 2006
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2006.00533.x
Subject(s) - unary operation , job shop scheduling , computer science , scheduling (production processes) , interval (graph theory) , mathematical optimization , binary number , mathematics , combinatorics , arithmetic , schedule , operating system
This article deals with the scheduling problem of minimizing the makespan in a two‐machine job‐shop with given w intervals of machine non‐availability. It is known that this problem is binary (unary) NP‐hard if there is at least one non‐availability interval (if the number of non‐availability intervals may be arbitrarily large), and all the jobs have the same machine route. We find sufficient conditions when Jackson's pair of permutations remains optimal for the two‐machine job‐shop problem with w 1 non‐availability intervals. Extensive computational studies show the effectiveness (in the number of problems solved) and efficiency (in computational time) of these conditions for the randomly generated instances with up to 10,000 jobs and w 5000 non‐availability intervals.