Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm
This paper considers a different version of the parallel machines scheduling problem in which the parallel jobs simultaneously requirea pre-specifiedjob-dependent number of machines when being processed.This relaxation departs from one of the classic scheduling assumptions. While the analytical cond...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Islamic Azad University, Qazvin Branch
2020-07-01
|
| Series: | Journal of Optimization in Industrial Engineering |
| Subjects: | |
| Online Access: | http://www.qjie.ir/article_538024_76d7b62328a6ea292f9b08df703e5028.pdf |
| _version_ | 1818959265734328320 |
|---|---|
| author | Javad Behnamian |
| author_facet | Javad Behnamian |
| author_sort | Javad Behnamian |
| collection | DOAJ |
| description | This paper considers a different version of the parallel machines scheduling problem in which the parallel jobs simultaneously requirea pre-specifiedjob-dependent number of machines when being processed.This relaxation departs from one of the classic scheduling assumptions. While the analytical conditions can be easily statedfor some simple models, a graph model approach is required when conflicts of processor usage are present. The main decisions and solving steps are as follows, respectively. (i) Converting the scheduling problem to graph model; (ii) Dividing jobs into independent sets: in this phase, we propose a semi-definite relaxation algorithm in which we use graph coloring concept; (iii) Sequencing the independent sets as a single-machine scheduling in which jobs in such a system arejob sets formed by using a semi-definite relaxation solution and determining the problem as a schedule that minimizes the sum of the tardiness of jobs. In this regard, after grouping the jobs by a semi-definite programming relaxation algorithm, we used the rounding algorithm for graph coloring. We also proposed a variable neighborhood search algorithm for sequencing the obtained job sets in order to minimize the sum of the tardiness. Experimental results show that this methodology is interesting by obtaining good results. |
| first_indexed | 2024-12-20T11:38:54Z |
| format | Article |
| id | doaj.art-104ff24cf5454da298baf7f31ca4a063 |
| institution | Directory Open Access Journal |
| issn | 2251-9904 2423-3935 |
| language | English |
| last_indexed | 2024-12-20T11:38:54Z |
| publishDate | 2020-07-01 |
| publisher | Islamic Azad University, Qazvin Branch |
| record_format | Article |
| series | Journal of Optimization in Industrial Engineering |
| spelling | doaj.art-104ff24cf5454da298baf7f31ca4a0632022-12-21T19:42:01ZengIslamic Azad University, Qazvin BranchJournal of Optimization in Industrial Engineering2251-99042423-39352020-07-0113219921010.22094/joie.2017.599.1385538024Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based AlgorithmJavad Behnamian0Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, IranThis paper considers a different version of the parallel machines scheduling problem in which the parallel jobs simultaneously requirea pre-specifiedjob-dependent number of machines when being processed.This relaxation departs from one of the classic scheduling assumptions. While the analytical conditions can be easily statedfor some simple models, a graph model approach is required when conflicts of processor usage are present. The main decisions and solving steps are as follows, respectively. (i) Converting the scheduling problem to graph model; (ii) Dividing jobs into independent sets: in this phase, we propose a semi-definite relaxation algorithm in which we use graph coloring concept; (iii) Sequencing the independent sets as a single-machine scheduling in which jobs in such a system arejob sets formed by using a semi-definite relaxation solution and determining the problem as a schedule that minimizes the sum of the tardiness of jobs. In this regard, after grouping the jobs by a semi-definite programming relaxation algorithm, we used the rounding algorithm for graph coloring. We also proposed a variable neighborhood search algorithm for sequencing the obtained job sets in order to minimize the sum of the tardiness. Experimental results show that this methodology is interesting by obtaining good results.http://www.qjie.ir/article_538024_76d7b62328a6ea292f9b08df703e5028.pdfparallel jobs schedulingsemidefinite relaxationtardinessgraph coloring |
| spellingShingle | Javad Behnamian Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm Journal of Optimization in Industrial Engineering parallel jobs scheduling semidefinite relaxation tardiness graph coloring |
| title | Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm |
| title_full | Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm |
| title_fullStr | Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm |
| title_full_unstemmed | Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm |
| title_short | Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm |
| title_sort | parallel jobs scheduling with a specific due date asemi definite relaxation based algorithm |
| topic | parallel jobs scheduling semidefinite relaxation tardiness graph coloring |
| url | http://www.qjie.ir/article_538024_76d7b62328a6ea292f9b08df703e5028.pdf |
| work_keys_str_mv | AT javadbehnamian paralleljobsschedulingwithaspecificduedateasemidefiniterelaxationbasedalgorithm |