An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines

In this paper, we introduce a new concept of semi-preemptive scheduling and we show how it can be used to derive a maximum-flow-based lower bound for the P|r_j|L_max which dominates the well-known preemptive lower bound. We show that, in some cases, the proposed bound strictly dominates the preemptive one while having the same complexity.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by realloeating resources. In this paper, authors consider a machine scheduling problemwith controllable processing times. In the first part of this paper, a special case where the pro-cessing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O（n^2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case, An effective heuristic to the genera/ problem will be presented.     

Scheduling jobs with different,job-dependent earliness and tardiness penalties using the SLK method

The single machine job scheduling problem, where due dates are assigned using the SLK due date determination method, is examined assuming different penalties for the early and tardy jobs. These penalties are assumed to be job-dependent, proportional to the processing times of jobs raised to an integer, non-negative power. The objective function is the total weighted lateness. Several cases are examined and four algorithms providing the optimal sequences for these cases are presented. Examples are given and conclusions are drawn.     

Scheduling two agents with controllable processing times

We consider several two-agent scheduling problems with controllable job processing times, where agents A and B have to share either a single machine or two identical machines in parallel while processing their jobs. The processing times of the jobs of agent A are compressible at additional cost. The objective function for agent B is always the same, namely a regular function _fmax$f_{\text{max}}$. Several different objective functions are considered for agent A, including the total completion time plus compression cost, the maximum tardiness plus compression cost, the maximum lateness plus compression cost and the total compression cost subject to deadline constraints (the imprecise computation model). All problems are to minimize the objective function of agent A subject to a given upper bound on the objective function of agent B. These problems have various applications in computer systems as well as in operations management. We provide NP-hardness proofs for the more general problems and polynomial-time algorithms for several special cases of the problems.     

Comments on “A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect”

The purpose of this paper is to point out that if there are some machines that do not process any job then the mathematical programming model provided by Eren [T. Eren, A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect, Applied Mathematics and Computation 209 (2009) 186-190] may not be a valid one. A simple way to fix this problem is given. Furthermore, based on the idea of Eren’s model, a general mathematical programming model is proposed.     

A dimensionless reaction coordinate for quantifying the lateness of transition states

The Hammond‐Leffler postulate asserts that transition states of exothermic reactions are reactant‐like (early), whereas transition states of endothermic reactions are product‐like (late). Related postulates have been proposed to describe the sensitivity of activation barriers for reactions occurring on catalytic surfaces to the catalyst structure. To evaluate the validity of these postulates for different chemical reactions, a general method for classifying transition states as either early or late is needed. One can envision a dimensionless reaction coordinate that changes continuously and monotonically from 0 to 1 along a minimum energy reaction pathway. The value of the dimensionless reaction coordinate for the transition state (W_TS) classifies transition states as (a) early when W_TS < 0.5, (b) late when W_TS > 0.5, and (c) equidistant between reactants and products when W_TS = 0.5. In this article, we derive such a dimensionless reaction coordinate and illustrate its usefulness for several different chemical reactions. © 2009 Wiley Periodicals, Inc. J Comput Chem, 2010     

A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives

This paper studies the two-agent scheduling on an unbounded parallel-batching machine. In the problem, there are two agents A and B with each having their own job sets. The jobs of a common agent can be processed in a common batch. Moreover, each agent has an objective function to be minimized. The objective function of agent A is the makespan of his jobs and the objective function of agent B is maximum lateness of his jobs. Yazdani Sabouni and Jolai [M.T. Yazdani Sabouni, F. Jolai, Optimal methods for batch processing problem with makespan and maximum lateness objectives, Appl. Math. Model. 34 (2010) 314–324] presented a polynomial-time algorithm for the problem to minimize a positive combination of the two agents’ objective functions. Unfortunately, their algorithm is incorrect. We then dwell on the problem and present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.     

Stochastic scheduling to minimize expected maximum lateness

This paper is concerned with the problems in scheduling a set of jobs associated with random due dates on a single machine so as to minimize the expected maximum lateness in stochastic environment. This is a difficult problem and few efforts have been reported on its solution in the literature. In this paper, we first derive a deterministic equivalent to the expected maximum lateness and then propose a dynamic programming algorithm to obtain the optimal solutions. The procedures to compute optimal solutions are initially developed in the case of deterministic processing times, and then extended to stochastic processing times following arbitrary probability distributions. Moreover, several heuristic rules are suggested to compute near-optimal solutions, which are shown to be highly efficient and accurate by computer-based experiments.     

求解带组换装时间单机调度问题的禁忌搜索算法

以包头某钢铁线材企业生产实际调度问题为背景,研究了一类带组换装时间的单机调度问题.由于该问题是NP难的,本文提出了一类适合该问题的禁忌搜索算法.此外,本文将问题性质引入了禁忌搜索算法以进一步提高算法寻优性能,降低算法运行时间.本文提出的算法在随机问题和实际问题上均进行了测试,实验结果表明,本文提出的算法能在不到10秒的时间内获得实际问题的一个近似最优解.     

原始工件的完工时间限制下的最小化最大延误时间的重新排序

考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决.