
-
Previous Article
Collection decisions and coordination in a closed-loop supply chain under recovery price and service competition
- JIMO Home
- This Issue
-
Next Article
Performance evaluation of the Chinese high-tech industry: A two-stage DEA approach with feedback and shared resource
Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.
Readers can access Online First articles via the “Online First” tab for the selected journal.
A best possible algorithm for an online scheduling problem with position-based learning effect
1. | School of Management Engineering, , Qingdao University of Technology, Qingdao 266525, China, University Research Center for Smart City Construction and Management of Shandong Province, Qingdao 266525, China |
2. | Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, China |
In this paper, we focus on an online scheduling problem with position-based learning effect on a single machine, where the jobs are released online over time and preemption is not allowed. The information about each job $ J_j $, including the basic processing time $ p_j $ and the release time $ r_j $, is only available when it arrives. The actual processing time $ p_j' $ of each job $ J_j $ is defined as a function related to its position $ r $, i.e., $ p_j' = p_j(\alpha-r\beta) $, where $ \alpha $ and $ \beta $ are both nonnegative learning index. Our goal is to minimize the sum of completion time of all jobs. For this problem, we design a deterministic polynomial time online algorithm Delayed Shortest Basic Processing Time (DSBPT). In order to facilitate the understanding of the online algorithm, we present a relatively common and simple example to describe the execution process of the algorithm, and then by competitive analysis, we show that online algorithm DSBPT is a best possible online algorithm with a competitive ratio of 2.
References:
[1] |
W. Allihaibi, M. Cholette, M. Masoud, J. Burke and A. Karim,
A heuristic approach for scheduling patient treatment in an emergency department based on bed blocking, International Journal of Industrial Engineering Computations, 11 (2020), 565-584.
doi: 10.5267/j.ijiec.2020.4.005. |
[2] |
D. Y. Bai, H. Y. Xue, L. Wang, C. C. Wu, W. C. Lin and D. H. Abdulkadir, Effective algorithms for single-machine learning-effect scheduling to minimize completion-time-based criteria with release dates, Expert Systems With Applications, 156 (2020), 113445. |
[3] |
L. Bai, D. Yang, X. Wang, L. Tong, X. Zhu, N. Zhong, C. Bai and C. A. Powell,
Chinese experts consensus on the Internet of Things-aided diagnosis and treatment of coronavirus disease 2019 (COVID-19), Clinical eHealth, 3 (2020), 7-15.
doi: 10.1016/j.ceh.2020.03.001. |
[4] |
D. Biskup,
Single-machine scheduling with learning considerations, European J. Oper. Res., 115 (1999), 173-178.
doi: 10.1016/S0377-2217(98)00246-X. |
[5] |
D. Biskup,
A state-of-the-art review on scheduling with learning effects, European J. Oper. Res., 188 (2008), 315-329.
doi: 10.1016/j.ejor.2007.05.040. |
[6] |
T. C. E. Cheng, S. R. Cheng, W. H. Wu, P. H. Hsu and C. C. Wu,
A two-agent single machine scheduling problem with truncated sum-of-processing-times-based learning considerations, Computers and Industrial Engineering, 60 (2011), 534-541.
|
[7] |
M. B. Cheng, S. X. Xiao and G. Liu,
Single-machine rescheduling problems with learning effect under disruptions, J. Ind. Manag. Optim., 14 (2018), 967-980.
doi: 10.3934/jimo.2017085. |
[8] |
J. A. Hoogeveen and A. P. A. Vestjens, Optimal on-line algorithms for single-machine scheduling, Lecture Notes in Comput. Sci., Springer, Berlin, (1996), 404–414. |
[9] |
Z. Y. Jiang, F. F. Chen and X. D. Zhang,
Single-machine scheduling with times-based and job-dependent learning effect, Journal of the Operational Research Society, 68 (2017), 809-815.
|
[10] |
S. Jun and S. Lee,
Learning dispatching rules for single machine scheduling with dynamic arrivals based on decision trees and feature construction, International Journal of Production Research, 59 (2020), 2838-2856.
doi: 10.1080/00207543.2020.1741716. |
[11] |
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy and D. B. Shmoys,
Sequencing and scheduling algorithms and complexity, Handbooks in Operations Research and Management Science, 4 (1993), 445-522.
|
[12] |
W. C. Lee and C. C. Wu,
A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model., 33 (2009), 2159-2163.
doi: 10.1016/j.apm.2008.05.020. |
[13] |
P. H. Liu and X. W. Lu,
On-line scheduling of parallel machines to minimize total completion times, Comput. Oper. Res., 36 (2009), 2647-2652.
doi: 10.1016/j.cor.2008.11.008. |
[14] |
Y. Y. Lu, F. Teng and Z. X. Feng, Scheduling jobs with truncated exponential sum-of-logarithm-processing-times based and position-based learning effects, Asia-Pac. J. Oper. Res., 32 (2015), 1550026.
doi: 10.1142/S0217595915500268. |
[15] |
R. Ma and J. P. Tao,
An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time, J. Ind. Manag. Optim., 14 (2018), 497-510.
doi: 10.3934/jimo.2017057. |
[16] |
R. Ma and S. N. Guo,
Applying "Peeling Onion" approach for competitive analysis in online scheduling with rejection, European J. Oper. Res., 290 (2021), 57-67.
doi: 10.1016/j.ejor.2020.08.009. |
[17] |
G. Mosheiov,
Scheduling problems with a learning effect, European J. Oper. Res., 132 (2001), 687-693.
doi: 10.1016/S0377-2217(00)00175-2. |
[18] |
G. Mosheiov,
Minimizing total absolute deviation of job completion times: Extensions to position-dependent processing times and parallel identical machines, J. Oper. Res. Soc., 59 (2008), 1422-1424.
doi: 10.1057/palgrave.jors.2602480. |
[19] |
S. Mustu and T. Eren,
The single machine scheduling problem with setup times under an extension of the general learning and forgetting effects, Optim. Lett., 15 (2021), 1327-1343.
doi: 10.1007/s11590-020-01641-9. |
[20] |
J. B. Wang, M. Gao, J. J. Wang, L. Liu and H. Y. He,
Scheduling with a position-weighted learning effect and job release dates, Eng. Optim., 52 (2019), 1475-1493.
doi: 10.1080/0305215X.2019.1664498. |
[21] |
J.-B. Wang, L. H. Sun and L. Y. Sun,
Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect, Appl. Math. Model., 34 (2010), 2813-2819.
doi: 10.1016/j.apm.2009.12.015. |
[22] |
J.-B. Wang and J.-J. Wang,
Single machine scheduling with sum-of-logarithm processing-times based and position based learning effects, Optim. Lett., 8 (2014), 971-982.
doi: 10.1007/s11590-012-0494-4. |
[23] |
J. B. Wang and Z. Q. Xia,
Flow-shop scheduling with a learning effect, J. Oper. Res. Soc., 56 (2005), 1325-1330.
doi: 10.1057/palgrave.jors.2601856. |
[24] |
T. P. Wright,
Factors affecting the cost of airplanes, J. Aer. Sci., 3 (1936), 122-128.
doi: 10.2514/8.155. |
[25] |
S.-J. Yang and D.-L. Yang,
Note on "A note on single-machine group scheduling problems with position-based learning effect", Appl. Math. Model., 34 (2010), 4306-4308.
doi: 10.1016/j.apm.2010.03.037. |
[26] |
A. E. Zade, S. S. Haghighi and M. Soltani, Reinforcement learning for optimal scheduling of Glioblastoma treatment with Temozolomide, Computer Methods and Programs in Biomedicine, 193 (2020), 105443. |
show all references
References:
[1] |
W. Allihaibi, M. Cholette, M. Masoud, J. Burke and A. Karim,
A heuristic approach for scheduling patient treatment in an emergency department based on bed blocking, International Journal of Industrial Engineering Computations, 11 (2020), 565-584.
doi: 10.5267/j.ijiec.2020.4.005. |
[2] |
D. Y. Bai, H. Y. Xue, L. Wang, C. C. Wu, W. C. Lin and D. H. Abdulkadir, Effective algorithms for single-machine learning-effect scheduling to minimize completion-time-based criteria with release dates, Expert Systems With Applications, 156 (2020), 113445. |
[3] |
L. Bai, D. Yang, X. Wang, L. Tong, X. Zhu, N. Zhong, C. Bai and C. A. Powell,
Chinese experts consensus on the Internet of Things-aided diagnosis and treatment of coronavirus disease 2019 (COVID-19), Clinical eHealth, 3 (2020), 7-15.
doi: 10.1016/j.ceh.2020.03.001. |
[4] |
D. Biskup,
Single-machine scheduling with learning considerations, European J. Oper. Res., 115 (1999), 173-178.
doi: 10.1016/S0377-2217(98)00246-X. |
[5] |
D. Biskup,
A state-of-the-art review on scheduling with learning effects, European J. Oper. Res., 188 (2008), 315-329.
doi: 10.1016/j.ejor.2007.05.040. |
[6] |
T. C. E. Cheng, S. R. Cheng, W. H. Wu, P. H. Hsu and C. C. Wu,
A two-agent single machine scheduling problem with truncated sum-of-processing-times-based learning considerations, Computers and Industrial Engineering, 60 (2011), 534-541.
|
[7] |
M. B. Cheng, S. X. Xiao and G. Liu,
Single-machine rescheduling problems with learning effect under disruptions, J. Ind. Manag. Optim., 14 (2018), 967-980.
doi: 10.3934/jimo.2017085. |
[8] |
J. A. Hoogeveen and A. P. A. Vestjens, Optimal on-line algorithms for single-machine scheduling, Lecture Notes in Comput. Sci., Springer, Berlin, (1996), 404–414. |
[9] |
Z. Y. Jiang, F. F. Chen and X. D. Zhang,
Single-machine scheduling with times-based and job-dependent learning effect, Journal of the Operational Research Society, 68 (2017), 809-815.
|
[10] |
S. Jun and S. Lee,
Learning dispatching rules for single machine scheduling with dynamic arrivals based on decision trees and feature construction, International Journal of Production Research, 59 (2020), 2838-2856.
doi: 10.1080/00207543.2020.1741716. |
[11] |
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy and D. B. Shmoys,
Sequencing and scheduling algorithms and complexity, Handbooks in Operations Research and Management Science, 4 (1993), 445-522.
|
[12] |
W. C. Lee and C. C. Wu,
A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model., 33 (2009), 2159-2163.
doi: 10.1016/j.apm.2008.05.020. |
[13] |
P. H. Liu and X. W. Lu,
On-line scheduling of parallel machines to minimize total completion times, Comput. Oper. Res., 36 (2009), 2647-2652.
doi: 10.1016/j.cor.2008.11.008. |
[14] |
Y. Y. Lu, F. Teng and Z. X. Feng, Scheduling jobs with truncated exponential sum-of-logarithm-processing-times based and position-based learning effects, Asia-Pac. J. Oper. Res., 32 (2015), 1550026.
doi: 10.1142/S0217595915500268. |
[15] |
R. Ma and J. P. Tao,
An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time, J. Ind. Manag. Optim., 14 (2018), 497-510.
doi: 10.3934/jimo.2017057. |
[16] |
R. Ma and S. N. Guo,
Applying "Peeling Onion" approach for competitive analysis in online scheduling with rejection, European J. Oper. Res., 290 (2021), 57-67.
doi: 10.1016/j.ejor.2020.08.009. |
[17] |
G. Mosheiov,
Scheduling problems with a learning effect, European J. Oper. Res., 132 (2001), 687-693.
doi: 10.1016/S0377-2217(00)00175-2. |
[18] |
G. Mosheiov,
Minimizing total absolute deviation of job completion times: Extensions to position-dependent processing times and parallel identical machines, J. Oper. Res. Soc., 59 (2008), 1422-1424.
doi: 10.1057/palgrave.jors.2602480. |
[19] |
S. Mustu and T. Eren,
The single machine scheduling problem with setup times under an extension of the general learning and forgetting effects, Optim. Lett., 15 (2021), 1327-1343.
doi: 10.1007/s11590-020-01641-9. |
[20] |
J. B. Wang, M. Gao, J. J. Wang, L. Liu and H. Y. He,
Scheduling with a position-weighted learning effect and job release dates, Eng. Optim., 52 (2019), 1475-1493.
doi: 10.1080/0305215X.2019.1664498. |
[21] |
J.-B. Wang, L. H. Sun and L. Y. Sun,
Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect, Appl. Math. Model., 34 (2010), 2813-2819.
doi: 10.1016/j.apm.2009.12.015. |
[22] |
J.-B. Wang and J.-J. Wang,
Single machine scheduling with sum-of-logarithm processing-times based and position based learning effects, Optim. Lett., 8 (2014), 971-982.
doi: 10.1007/s11590-012-0494-4. |
[23] |
J. B. Wang and Z. Q. Xia,
Flow-shop scheduling with a learning effect, J. Oper. Res. Soc., 56 (2005), 1325-1330.
doi: 10.1057/palgrave.jors.2601856. |
[24] |
T. P. Wright,
Factors affecting the cost of airplanes, J. Aer. Sci., 3 (1936), 122-128.
doi: 10.2514/8.155. |
[25] |
S.-J. Yang and D.-L. Yang,
Note on "A note on single-machine group scheduling problems with position-based learning effect", Appl. Math. Model., 34 (2010), 4306-4308.
doi: 10.1016/j.apm.2010.03.037. |
[26] |
A. E. Zade, S. S. Haghighi and M. Soltani, Reinforcement learning for optimal scheduling of Glioblastoma treatment with Temozolomide, Computer Methods and Programs in Biomedicine, 193 (2020), 105443. |



