Bicriterion Single Machine Scheduling with Resource Dependent Processing Times
Bicriterion Single Machine Scheduling with Resource Dependent Processing Times
复制标题
DOI：
10.1137/s1052623495288192
复制
发表时间：
1998-02
期刊：
影响因子：
--
通讯作者：
T. Cheng;A. Janiak;M. Kovalyov
中科院分区：
文献类型：
--
作者：
T. Cheng;A. Janiak;M. Kovalyov
研究了单机上工件排序的双约束问题。每个工件的加工时间是分配给该工件的公共离散资源量的线性递减函数。解决方案由作业序列和资源分配指定。解决方案的质量由两个标准F1和F2衡量。第一个标准是最大或总（加权）资源消耗，第二个标准是一个定期调度标准，取决于作业完成时间。这两个标准都必须最小化。一般计划的建设的Pareto集和Pareto集$\emp $-近似。本文研究了F_1和F_2在F_2\leK $下最小化F_1和在F_1\leK $下最小化F_2问题的计算复杂性，其中K是任意数。算法解决这些问题，并为建设的Pareto集和Pareto集$\endash $-近似相应的bicriminal问题。
A bicriterion problem of scheduling jobs on a single machine is studied. The processing time of each job is a linear decreasing function of the amount of a common discrete resource allocated to the job. A solution is specified by a sequence of the jobs and a resource allocation. The quality of a solution is measured by two criteria, F1 and F2. The first criterion is the maximal or total (weighted) resource consumption, and the second criterion is a regular scheduling criterion depending on the job completion times. Both criteria have to be minimized. General schemes for the construction of the Pareto set and the Pareto set $\epsilon$-approximation are presented. Computational complexities of problems to minimize F1 subject to F_2\le K$ and to minimize F2 subject to $F_1\le K$, where K is any number, are studied for various functions F1 and F2. Algorithms for solving these problems and for the construction of the Pareto set and the Pareto set $\epsilon$-approximation for the corresponding bicriterion problems are presented.