Scheduling a Single Machine with Primary and Secondary Objectives
We study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme to minimize the maximum job lateness, with...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-06-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/11/6/80 |
| _version_ | 1811327053100744704 |
|---|---|
| author | Nodari Vakhania |
| author_facet | Nodari Vakhania |
| author_sort | Nodari Vakhania |
| collection | DOAJ |
| description | We study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme to minimize the maximum job lateness, with the secondary objective to minimize the maximum job completion time. The problem of finding the Pareto-optimal set of feasible solutions with these two objective criteria is strongly NP-hard. We give the dominance properties and conditions when the Pareto-optimal set can be formed in polynomial time. These properties, together with our general framework, provide the theoretical background, so that the basic framework can be expanded to (exponential-time) implicit enumeration algorithms and polynomial-time approximation algorithms (generating the Pareto sub-optimal frontier with a fair balance between the two objectives). Some available in the literature experimental results confirm the practical efficiency of the proposed framework. |
| first_indexed | 2024-04-13T14:59:49Z |
| format | Article |
| id | doaj.art-328f7723c5914b0891522bd95b92e1df |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-13T14:59:49Z |
| publishDate | 2018-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-328f7723c5914b0891522bd95b92e1df2022-12-22T02:42:20ZengMDPI AGAlgorithms1999-48932018-06-011168010.3390/a11060080a11060080Scheduling a Single Machine with Primary and Secondary ObjectivesNodari Vakhania0Centro de Investigación en Ciencias, Universidad Autonoma del Estado de Morelos, 62210 Cuernavaca, MexicoWe study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme to minimize the maximum job lateness, with the secondary objective to minimize the maximum job completion time. The problem of finding the Pareto-optimal set of feasible solutions with these two objective criteria is strongly NP-hard. We give the dominance properties and conditions when the Pareto-optimal set can be formed in polynomial time. These properties, together with our general framework, provide the theoretical background, so that the basic framework can be expanded to (exponential-time) implicit enumeration algorithms and polynomial-time approximation algorithms (generating the Pareto sub-optimal frontier with a fair balance between the two objectives). Some available in the literature experimental results confirm the practical efficiency of the proposed framework.http://www.mdpi.com/1999-4893/11/6/80scheduling single machinerelease timelatenessmakespanbi-criteria schedulingPareto-optimal solution |
| spellingShingle | Nodari Vakhania Scheduling a Single Machine with Primary and Secondary Objectives Algorithms scheduling single machine release time lateness makespan bi-criteria scheduling Pareto-optimal solution |
| title | Scheduling a Single Machine with Primary and Secondary Objectives |
| title_full | Scheduling a Single Machine with Primary and Secondary Objectives |
| title_fullStr | Scheduling a Single Machine with Primary and Secondary Objectives |
| title_full_unstemmed | Scheduling a Single Machine with Primary and Secondary Objectives |
| title_short | Scheduling a Single Machine with Primary and Secondary Objectives |
| title_sort | scheduling a single machine with primary and secondary objectives |
| topic | scheduling single machine release time lateness makespan bi-criteria scheduling Pareto-optimal solution |
| url | http://www.mdpi.com/1999-4893/11/6/80 |
| work_keys_str_mv | AT nodarivakhania schedulingasinglemachinewithprimaryandsecondaryobjectives |