Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time
This paper investigates semi-online scheduling problems on two parallel machines under a grade of service (GoS) provision subject to minimize the makespan. We consider three different semi-online versions with knowing the total processing time of the jobs with higher GoS level, knowing the total pro...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/576234 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832564278004023296 |
|---|---|
| author | Taibo Luo Yinfeng Xu |
| author_facet | Taibo Luo Yinfeng Xu |
| author_sort | Taibo Luo |
| collection | DOAJ |
| description | This paper investigates semi-online scheduling problems on two parallel machines under a grade of service (GoS) provision subject to minimize the makespan. We consider three different semi-online versions with knowing the total processing time of the jobs with higher GoS level, knowing the total processing time of the jobs with lower GoS level, or knowing both in advance. Respectively, for the three semi-online versions, we develop algorithms with competitive ratios of 3/2, 20/13, and 4/3 which are shown to be optimal. |
| format | Article |
| id | doaj-art-90c393a8d97a4452a8af403e7a92aacc |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-90c393a8d97a4452a8af403e7a92aacc2025-02-03T01:11:24ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/576234576234Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing TimeTaibo Luo0Yinfeng Xu1Business School, Sichuan University, Chengdu 610065, ChinaBusiness School, Sichuan University, Chengdu 610065, ChinaThis paper investigates semi-online scheduling problems on two parallel machines under a grade of service (GoS) provision subject to minimize the makespan. We consider three different semi-online versions with knowing the total processing time of the jobs with higher GoS level, knowing the total processing time of the jobs with lower GoS level, or knowing both in advance. Respectively, for the three semi-online versions, we develop algorithms with competitive ratios of 3/2, 20/13, and 4/3 which are shown to be optimal.http://dx.doi.org/10.1155/2014/576234 |
| spellingShingle | Taibo Luo Yinfeng Xu Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time The Scientific World Journal |
| title | Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time |
| title_full | Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time |
| title_fullStr | Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time |
| title_full_unstemmed | Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time |
| title_short | Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time |
| title_sort | semi online scheduling on two machines with gos levels and partial information of processing time |
| url | http://dx.doi.org/10.1155/2014/576234 |
| work_keys_str_mv | AT taiboluo semionlineschedulingontwomachineswithgoslevelsandpartialinformationofprocessingtime AT yinfengxu semionlineschedulingontwomachineswithgoslevelsandpartialinformationofprocessingtime |