Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times(机器带准备时间的三台平行机排序问题的线性时间算法)
对于机器带准备时间的平行机排序问题，研究了3台机器的情况，给出了线性时间的对偶阈值算法族DA3（ε）（其中ε为可选参数），并证明了当时，对偶阈值算法的近似比为，且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法....
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Zhejiang University Press
2005-05-01
|
| Series: | Zhejiang Daxue xuebao. Lixue ban |
| Subjects: | |
| Online Access: | https://doi.org/zjup/1008-9497.2005.32.3.258-263 |
| _version_ | 1797236352664731648 |
|---|---|
| author | FANJing(范静) YANGQi-fan(杨启帆) |
| author_facet | FANJing(范静) YANGQi-fan(杨启帆) |
| author_sort | FANJing(范静) |
| collection | DOAJ |
| description | 对于机器带准备时间的平行机排序问题，研究了3台机器的情况，给出了线性时间的对偶阈值算法族DA3（ε）（其中ε为可选参数），并证明了当时，对偶阈值算法的近似比为，且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法. |
| first_indexed | 2024-04-24T17:02:30Z |
| format | Article |
| id | doaj.art-5353a359ba6a4c639aee9af01ca48418 |
| institution | Directory Open Access Journal |
| issn | 1008-9497 |
| language | zho |
| last_indexed | 2024-04-24T17:02:30Z |
| publishDate | 2005-05-01 |
| publisher | Zhejiang University Press |
| record_format | Article |
| series | Zhejiang Daxue xuebao. Lixue ban |
| spelling | doaj.art-5353a359ba6a4c639aee9af01ca484182024-03-29T01:58:22ZzhoZhejiang University PressZhejiang Daxue xuebao. Lixue ban1008-94972005-05-01323258263zjup/1008-9497.2005.32.3.258-263Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times(机器带准备时间的三台平行机排序问题的线性时间算法)FANJing(范静)0YANGQi-fan(杨启帆)1Department of Mathematics, Zhejiang University, Hangzhou 310027, China(浙江大学数学系，浙江 杭州 310027)Department of Mathematics, Zhejiang University, Hangzhou 310027, China(浙江大学数学系，浙江 杭州 310027)对于机器带准备时间的平行机排序问题，研究了3台机器的情况，给出了线性时间的对偶阈值算法族DA3（ε）（其中ε为可选参数），并证明了当时，对偶阈值算法的近似比为，且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法.https://doi.org/zjup/1008-9497.2005.32.3.258-263排序近似比机器准备时间线性时间 |
| spellingShingle | FANJing(范静) YANGQi-fan(杨启帆) Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times(机器带准备时间的三台平行机排序问题的线性时间算法) Zhejiang Daxue xuebao. Lixue ban 排序 近似比 机器准备时间 线性时间 |
| title | Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times(机器带准备时间的三台平行机排序问题的线性时间算法) |
| title_full | Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times(机器带准备时间的三台平行机排序问题的线性时间算法) |
| title_fullStr | Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times(机器带准备时间的三台平行机排序问题的线性时间算法) |
| title_full_unstemmed | Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times(机器带准备时间的三台平行机排序问题的线性时间算法) |
| title_short | Linear time algorithm for scheduling on three parallel machines with non-simultaneous machine available times(机器带准备时间的三台平行机排序问题的线性时间算法) |
| title_sort | linear time algorithm for scheduling on three parallel machines with non simultaneous machine available times 机器带准备时间的三台平行机排序问题的线性时间算法 |
| topic | 排序 近似比 机器准备时间 线性时间 |
| url | https://doi.org/zjup/1008-9497.2005.32.3.258-263 |
| work_keys_str_mv | AT fanjingfànjìng lineartimealgorithmforschedulingonthreeparallelmachineswithnonsimultaneousmachineavailabletimesjīqìdàizhǔnbèishíjiāndesāntáipíngxíngjīpáixùwèntídexiànxìngshíjiānsuànfǎ AT yangqifanyángqǐfān lineartimealgorithmforschedulingonthreeparallelmachineswithnonsimultaneousmachineavailabletimesjīqìdàizhǔnbèishíjiāndesāntáipíngxíngjīpáixùwèntídexiànxìngshíjiānsuànfǎ |