Open shop scheduling problem to minimize total weighted completion time

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.

KEYWORDS:

• Scheduling
• open shop
• total weighted completion time
• asymptotic analysis
• discrete differential evolution

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research is partly supported by the National Natural Science Foundation of China [grant nos 71201107 and 71371106] and the State Key Program of National Natural Science Foundation of China [grant no. 71332005].