A New Theorem for Lower Bounds in NP-Hard Multi-Objective Scheduling Problems
Abstrak
On a single machine, each of n jobs must be processed continuously. At time zero, every job is ready for processing. The tasks to process a sequence that minimizes the total sum of competition times plus the sum of tardiness . This bi-criteria problem is NP-hard because of the second one. We provide a theorem that demonstrates a relationship between the optimal solution, lower bounds, and the number of efficient solutions. The case is that the theorem works for NP-hard problems, whereas in previous works the focus was on P-hard problems. The theorem limits the lower bound's range, which is crucial for determining the best answer. Additionally, the theorem allows for discovering new lower bounds by opening algebraic procedures and concepts.
Topik & Kata Kunci
Penulis (2)
Hassan A. Mahmood
Ayad M. Ramadan
Akses Cepat
PDF tidak tersedia langsung
Cek di sumber asli →- Tahun Terbit
- 2025
- Sumber Database
- DOAJ
- DOI
- 10.33899/iqjoss.v22i2.54081
- Akses
- Open Access ✓