An iterated local search and tabu search for two-parallel machine scheduling problem to minimize the maximum total completion time. Issue 3 (3rd April 2019)

• Record Type: Journal Article
• Authors: Xu, Jianyou; Liu, Shang-Chia; Zhao, Chuanli; Wu, Junjie; Lin, Win-Chin; Yu, Pay-Wen
• Is Part Of: Journal of information & optimization sciences. Volume 40:Issue 3(2019)
• Page Start: 751
• Page End: 766
• Publication Date: 2019-04-03
• Subjects: (2010) Primary: 90B35 -- Secondary: 90C26; Scheduling -- Parallel machine -- Maximum total completion time -- Iterated local search -- Tabu search algorithm; Electronic data processing -- Periodicals; Information science -- Periodicals; Mathematical optimization -- Periodicals; 519.6
• DOI: 10.1080/02522667.2018.1468610
• Languages: English
• ISSNs: 0252-2667

Abstract

Abstract: The parallel machine scheduling problems exist in many real-life industrial examples. In order to effectively utilize the machines and decline the total waiting time of jobs assigned to each machine, the maximum total completion time per machine on a parallel machine is thus addressed. Due to the NP-hardness of the problem under consideration, in this paper the authors explore an optimal solution by a branch-and-bound method, incorporating several dominances and a lower bound. In addition, the authors also adopted an iterated local search (ILS) and a Tabu search to find its near-optimal solution for the problem. The computational results on randomly generated instances illustrate that the proposed Tabu search algorithm performs better than the two existing algorithms, and the ILS method for the small jobs, but the ILS method performs better than the two existing algorithms and Tabu search algorithm for the bigger jobs.