Notation | Meaning |
the job of index |
|
a job instance, |
|
the release time of job |
|
the basic processing time of job |
|
the actual processing time of job |
|
a feasible schedule of |
|
the starting time of job |
|
the completion time of job |
|
the contribution of job |
|
the total objective value of |
|
an off-line optimal schedule of |
|
the total objective value of |
Notation | Meaning |
the job of index |
|
a job instance, |
|
the release time of job |
|
the basic processing time of job |
|
the actual processing time of job |
|
a feasible schedule of |
|
the starting time of job |
|
the completion time of job |
|
the contribution of job |
|
the total objective value of |
|
an off-line optimal schedule of |
|
the total objective value of |
Notation | Meaning |
the number of jobs in |
|
the set of jobs of |
|
the total contribution of jobs of |
|
the total objective value of jobs of |
Notation | Meaning |
the number of jobs in |
|
the set of jobs of |
|
the total contribution of jobs of |
|
the total objective value of jobs of |
Algorithm 1 DSBPT |
At each decision time |
Algorithm 1 DSBPT |
At each decision time |
Algorithm 1: Online Algorithm DSBPT. |
1: Input: job instance 2: 3: While True do 4: update available jobs set A, 5: 6: arbitrarily select a job 7: If 8: 9: 10: 11: 12: end if 13: If 14: 15: end if 16: end while 17: return |
Algorithm 1: Online Algorithm DSBPT. |
1: Input: job instance 2: 3: While True do 4: update available jobs set A, 5: 6: arbitrarily select a job 7: If 8: 9: 10: 11: 12: end if 13: If 14: 15: end if 16: end while 17: return |
release time | 0 | 8 | 17 | 23 | 28 | 30 |
basic processing time | 8 | 6 | 12 | 10 | 4 | 8 |
release time | 0 | 8 | 17 | 23 | 28 | 30 |
basic processing time | 8 | 6 | 12 | 10 | 4 | 8 |
decision time | valid job set | selected job | sequence of finished jobs | current objective function value |
0 | None | None | 0 | |
8 | None | 0 | ||
14 | 14 | |||
17 | None | 14 | ||
20.8 | 34.8 | |||
23 | None | 34.8 | ||
28 | None | 34.8 | ||
29.2 | 64 | |||
30 | None | 64 | ||
31.4 | 95.4 | |||
34.6 | 130 | |||
37.1 | None | None | 167.1 |
decision time | valid job set | selected job | sequence of finished jobs | current objective function value |
0 | None | None | 0 | |
8 | None | 0 | ||
14 | 14 | |||
17 | None | 14 | ||
20.8 | 34.8 | |||
23 | None | 34.8 | ||
28 | None | 34.8 | ||
29.2 | 64 | |||
30 | None | 64 | ||
31.4 | 95.4 | |||
34.6 | 130 | |||
37.1 | None | None | 167.1 |
time | valid job set | selected job | sequence of finished jobs | current objective function value |
0 | None | 0 | ||
8 | 8 | |||
13.1 | None | None | 21.1 | |
17 | 21.1 | |||
23 | None | 21.1 | ||
25.4 | 46.5 | |||
28 | None | 46.5 | ||
30 | None | 46.5 | ||
30.9 | 77.4 | |||
32.5 | 109.9 | |||
34.5 | None | None | 144.4 |
time | valid job set | selected job | sequence of finished jobs | current objective function value |
0 | None | 0 | ||
8 | 8 | |||
13.1 | None | None | 21.1 | |
17 | 21.1 | |||
23 | None | 21.1 | ||
25.4 | 46.5 | |||
28 | None | 46.5 | ||
30 | None | 46.5 | ||
30.9 | 77.4 | |||
32.5 | 109.9 | |||
34.5 | None | None | 144.4 |
job processing scheduling | objective function value | |
167.1 | ||
144.4 |
job processing scheduling | objective function value | |
167.1 | ||
144.4 |
Algorithm 2 FDSBPT |
At arbitrary time |
Algorithm 2 FDSBPT |
At arbitrary time |
Algorithm 2: Online Algorithm DSBPT. |
1: Input: job instance 2: 3: While True do 4: update available jobs set A 5: 6: arbitrarily select a job 7: If 8: 9: 10: 11: 12: end if 13: 14: end while 15: return |
Algorithm 2: Online Algorithm DSBPT. |
1: Input: job instance 2: 3: While True do 4: update available jobs set A 5: 6: arbitrarily select a job 7: If 8: 9: 10: 11: 12: end if 13: 14: end while 15: return |
release time | 0 | 8 | 17 | 23 | 28 | 30 | 30 | 33 | 35 | 39 |
basic processing time | 8 | 6 | 12 | 10 | 4 | 8 | 12 | 9 | 10 | 11 |
release time | 41 | 42 | 46 | 48 | 48 | 48 | 48 | 50 | 52 | 52 |
basic processing time | 13 | 6 | 7 | 9 | 8 | 8 | 9 | 5 | 13 | 8 |
release time | 0 | 8 | 17 | 23 | 28 | 30 | 30 | 33 | 35 | 39 |
basic processing time | 8 | 6 | 12 | 10 | 4 | 8 | 12 | 9 | 10 | 11 |
release time | 41 | 42 | 46 | 48 | 48 | 48 | 48 | 50 | 52 | 52 |
basic processing time | 13 | 6 | 7 | 9 | 8 | 8 | 9 | 5 | 13 | 8 |
decision time | valid job set | selected job | current objective function value |
0 | $J_1$ | None | 0 |
8 | $J_1$ $J_2$ | $J_2$ | 0 |
14 | $J_1$ | $J_1$ | 14 |
17 | $J_3$ | None | 14 |
21.84 | $J_3$ | $J_3$ | 35.84 |
23 | $J_4$ | None | 35.84 |
28 | $J_4$ $J_5$ | None | 35.84 |
30 | $J_4$ $J_5$ $J_6$ $J_7$ | None | 35.84 |
33 | $J_4$ $J_5$ $J_6$ $J_7$ $J_8$ | None | 35.84 |
33.36 | $J_4$ $J_5$ $J_6$ $J_7$ $J_8$ | $J_5$ | 69.2 |
35 | $J_4$ $J_6$ $J_7$ $J_8$ $J_9$ | None | 69.2 |
37.12 | $J_4$ $J_6$ $J_7$ $J_8$ $J_9$ | $J_6$ | 106.32 |
39 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ | None | 106.32 |
41 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ | None | 106.32 |
42 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{12}$ | None | 106.32 |
44.48 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{12}$ | $J_{12}$ | 150.8 |
46 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ | None | 150.8 |
48 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ | None | 150.8 |
49.88 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ | $J_{13}$ | 200.68 |
50 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{18}$ | None | 200.68 |
52 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{18}$ $J_{19}$ $J_{20}$ | None | 200.68 |
56.04 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{18}$ $J_{19}$ $J_{20}$ | $J_{18}$ | 256.72 |
60.34 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{15}$ | 317.06 |
67.06 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{16}$ | 384.12 |
73.62 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{20}$ | 457.74 |
80.02 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ | $J_8$ | 537.76 |
87.04 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ | $J_{14}$ | 624.8 |
93.88 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{17}$ $J_{19}$ | $J_{17}$ | 718.68 |
100.54 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_4$ | 819.22 |
107.74 | $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_9$ | 926.96 |
114.74 | $J_7$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_{10}$ | 1041.7 |
122.22 | $J_7$ $J_{11}$ $J_{19}$ | $J_7$ | 1163.92 |
130.14 | $J_{11}$ $J_{19}$ | $J_{11}$ | 1294.06 |
138.46 | $J_{19}$ | $J_{19}$ | 1432.52 |
146.52 | None | None | 1579.04 |
decision time | valid job set | selected job | current objective function value |
0 | $J_1$ | None | 0 |
8 | $J_1$ $J_2$ | $J_2$ | 0 |
14 | $J_1$ | $J_1$ | 14 |
17 | $J_3$ | None | 14 |
21.84 | $J_3$ | $J_3$ | 35.84 |
23 | $J_4$ | None | 35.84 |
28 | $J_4$ $J_5$ | None | 35.84 |
30 | $J_4$ $J_5$ $J_6$ $J_7$ | None | 35.84 |
33 | $J_4$ $J_5$ $J_6$ $J_7$ $J_8$ | None | 35.84 |
33.36 | $J_4$ $J_5$ $J_6$ $J_7$ $J_8$ | $J_5$ | 69.2 |
35 | $J_4$ $J_6$ $J_7$ $J_8$ $J_9$ | None | 69.2 |
37.12 | $J_4$ $J_6$ $J_7$ $J_8$ $J_9$ | $J_6$ | 106.32 |
39 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ | None | 106.32 |
41 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ | None | 106.32 |
42 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{12}$ | None | 106.32 |
44.48 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{12}$ | $J_{12}$ | 150.8 |
46 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ | None | 150.8 |
48 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ | None | 150.8 |
49.88 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ | $J_{13}$ | 200.68 |
50 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{18}$ | None | 200.68 |
52 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{18}$ $J_{19}$ $J_{20}$ | None | 200.68 |
56.04 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{18}$ $J_{19}$ $J_{20}$ | $J_{18}$ | 256.72 |
60.34 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{15}$ | 317.06 |
67.06 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{16}$ | 384.12 |
73.62 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{20}$ | 457.74 |
80.02 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ | $J_8$ | 537.76 |
87.04 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ | $J_{14}$ | 624.8 |
93.88 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{17}$ $J_{19}$ | $J_{17}$ | 718.68 |
100.54 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_4$ | 819.22 |
107.74 | $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_9$ | 926.96 |
114.74 | $J_7$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_{10}$ | 1041.7 |
122.22 | $J_7$ $J_{11}$ $J_{19}$ | $J_7$ | 1163.92 |
130.14 | $J_{11}$ $J_{19}$ | $J_{11}$ | 1294.06 |
138.46 | $J_{19}$ | $J_{19}$ | 1432.52 |
146.52 | None | None | 1579.04 |
time | valid job set | selected job | current objective function value |
0 | $J_1$ | $J_1$ | 0 |
8 | $J_2$ | $J_2$ | 8 |
13.88 | None | None | 21.88 |
17 | $J_3$ | $J_3$ | 21.88 |
28.52 | $J_4$ $J_5$ | $J_5$ | 50.4 |
32.28 | $J_4$ $J_6$ $J_7$ | $J_6$ | 82.68 |
39.64 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ | $J_8$ | 122.32 |
47.74 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{12}$ $J_{13}$ | $J_{12}$ | 170.06 |
53.02 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{18}$ $J_{19}$ $J_{20}$ | $J_{18}$ | 223.08 |
57.32 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{13}$ | 280.4 |
63.2 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{15}$ | 343.6 |
69.76 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{16}$ | 413.36 |
76.16 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{20}$ | 489.52 |
82.4 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ | $J_{14}$ | 571.92 |
89.24 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{17}$ $J_{19}$ | $J_{17}$ | 661.16 |
95.9 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_4$ | 757.06 |
103.1 | $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_9$ | 860.16 |
110.1 | $J_7$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_{10}$ | 970.26 |
117.58 | $J_7$ $J_{11}$ $J_{19}$ | $J_7$ | 1087.84 |
125.5 | $J_{11}$ $J_{19}$ | $J_{11}$ | 1213.34 |
133.82 | $J_{19}$ | $J_{19}$ | 1347.16 |
141.88 | None | None | 1489.04 |
time | valid job set | selected job | current objective function value |
0 | $J_1$ | $J_1$ | 0 |
8 | $J_2$ | $J_2$ | 8 |
13.88 | None | None | 21.88 |
17 | $J_3$ | $J_3$ | 21.88 |
28.52 | $J_4$ $J_5$ | $J_5$ | 50.4 |
32.28 | $J_4$ $J_6$ $J_7$ | $J_6$ | 82.68 |
39.64 | $J_4$ $J_7$ $J_8$ $J_9$ $J_{10}$ | $J_8$ | 122.32 |
47.74 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{12}$ $J_{13}$ | $J_{12}$ | 170.06 |
53.02 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{18}$ $J_{19}$ $J_{20}$ | $J_{18}$ | 223.08 |
57.32 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{13}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{13}$ | 280.4 |
63.2 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{15}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{15}$ | 343.6 |
69.76 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{16}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{16}$ | 413.36 |
76.16 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ $J_{20}$ | $J_{20}$ | 489.52 |
82.4 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{14}$ $J_{17}$ $J_{19}$ | $J_{14}$ | 571.92 |
89.24 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{17}$ $J_{19}$ | $J_{17}$ | 661.16 |
95.9 | $J_4$ $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_4$ | 757.06 |
103.1 | $J_7$ $J_9$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_9$ | 860.16 |
110.1 | $J_7$ $J_{10}$ $J_{11}$ $J_{19}$ | $J_{10}$ | 970.26 |
117.58 | $J_7$ $J_{11}$ $J_{19}$ | $J_7$ | 1087.84 |
125.5 | $J_{11}$ $J_{19}$ | $J_{11}$ | 1213.34 |
133.82 | $J_{19}$ | $J_{19}$ | 1347.16 |
141.88 | None | None | 1489.04 |
job processing scheduling | objective function value | |
1579.04 | ||
1489.04 |
job processing scheduling | objective function value | |
1579.04 | ||
1489.04 |
[1] |
Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269 |
[2] |
Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial and Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185 |
[3] |
Mingbao Cheng, Shuxian Xiao, Guosheng Liu. Single-machine rescheduling problems with learning effect under disruptions. Journal of Industrial and Management Optimization, 2018, 14 (3) : 967-980. doi: 10.3934/jimo.2017085 |
[4] |
Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088 |
[5] |
Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial and Management Optimization, 2020, 16 (1) : 231-244. doi: 10.3934/jimo.2018148 |
[6] |
Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057 |
[7] |
Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial and Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825 |
[8] |
Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040 |
[9] |
Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial and Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058 |
[10] |
Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial and Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757 |
[11] |
Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial and Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219 |
[12] |
Aude Hofleitner, Tarek Rabbani, Mohammad Rafiee, Laurent El Ghaoui, Alex Bayen. Learning and estimation applications of an online homotopy algorithm for a generalization of the LASSO. Discrete and Continuous Dynamical Systems - S, 2014, 7 (3) : 503-523. doi: 10.3934/dcdss.2014.7.503 |
[13] |
Shuang Zhao. Resource allocation flowshop scheduling with learning effect and slack due window assignment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2817-2835. doi: 10.3934/jimo.2020096 |
[14] |
Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1329-1347. doi: 10.3934/jimo.2019005 |
[15] |
Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71 |
[16] |
Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691 |
[17] |
Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323 |
[18] |
Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071 |
[19] |
Shuen Guo, Zhichao Geng, Jinjiang Yuan. Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021192 |
[20] |
Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]