Scheduling with Time-Dependent Processing Times 2015
Scheduling with Time-Dependent Processing Times 2015
复制标题
DOI：
10.1155/2015/367585
复制
发表时间：
2014-03
影响因子：
--
通讯作者：
Yunqiang Yin;T. Cheng;Chin-Chia Wu
中科院分区：
文献类型：
--
作者：
Yunqiang Yin;T. Cheng;Chin-Chia Wu
加工时间依赖于时间的调度问题涉及工件加工时间随环境参数变化的调度问题。时间相关调度问题的研究是调度领域的一个新的研究领域。它揭示了许多经典调度理论中所没有的新性质，并为算法设计和NP难证明提供了新的方法论途径。由于其理论上的挑战性和实际应用价值，时间相关的调度问题已经引起了大量文献的关注。我们在本期中发表了许多关于该主题的最新研究，涵盖单机、流水车间和并行设置。对于涉及在单个机器上学习和/或恶化作业的研究，X。Zhang和Q.在成组技术和加工时间依赖于位置的假设下，研究了工件准备时间的单机排序问题。他们的目标是寻找最优的组序列和最优的工件序列，以最小化最大完工时间。P. Ji和L.考虑了同时具有一般位置依赖学习效应和恶化工件单机成组排序问题。在假设组建立时间是资源消耗量的正的严格递减的连续函数的条件下，证明了在总资源消耗不超过给定极限的约束下，最小化最大完工时间问题是多项式可解的，在总资源消耗不超过给定极限的约束下，最小化最大完工时间问题也是多项式可解的. J. - G. Kim等人考虑了以最小化具有不同到期日的订单的总拖期为目标的分批订单分配问题。结果表明，对于加工时间为非负时变的单机总拖期调度问题，通过寻找最优序列，可以得到最优解.假设所有工件的实际加工时间服从基于加工时间和的老化效应，DG Kim和JY Choi考虑了一个两代理单机调度问题，该问题在禁止第二个代理有延误工件的约束下，使第一个代理的加权总延误最小. S.- C. Liu等人研究了一个单机问题，该问题具有基于加工时间和的学习和准备时间，以最小化最大完工时间。为了解决该问题，他们分别建立了分支定界算法和启发式算法来寻找最优解和近似最优解。T. Wang）和雅江翠雀花（D. Xu考虑了单机上具有工作负荷相关强制维修的最大延误最小化排序问题.证明了该问题是NP-难的，并给出了一个近似算法。Li和H. Tian研究了单机调度问题的一个新的变体，考虑了顺序相关的安装成本和下游生产线的需求。他们将其表述为混合整数线性规划模型，并提出了一种改进的粒子群优化算法来求解。Qi等人研究了一个单机维修调度问题，其中维修的开始时间是预先给定的，但维修的持续时间取决于维修前机器的负荷。他们将其表述为一个整数规划模型，讨论了其复杂性，并提出了一个FPTAS和快速启发式算法。
Scheduling with time-dependent processing times is concerned with scheduling situations in which the job processing times vary with some situational parameters. Research on time-dependent scheduling problems has spawned a new area in the scheduling field. It has uncovered many new properties that are absent in classical scheduling theory and led to new methodological approaches to algorithmic design and NP-hardness proof. Due to its theoretical challenge and practical value, scheduling with time-dependent processing times has attracted a considerable amount of research attention in the literature. We publish in this issue a number of state-of-the-art studies on the topic that span the singlemachine, flow shop, and parallel settings. For research involving learning and/or deteriorating jobs on a single machine, X. Zhang and Q. Xie consider single-machine scheduling with job ready times under the assumptions of group technology and position-dependent processing times. Their objective is to find the optimal group sequence and the optimal job sequence to minimize the makespan. P. Ji and L. Li consider single-machine group scheduling with general position-dependent learning effects and deteriorating jobs simultaneously. Under the assumption that the group setup time is a positive strictly decreasing continuous function of the amount of consumed resource, they show that the makespan minimization problem is polynomially solvable under the constraint that the total resource consumption does not exceed a given limit, and the total resource consumption minimization problem is also polynomially solvable under the constraint that the makespan does not exceed a given limit. J.-G. Kim et al. consider the lotorder assignment problem with the objective of minimizing the total tardiness of the orders with distinct due dates. They show that the proposed problem can be solved optimally by finding an optimal sequence for the single-machine total tardiness scheduling problem with nonnegative time-dependent processing times. Assuming that the actual processing times of all the jobs are subject to a sum-of-processing-timesbased aging effect, DG Kim and JY Choi consider a twoagent single-machine scheduling problem that minimizes the total weighted tardiness of one agent under the restriction that the second agent is prohibited from having tardy jobs. S.-C. Liu et al. investigate a single-machine problem with sum-of-processing-times-based learning and ready times to minimize the makespan. To solve the problem, they build a branch-and-bound algorithm and a heuristic algorithm to find the optimal solution and near-optimal solution, respectively. T. Wang and D. Xu consider a maximum lateness minimization scheduling problem on a single machine with a mandatory maintenance whose duration is workload dependent. They show that the problem is NP-hard and propose an approximation algorithm for it. K. Li and H. Tian investigate a new variant of the single-machine scheduling problem by considering sequence-dependent setup costs and demands of downstream production lines. They formulate it as a mixed integer linear programming model and propose an improved particle swarm optimization to solve it. Y. Qi et al. investigate a scheduling problem on a single machine with a maintenance, in which the starting time of the maintenance is given in advance but its duration depends on the load of the machine before the maintenance. They formulate it as an integer programming model, discuss the complexity, and propose an FPTAS and fast heuristic algorithms for the problem.