Minimizing the makespan for the two-machine scheduling problem with a single server: Two algorithms for very large instances. Issue 1 (2nd January 2016)

• Record Type: Journal Article
• Authors: Hasani, Keramat; Kravchenko, Svetlana A.; Werner, Frank
• Is Part Of: Engineering optimization. Volume 48:Issue 1(2016)
• Page Start: 173
• Page End: 183
• Publication Date: 2016-01-02
• Subjects: scheduling -- parallel machines -- single server -- lower bound -- machine idle time -- server waiting time; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2015.1005083
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : This article considers the problem of scheduling a given set of n jobs on two identical parallel machines with a single server. Each job must be processed on one of the machines. Before processing, the server has to set up the relevant machine. The objective is to minimize the makespan. For this unary NP-hard problem, two fast constructive algorithms with a complexity of O ( n 2 ) are presented. The performance of these algorithms is evaluated for instances with up to 10, 000 jobs. Computational results indicate that the algorithms have an excellent performance for very large instances so that the obtained objective function values are very close to a lower bound, and in many cases even an optimal solution is achieved. Superiority over all existing algorithms is obtained by sequencing the jobs on the two machines so that the machine idle time and the server waiting time are minimized. In doing so, the characteristics of an optimal solution resulting from its relevant lower bound are taken into account.