Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Single-Machine Scheduling Problems with Two Agents Competing for Makespan
verfasst von : Guosheng Ding, Shijie Sun
Erschienen in: Life System Modeling and Intelligent Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper considers the single-machine scheduling problems in which two distinct agents are concerned. Each agent has a set of jobs with different release times, and both of them expect to complete their respective jobs as early as possible. We take the makespan of each agent as its own criterion and take the linear combination of the two makespans as our objective function. In this paper, both off-line and on-line models are considered. When preemption is allowed, we present an exact algorithm for the off-line model and an optimal algorithm for the on-line model. When preemption is not allowed we point out that the problem is NP-hard for the off-line model and give a (2 + 1/
θ
)-competitive algorithm for the on-line model. We also prove that a lower bound of the competitive ratio for the later model is 1 +
θ
/(1 +
θ
), where
θ
is a given factor not less than 1.