A note on combined job selection and sequencing problems

Christos Koulamas and Shrikant. S. Panwalkar

Naval Research Logistics (NRL), 2013, vol. 60, issue 6, 449-453

Abstract: We investigate the solvability of two single‐machine scheduling problems when the objective is to identify among all job subsets with cardinality k,1≤k≤n, the one that has the minimum objective function value. For the single‐machine minimum maximum lateness problem, we conclude that the problem is solvable in O(n2) time using the proposed REMOVE algorithm. This algorithm can also be used as an alternative to Moore's algorithm to solve the minimum number of tardy jobs problem by actually solving the hierarchical problem in which the objective is to minimize the maximum lateness subject to the minimum number of tardy jobs. We then show that the REMOVE algorithm cannot be used to solve the general case of the single‐machine total‐weighted completion time problem; we derive sufficient conditions among the job parameters so that the total weighted completion time problem becomes solvable in O(n2) time. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 449–453, 2013

Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/nav.21543

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:60:y:2013:i:6:p:449-453

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().