<link rel="stylesheet" href="styles.cf390c6bfbe7555f.css">

Browsing by Author "Posner, Marc E."

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item type:Item,
    Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs
    (2019-08-01)
    Hung, Hui-Chih
    ;
    Lin, Bertrand M. T.
    ;
    Posner, Marc E.
    ;
    Wei, Jun-Min
    ;
    工業工程與管理學系
    This paper investigates the classical preemptive parallel-machine scheduling problem of maximizing number of on-time jobs. While the problem is known to be NP-hard, no theoretical analysis of approximation algorithms exists in the literature. As part of the analysis, a new non-standard mixed integer formulation is developed. We propose heuristics based on different design strategies. These heuristics have asymptotically tight relative errors of 1/2. Experimental tests evaluate the computational performance of the procedures.