Scheduling jobs with position-dependent processing times
Scheduling jobs with position-dependent processing times
复制标题
DOI：
10.1057/palgrave.jors.2601689
复制
发表时间：
2004-03-01
影响因子：
3.6
通讯作者：
Janiak, A
中科院分区：
文献类型：
--
作者：
Bachman, A;Janiak, A
本文致力于一些单机调度问题，其中作业处理时间由依赖于它们在序列中的位置的函数定义。假设每个作业都可以在其就绪时间进行处理。我们证明了以下优化标准的问题特殊情况的一些属性：完工时间、总完成时间和总加权完成时间。我们证明了两种不同的作业处理时间模型的完工时间最小化问题的强 NP 难度。这些缩减是根据著名的三分区问题完成的。为了解决完工时间最小化问题，我们建议使用最早就绪日期算法，计算最坏情况的比率。我们还证明了作业准备时间的完工时间最小化问题等价于最大延迟最小化问题。
The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem.