排序方式: 共有4条查询结果,搜索用时 0 毫秒
1
1.
A hybrid two-stage flowshop scheduling problem was considered which involves m identical parallel machines at Stage 1 and a burn-in processor M at Stage 2, and the makespan was taken as the minimization objective. This scheduling problem is NP-hard in general. We divide it into eight subcases. Except for the following two subcases: (1) b≥ an, max{m, B} 〈 n; (2) a1 ≤ b ≤ an, m ≤ B 〈 n, for all other subcases, their NP-hardness was proved or pointed out, corresponding approximation algorithms were conducted and their worst-case performances were estimated. In all these approximation algorithms, the Multifit and PTAS algorithms were respectively used, as the jobs were scheduled in m identical parallel machines. 相似文献
2.
In this paper, a single-machine scheduling model with a given common due date and simple linear processing times was considered. The objective is the total weighted tardiness penalty and earliness award. Some polynomial time solvable cases for this problem are given. A dynamic programming algorithm was provided and a branch and bound algorithm for general case of the problem was provided based on a rapid method for estimating the lower bound. 相似文献
3.
A hybrid two-stage flowshop scheduling problem was considered which involves m identical parallel machines at Stage 1 and a burn-in processor M at Stage 2,and the makespan was taken as the minimization objective.This scheduling prob- lem is NP-hard in general.We divide it into eight subcases.Except for the following two subcases:(1)b≥a_n,max{m,B}<n; (2)a_1≤b≤a_n,m≤B≤n,for all other subcases,their NP-hardness was proved or pointed out,corresponding approxima- tion algorithms were conducted and their worst-case performances were estimated.In aU these approximation algorithms,the Multifit and PTAS algorithms were respectively used,as the jobs were scheduled in m identical parallel machines. 相似文献
4.
与开工时间有关的加工时间的超前有奖迟后受罚的排序问题的动态规划算法 总被引:1,自引:0,他引:1
In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided. 相似文献
1