Open shop scheduling problem to minimize total weighted completion time. Issue 1 (2nd January 2017)

• Record Type: Journal Article
• Authors: Bai, Danyu; Zhang, Zhihai; Zhang, Qiang; Tang, Mengqian
• Is Part Of: Engineering optimization. Volume 49:Issue 1(2017)
• Page Start: 98
• Page End: 112
• Publication Date: 2017-01-02
• Subjects: Scheduling -- open shop -- total weighted completion time -- asymptotic analysis -- discrete differential evolution; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2016.1164854
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: A given number of jobs in an open shop scheduling environment must each be processed for given amounts of time on each of a given set of machines in an arbitrary sequence. This study aims to achieve a schedule that minimizes total weighted completion time. Owing to the strong NP-hardness of the problem, the weighted shortest processing time block (WSPTB) heuristic is presented to obtain approximate solutions for large-scale problems. Performance analysis proves the asymptotic optimality of the WSPTB heuristic in the sense of probability limits. The largest weight block rule is provided to seek optimal schedules in polynomial time for a special case. A hybrid discrete differential evolution algorithm is designed to obtain high-quality solutions for moderate-scale problems. Simulation experiments demonstrate the effectiveness of the proposed algorithms.