Single machine Pareto scheduling with positional deadlines and agreeable release and processing times
This paper studies the problem of scheduling $ n $ jobs on a single machine to minimize total completion time and maximum cost, simultaneously. Each job is associated with a positional deadline that indicates the largest ordinal number of this job in any feasible schedule. The jobs have agreeable re...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AIMS Press
2023-03-01
|
| Series: | Electronic Research Archive |
| Subjects: | |
| Online Access: | https://www.aimspress.com/article/doi/10.3934/era.2023154?viewType=HTML |
| _version_ | 1827951767994761216 |
|---|---|
| author | Shuguang Li Yong Sun Muhammad Ijaz Khan |
| author_facet | Shuguang Li Yong Sun Muhammad Ijaz Khan |
| author_sort | Shuguang Li |
| collection | DOAJ |
| description | This paper studies the problem of scheduling $ n $ jobs on a single machine to minimize total completion time and maximum cost, simultaneously. Each job is associated with a positional deadline that indicates the largest ordinal number of this job in any feasible schedule. The jobs have agreeable release and processing times, meaning that jobs with larger release times also have larger processing times. The agreeability assumption is reasonable since both the single-criterion problems (without positional deadline constraints) of minimizing total completion time and maximum lateness on a single machine with arbitrary release and processing times are strongly NP-hard. An $ O(n^3) $-time Pareto optimal algorithm is presented. The previously known algorithms only solve two special cases of the agreeability assumption: either the case of equal release times in $ O(n^4) $ time, or the case of equal processing times (without positional deadline constraints) in $ O(n^3) $ time. |
| first_indexed | 2024-04-09T13:46:43Z |
| format | Article |
| id | doaj.art-30f79636129a4d83b50aea9783b24c2f |
| institution | Directory Open Access Journal |
| issn | 2688-1594 |
| language | English |
| last_indexed | 2024-04-09T13:46:43Z |
| publishDate | 2023-03-01 |
| publisher | AIMS Press |
| record_format | Article |
| series | Electronic Research Archive |
| spelling | doaj.art-30f79636129a4d83b50aea9783b24c2f2023-05-09T01:13:09ZengAIMS PressElectronic Research Archive2688-15942023-03-013153050306310.3934/era.2023154Single machine Pareto scheduling with positional deadlines and agreeable release and processing timesShuguang Li0Yong Sun 1Muhammad Ijaz Khan21. School of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, China1. School of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, China2. Department of Mechanical Engineering, Lebanese American University, Beirut 362060, Lebanon 3. Department of Mechanics and Engineering Science, Peking University, Beijing 100871, ChinaThis paper studies the problem of scheduling $ n $ jobs on a single machine to minimize total completion time and maximum cost, simultaneously. Each job is associated with a positional deadline that indicates the largest ordinal number of this job in any feasible schedule. The jobs have agreeable release and processing times, meaning that jobs with larger release times also have larger processing times. The agreeability assumption is reasonable since both the single-criterion problems (without positional deadline constraints) of minimizing total completion time and maximum lateness on a single machine with arbitrary release and processing times are strongly NP-hard. An $ O(n^3) $-time Pareto optimal algorithm is presented. The previously known algorithms only solve two special cases of the agreeability assumption: either the case of equal release times in $ O(n^4) $ time, or the case of equal processing times (without positional deadline constraints) in $ O(n^3) $ time.https://www.aimspress.com/article/doi/10.3934/era.2023154?viewType=HTMLschedulingpareto optimizationsingle machinepositional deadlinesrelease times |
| spellingShingle | Shuguang Li Yong Sun Muhammad Ijaz Khan Single machine Pareto scheduling with positional deadlines and agreeable release and processing times Electronic Research Archive scheduling pareto optimization single machine positional deadlines release times |
| title | Single machine Pareto scheduling with positional deadlines and agreeable release and processing times |
| title_full | Single machine Pareto scheduling with positional deadlines and agreeable release and processing times |
| title_fullStr | Single machine Pareto scheduling with positional deadlines and agreeable release and processing times |
| title_full_unstemmed | Single machine Pareto scheduling with positional deadlines and agreeable release and processing times |
| title_short | Single machine Pareto scheduling with positional deadlines and agreeable release and processing times |
| title_sort | single machine pareto scheduling with positional deadlines and agreeable release and processing times |
| topic | scheduling pareto optimization single machine positional deadlines release times |
| url | https://www.aimspress.com/article/doi/10.3934/era.2023154?viewType=HTML |
| work_keys_str_mv | AT shuguangli singlemachineparetoschedulingwithpositionaldeadlinesandagreeablereleaseandprocessingtimes AT yongsun singlemachineparetoschedulingwithpositionaldeadlinesandagreeablereleaseandprocessingtimes AT muhammadijazkhan singlemachineparetoschedulingwithpositionaldeadlinesandagreeablereleaseandprocessingtimes |