A new model for completion time variance problem with job-dependent weights and controllable processing times

Chi To Ng, X. Cai

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


We consider a new model for scheduling n jobs on a single machine. Each job requires a processing time pi, which may be compressed at an additional cost, and is associated with a weight wi. The objective is to minimize the weighted variance of completion times and the total cost incurred from the compression of processing times. This is the WCTV problem with controllable processing times. The WCTV problem with equal weight and with noncontrollable processing times has been shown to be NP-hard. In this paper, we describe optimality properties, and we propose a heuristic algorithm to solve the problem. Computational results are reported that demonstrate the effectiveness of the algorithm.
Original languageEnglish
Pages (from-to)306-309
Number of pages4
JournalInternational Journal of Modelling and Simulation
Issue number4
Publication statusPublished - 1 Jan 1997


  • Completion time variance
  • Heuristic
  • Modelling
  • Optimization
  • Scheduling

ASJC Scopus subject areas

  • Software
  • Modelling and Simulation
  • Mechanics of Materials
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this