An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines

Xiaoyun Xiong, Peng Zhou, Yunqiang Yin, T. C.E. Cheng, Dengfeng Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)502-516
Number of pages15
JournalNaval Research Logistics
Volume66
Issue number6
DOIs
Publication statusPublished - 1 Jan 2019

Keywords

  • branch-and-price
  • column generation
  • multitasking
  • scheduling

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Cite this