Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem

Youngho Lee, Hanif D. Sherali

    Research output: Contribution to journalArticlepeer-review

    17 Citations (Scopus)

    Abstract

    This paper deals with an unrelated machine scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. We present a zero-one integer programming formulation of this problem. The linear programming relaxation of this formulation affords a tight lower bound and often generates an integer optimal solution for the problem. By exploiting the special structures inherent in the formulation, we develop some classes of strong valid inequalities that can be used to tighten the initial formulation, as well as to provide cutting planes in the context of a branch-and-cut procedure. A major computational bottleneck is the solution of the underlying linear programming relaxation because of the extremely high degree of degeneracy inherent in the formulation. In order to overcome this difficulty, we employ a Lagrangian dual formulation to generate lower and upper bounds and to drive the branch-and-bound algorithm. As a practical instance of the unrelated machine scheduling problem, we describe a combinatorial naval defense problem. This problem seeks to schedule a set of illuminators (passive homing devices) in order to strike a given set of targets using surface-to-air missiles in a naval battle-group engagement scenario. We present computational results for this problem using suitable realistic data.

    Original languageEnglish
    Pages (from-to)339-365
    Number of pages27
    JournalAnnals of Operations Research
    Volume50
    Issue number1
    DOIs
    Publication statusPublished - 1994 Dec

    Keywords

    • Lagrangian relaxation
    • Unrelated machine scheduling
    • strong integer programming formulation
    • time-window constraints

    ASJC Scopus subject areas

    • General Decision Sciences
    • Management Science and Operations Research

    Fingerprint

    Dive into the research topics of 'Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem'. Together they form a unique fingerprint.

    Cite this