A Single-machine Scheduling with Generalized Due Dates to Minimize Total Weighted Late Work
Myoung-Ju Park, Byung-Cheon Choi
Asian Research Journal of Mathematics · pp. 1–6 · Published 11 Apr 2022
10.9734/arjom/2022/v18i430368Abstract
In the paper, we consider a single-machine scheduling problem with generalized due dates, in which the objective is to minimize total weighted work. This problem was proven to be NP-hard by Mosheiov et al. [1]. However, the exact complexity remains open. We show that the problem is strongly NP-hard, and is weakly NP-hard if the lengths of the intervals between the consecutive due dates are identical.
Cited by 0
No indexed citations yet.
Related research
- The Computational Limit to Quantum Determinism and the Black Hole Information Loss Paradox — shares topic coverage
- Computational Solution to Quantum Foundational Problems — shares topic coverage
- Acceleration of Biological Sequence Alignment Using Residue Number System — shares topic coverage
- A Computational Complexity Analysis of an Algorithm for Reliability Optimization — shares topic coverage
- A Conceptual Approach to Resources Allocation Scheduling — shares topic coverage
Article metrics
Real usage data collected on this platform.
13
Page views
0
PDF downloads
0
Outbound clicks
0
Citations
Views over time
Views by country
Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".
Traffic sources
Referring site, by host.
Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.