One-machine job-scheduling with non-constant capacity - Minimizing weighted completion times

H.F. Amaddeo, H.F. Amaddeo, W.M. Nawijn, Aart van Harten

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)
    51 Downloads (Pure)

    Abstract

    In this paper an n-job one-machine scheduling problem is considered, in which the machine capacity is time-dependent and jobs are characterized by their work content. The objective is to minimize the sum of weighted completion times. A necessary optimality condition is presented and we discuss some special cases where this condition is also sufficient. We prove that the problem is NP-complete. A branch-and-bound algorithm is developed for the case when the capacity function is a step function. Computational results for 1000 test problems are presented.
    Original languageUndefined
    Pages (from-to)502-512
    Number of pages11
    JournalEuropean journal of operational research
    Volume102
    Issue number3
    DOIs
    Publication statusPublished - 1997

    Keywords

    • IR-30131
    • METIS-140770

    Cite this