2009 | OriginalPaper | Buchkapitel
Bicriteria Scheduling on Single-Machine with Inventory Operations
verfasst von : Baoqiang Fan, Rongjun Chen, Guochun Tang
Erschienen in: Combinatorial Optimization and Applications
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
In this paper, we consider the single machine scheduling problem with inventory operations. The objective is to minimize makespan subject to the constraint that the total number of tardy jobs is minimum. We show the problem is strongly NP-hard. A polynomial (1 + 1/(
m
− 1))-approximation scheme for the problem is presented, where
m
is defined as the total job’s processing times ∑
p
j
divided by the capacity
c
of the storage, and an optimal algorithm for a special case of the problem, in which each job is one unit in size, is provided.