Online Scheduling on a Single Machine with Grouped Processing Times
We consider the online scheduling problem on a single machine with the assumption that all jobs have their processing times in [p,(1+α)p], where p>0 and α=(5-1)/2. All jobs arrive over time, and each job and its processing time become known at its arrival time. The jobs should be first processed...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2015-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2015/805294 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832563067167178752 |
|---|---|
| author | Qijia Liu Long Wan Lijun Wei |
| author_facet | Qijia Liu Long Wan Lijun Wei |
| author_sort | Qijia Liu |
| collection | DOAJ |
| description | We consider the online scheduling problem on a single machine with the assumption that all jobs have their processing times in [p,(1+α)p], where p>0 and α=(5-1)/2. All jobs arrive over time, and each job and its processing time become known at its arrival time. The jobs should be first processed on a single machine and then delivered by a vehicle to some customer. When the capacity of the vehicle is infinite, we provide an online algorithm with the best competitive ratio of (5+1)/2. When the capacity of the vehicle is finite, that is, the vehicle can deliver at most c jobs at a time, we provide another best possible online algorithm with the competitive ratio of (5+1)/2. |
| format | Article |
| id | doaj-art-0741dda916e34b56ae2227f481db20e9 |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2015-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-0741dda916e34b56ae2227f481db20e92025-02-03T01:20:59ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2015-01-01201510.1155/2015/805294805294Online Scheduling on a Single Machine with Grouped Processing TimesQijia Liu0Long Wan1Lijun Wei2School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, ChinaSchool of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, ChinaSchool of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, ChinaWe consider the online scheduling problem on a single machine with the assumption that all jobs have their processing times in [p,(1+α)p], where p>0 and α=(5-1)/2. All jobs arrive over time, and each job and its processing time become known at its arrival time. The jobs should be first processed on a single machine and then delivered by a vehicle to some customer. When the capacity of the vehicle is infinite, we provide an online algorithm with the best competitive ratio of (5+1)/2. When the capacity of the vehicle is finite, that is, the vehicle can deliver at most c jobs at a time, we provide another best possible online algorithm with the competitive ratio of (5+1)/2.http://dx.doi.org/10.1155/2015/805294 |
| spellingShingle | Qijia Liu Long Wan Lijun Wei Online Scheduling on a Single Machine with Grouped Processing Times Discrete Dynamics in Nature and Society |
| title | Online Scheduling on a Single Machine with Grouped Processing Times |
| title_full | Online Scheduling on a Single Machine with Grouped Processing Times |
| title_fullStr | Online Scheduling on a Single Machine with Grouped Processing Times |
| title_full_unstemmed | Online Scheduling on a Single Machine with Grouped Processing Times |
| title_short | Online Scheduling on a Single Machine with Grouped Processing Times |
| title_sort | online scheduling on a single machine with grouped processing times |
| url | http://dx.doi.org/10.1155/2015/805294 |
| work_keys_str_mv | AT qijialiu onlineschedulingonasinglemachinewithgroupedprocessingtimes AT longwan onlineschedulingonasinglemachinewithgroupedprocessingtimes AT lijunwei onlineschedulingonasinglemachinewithgroupedprocessingtimes |