Premium
An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines
Author(s) -
Xiong Xiaoyun,
Zhou Peng,
Yin Yunqiang,
Cheng T. C. E.,
Li Dengfeng
Publication year - 2019
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21863
Subject(s) - human multitasking , column generation , computer science , mathematical optimization , scheduling (production processes) , job shop scheduling , computer multitasking , greedy algorithm , algorithm , parallel computing , mathematics , schedule , psychology , cognitive psychology , operating system
We consider the multitasking scheduling problem on unrelated parallel machines to minimize the total weighted completion time. In this problem, each machine processes a set of jobs, while the processing of a selected job on a machine may be interrupted by other available jobs scheduled on the same machine but unfinished. To solve this problem, we propose an exact branch‐and‐price algorithm, where the master problem at each search node is solved by a novel column generation scheme, called in‐out column generation, to maintain the stability of the dual variables. We use a greedy heuristic to obtain a set of initial columns to start the in‐out column generation, and a hybrid strategy combining a genetic algorithm and an exact dynamic programming algorithm to solve the pricing subproblems approximately and exactly, respectively. Using randomly generated data, we conduct numerical studies to evaluate the performance of the proposed solution approach. We also examine the effects of multitasking on the scheduling outcomes, with which the decision maker can justify making investments to adopt or avoid multitasking.