In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. W...In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O（n^2） time algorithm for the special case that all stocking costs of jobs in unit time are 1.展开更多
Chinese animated movie Ne Zha 2 breaks box office records 中国动画电影《哪吒2》创下票房新纪录The Chinese animated movie Ne Zha 2 has become very popular since its release1 on January 29,2025.It has broken many box off...Chinese animated movie Ne Zha 2 breaks box office records 中国动画电影《哪吒2》创下票房新纪录The Chinese animated movie Ne Zha 2 has become very popular since its release1 on January 29,2025.It has broken many box office records in China and other countries.展开更多
This paper considers the uniform parallel machine scheduling problem with unequal release dates and delivery times to minimize the maximum completion time.For this NP-hard problem,the largest sum of release date,proce...This paper considers the uniform parallel machine scheduling problem with unequal release dates and delivery times to minimize the maximum completion time.For this NP-hard problem,the largest sum of release date,processing time and delivery time first rule is designed to determine a certain machine for each job,and the largest difference between delivery time and release date first rule is designed to sequence the jobs scheduled on the same machine,and then a novel algorithm for the scheduling problem is built.To evaluate the performance of the proposed algorithm,a lower bound for the problem is proposed.The accuracy of the proposed algorithm is tested based on the data with problem size varying from 200 jobs to 600 jobs.The computational results indicate that the average relative error between the proposed algorithm and the lower bound is only 0.667%,therefore the solutions obtained by the proposed algorithm are very accurate.展开更多
This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph-<span style="font-family:;" "=""> </span&...This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph-<span style="font-family:;" "=""> </span><span style="font-family:Verdana;">based and sequence-based, of the well-known scheduling problem<img src="Edit_41010f25-7ca5-482c-89be-790fad4616e1.png" alt="" /></span><span style="font-family:Verdana;text-align:justify;">. Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.</span> <div> <span style="font-family:Verdana;text-align:justify;"><br /> </span> </div>展开更多
We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern,respectively,to minimize the total weighted late work and the weighted number of tardy jobs,respectively...We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern,respectively,to minimize the total weighted late work and the weighted number of tardy jobs,respectively,where each job has a release date and a due date.According to the different combinations of the two scheduling patterns and the two scheduling criteria,six scheduling problems(including two Pareto-scheduling problems)are studied in this paper.We show that by modifying the release dates and the due dates,the six problems can be reduced to their corresponding scheduling problems without maintenance intervals in quasi-linear time.As a consequence,complexity results of our problems can be directly obtained from the known results in the literature.In particular,for the problem under resumable pattern to minimize the total weighted late work with all the jobs being released at time O,an O(mn^(2)P)-time algorithm was presented in the literature,where m is the number of maintenance intervals,n is the number of jobs,and P is the total processing time of the jobs;and our research shows that the same problem is solvable in O(n^(2)p+m log m)time,improving this known result.展开更多
文摘In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O（n^2） time algorithm for the special case that all stocking costs of jobs in unit time are 1.
文摘Chinese animated movie Ne Zha 2 breaks box office records 中国动画电影《哪吒2》创下票房新纪录The Chinese animated movie Ne Zha 2 has become very popular since its release1 on January 29,2025.It has broken many box office records in China and other countries.
基金supported by the National Natural Science Foundation of China (7087103290924021+2 种基金70971035)the National High Technology Research and Development Program of China (863 Program) (2008AA042901)Anhui Provincial Natural Science Foundation (11040606Q27)
文摘This paper considers the uniform parallel machine scheduling problem with unequal release dates and delivery times to minimize the maximum completion time.For this NP-hard problem,the largest sum of release date,processing time and delivery time first rule is designed to determine a certain machine for each job,and the largest difference between delivery time and release date first rule is designed to sequence the jobs scheduled on the same machine,and then a novel algorithm for the scheduling problem is built.To evaluate the performance of the proposed algorithm,a lower bound for the problem is proposed.The accuracy of the proposed algorithm is tested based on the data with problem size varying from 200 jobs to 600 jobs.The computational results indicate that the average relative error between the proposed algorithm and the lower bound is only 0.667%,therefore the solutions obtained by the proposed algorithm are very accurate.
文摘This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph-<span style="font-family:;" "=""> </span><span style="font-family:Verdana;">based and sequence-based, of the well-known scheduling problem<img src="Edit_41010f25-7ca5-482c-89be-790fad4616e1.png" alt="" /></span><span style="font-family:Verdana;text-align:justify;">. Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.</span> <div> <span style="font-family:Verdana;text-align:justify;"><br /> </span> </div>
基金supported by the National Natural Science Foundation of China(Nos.12071442 and 12201186).
文摘We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern,respectively,to minimize the total weighted late work and the weighted number of tardy jobs,respectively,where each job has a release date and a due date.According to the different combinations of the two scheduling patterns and the two scheduling criteria,six scheduling problems(including two Pareto-scheduling problems)are studied in this paper.We show that by modifying the release dates and the due dates,the six problems can be reduced to their corresponding scheduling problems without maintenance intervals in quasi-linear time.As a consequence,complexity results of our problems can be directly obtained from the known results in the literature.In particular,for the problem under resumable pattern to minimize the total weighted late work with all the jobs being released at time O,an O(mn^(2)P)-time algorithm was presented in the literature,where m is the number of maintenance intervals,n is the number of jobs,and P is the total processing time of the jobs;and our research shows that the same problem is solvable in O(n^(2)p+m log m)time,improving this known result.
