Two parallel identical machines scheduling to minimise the maximum inter-completion time

Feifeng Zheng, Yang Sui, E Zhang, Yinfeng Xu and Ming Liu

International Journal of Production Research, 2020, vol. 58, issue 22, 6811-6825

Abstract: In many manufacturing and service systems, it is of great importance to generate processing schedules with strong response abilities to unexpected or urgent jobs. In this paper, we investigate the problem of scheduling jobs on two parallel identical machines. The objective is to minimise the maximum difference between any two consecutive completion times of jobs, i.e. to minimise the maximum inter-completion time. The processing of any job cannot be interrupted, and a smaller objective value of the processing schedule implies a faster response to an unexpected job that may arrive at any time point. The problem was introduced by Zheng, Pinedo, Lee, Liu, and Xu [2019. “Towards Robustness of Response Times: Minimising the Maximum Inter-completion Time on Parallel Machines.” International Journal of Production Research 57 (1): 182–199]. In this work, we first give a sufficient condition of feasible solutions with respect to the makespan constraint, and reveal several basic properties of any optimal solution. We then prove a theoretical lower bound of the objective value, and propose a $O(n^2) $O(n2) time algorithm to compute the lower bound. An efficient heuristic algorithm is further constructed to solve the considered problem. Experimental results show that the proposed algorithm outperforms all the three heuristics introduced in Zheng, Pinedo, Lee, Liu, and Xu 2019.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2019.1685707 (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:58:y:2020:i:22:p:6811-6825

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

DOI: 10.1080/00207543.2019.1685707

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