Output details

A polynomial-time algorithm for a flow-shop batching problem with equal-length operations

<12>This paper, published in the leading scheduling journal, settles the complexity status of a batching problem with a long history of study. Each of the earlier papers (Cheng et al. 2000, Mosheiov and Oron 2005, Ng and Kovalyov 2007) provided improved results, but the main question on the existence of a polynomial-time algorithm remained open. We propose an original technique, combining insights from scheduling and number theory, to develop a polynomial-time algorithm of complexity O(log^3(n)). A similar result (but of a slightly worse O(log^4(n)) complexity) by Ng et al. 2009 was proposed independently. The paper led to follow-up funding (EP/K041274/1).