排序方式: 共有3条查询结果,搜索用时 15 毫秒
1
1.
Byung-Cheon Choi Joseph Y.-T. Leung Michael L. Pinedo 《Journal of Combinatorial Optimization》2011,22(4):797-818
We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing
requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is
equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine.
In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number
of machines is fixed. 相似文献
2.
We consider a two-stage flexible flow shop problem with a single machine at one stage and m identical machines at the other stage, where the processing times of each job at both stages are identical. The objective is to minimize the makespan. We describe some optimality conditions and show that the problem is NP-hard when m is fixed. Finally, we present an approximation algorithm that has a worst-case performance ratio of $\frac{5}{4}$ for m=2 and $\frac{\sqrt{1+m^{2}}+1+m}{2m}$ for m≥3. 相似文献
3.
We consider a single-machine scheduling problem such that the due dates are assigned to each job depending on its order, and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total penalty for the earliness and tardiness of each job. The early penalty proportionally increases according to the earliness amount, while the tardy penalty increases according to the step function. We show that the problem is strongly NP-hard, and furthermore, polynomially solvable if the two types of processing times exist.
相似文献
1