A note on minimising total absolute deviation of job completion times on a two-machine no-wait proportionate flowshop

Yoav Ben-Yehoshua, Eyal Hariri and Gur Mosheiov

International Journal of Production Research, 2015, vol. 53, issue 19, 5717-5724

Abstract: A popular measure used in service systems is that of total absolute deviation of job completion times (TADC). It is relevant to settings where the objective is to balance the level of service provided to different customers. During the last decade, TADC has been studied in various machine settings, and under various assumptions on the job processing times. In this note, we study TADC on a two-machine no-wait proportionate flow shop, i.e. a flow shop with machine-independent processing times, and with no buffer between the machines. A very surprising and unique result is introduced: a simple index policy (the well-known largest processing time (LPT) first sequence) is shown to be optimal for instances of no more than seven jobs. This property does not hold for larger instances. We show that for instances of eight and nine jobs, there are exactly two schedules which are candidates for optimality. For the 10-job instance, the number of candidates increases. This uncommon behaviour of the optimal solution and, consequently, the complexity of the problem studied here, remain open questions, and are challenging topics for future research.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2014.991843 (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:53:y:2015:i:19:p:5717-5724

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

DOI: 10.1080/00207543.2014.991843

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 ().