New Hybrid Optimization Algorithms for Machine Scheduling Problems

Dynamic programming, branch-and-bound, and constraint programming are the standard solution principles for finding optimal solutions to machine scheduling problems. We propose a new hybrid optimization framework that integrates all three methodologies. The hybrid framework leads to powerful solution procedures. We demonstrate our approach through the optimal solution of the single-machine total weighted completion time scheduling problem subject to release dates, which is known to be strongly NP-hard. Extensive computational experiments indicate that new hybrid algorithms use orders of magnitude less storage than dynamic programming, and yet can still reap the full benefit of the dynamic programming property inherent to the problem. We are able to solve to optimality all 1900 instances with up to 200 jobs. This more than doubles the size of problems that can be solved optimally by the previous best algorithm running on the latest computing hardware.     

Minimizing total weighted completion time under makespan constraint for two-agent scheduling with job-dependent aging effects

In this paper, we consider a two-agent single-machine scheduling problem with linear position-based aging effects and job-dependent aging ratios. The objective is to minimize the total weighted completion time of all jobs for two agents, where the makespan for one agent is constrained under an upper bound. After showing that this problem is at least NP-hard, we develop two solution algorithms: First, we devise a branch-and-bound algorithm to find an optimal solution through the establishment of several dominance and feasibility properties, and a lower bound. Second, we propose efficient simulated annealing algorithms, using three different methods to generate an initial solution. Through a numerical experiment, we demonstrate that the suggested algorithms can be applied to efficiently find near-optimal solutions within a reasonable amount of CPU time. In particular, we show that the initial solution method (arranging the jobs for one agent in non-increasing order of aging ratio, and scheduling the jobs for the other in the weighted shortest normal processing time order) is superior to others. Moreover, through scalability testing, we verify its consistent and relatively outstanding performance for larger systems with many processing jobs.     

Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times

In this article, we consider a single-machine scheduling problem with one unavailability period, with the aim of minimizing the weighted sum of the completion times. We propose three exact methods for solving such a problem: a branch-and-bound method based on new properties and lower bounds, a mixed integer programming model, and a dynamic programming method. These methods were coded and tested on randomly generated instances, and their performances were analyzed. Our numerical experiments show that the branch-and-bound method and the dynamic programming method are complementary. Using these approaches, we are able to solve problems with up to 3000 jobs within a reasonable computation time.     

A single-machine bi-criterion learning scheduling problem with release times

The learning effect in scheduling has received considerable attention recently. However, most researchers consider a single criterion with the assumption that jobs are all ready to be processed. The research of bi-criterion problems with learning effect is relatively limited. This paper studies a single-machine learning effect scheduling problem with release times where the objective is to minimize the sum of makespan and total completion time. First, we develop a branch-and-bound algorithm incorporating with several dominance properties and a lower bound to derive the optimal solution. Secondly, we propose a genetic algorithm to obtain near-optimal solutions. Finally, a computational experiment is conducted to evaluate the performance of the branch-and-bound and the genetic algorithms.     

Notes on “some single-machine scheduling problems with general position-dependent and time-dependent learning effects”

This paper provides a continuation of the idea presented by Yin et al. [Yin et al., Some scheduling problems with general position-dependent and time-dependent learning effects, Inform. Sci. 179 (2009) 2416-2425]. For each of the following three objectives, total weighted completion time, maximum lateness and discounted total weighted completion time, this paper presents an approximation algorithm which is based on the optimal algorithm for the corresponding single-machine scheduling problem and analyzes its worst-case bound. It shows that the single-machine scheduling problems under the proposed model can be solved in polynomial time if the objective is to minimize the total lateness or minimize the sum of earliness penalties. It also shows that the problems of minimizing the total tardiness, discounted total weighted completion time and total weighted earliness penalty are polynomially solvable under some agreeable conditions on the problem parameters.     

The total completion time open shop scheduling problem with a given sequence of jobs on one machine

This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense, however it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.Scope and purposeShop scheduling problems, widely used in the modeling of industrial production processes, are receiving an increasing amount of attention from researchers. To model practical production processes more closely, additional processing restrictions can be introduced, e.g., the resource constraints, the no-wait in process requirement, the precedence constraints, etc. This paper considers the total completion time open shop scheduling problem with a given sequence of jobs on one machine. This model belongs to a new class of shop scheduling problems under machine-dependent precedence constraints. This problem is NP-hard in the strong sense. A heuristic is proposed to efficiently solve large-scaled problems and a branch-and-bound algorithm is presented to optimally solve small-scaled problems. Computational experience is also reported.     

A new Lagrangian Relaxation Algorithm for scheduling dissimilar parallel machines with release dates

In this article we investigate the parallel machine scheduling problem with job release dates, focusing on the case that machines are dissimilar with each other. The goal of scheduling is to find an assignment and sequence for a set of jobs so that the total weighted completion time is minimised. This type of production environment is frequently encountered in process industry, such as chemical and steel industries, where the scheduling of jobs with different purposes is an important goal. This article formulates the problem as an integer linear programming model. Because of the dissimilarity of machines, the ordinary job-based decomposition method is no longer applicable, a novel machine-based Lagrangian relaxation algorithm is therefore proposed. Penalty terms associated with violations of coupling constraints are introduced to the objective function by Lagrangian multipliers, which are updated using subgradient optimisation method. For each machine-level subproblem after decomposition, a forward dynamic programming algorithm is designed together with the weighted shortest processing time rule to provide an optimal solution. A heuristics is developed to obtain a feasible schedule from the solution of subproblems to provide an upper bound. Numerical results show that the new approach is computationally effective to handle the addressed problem and provide high quality schedules.     

连铸-轧制混流生产模式下轧批调度问题的分支-定价算法

研究了连铸——轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯（热钢锭）缓冷（等待）导致的热能损失和连轧机架切换带来的产能损失为目标,建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解,提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题,采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界,最后以列生成算法作为定界机制嵌入分支——定界框架中形成分支——定价算法,执行分支搜索过程以获得整数最优解.本文还从影响分支——定价算法性能的要素出发提出改进策略.针对主问题,提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题,在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间,加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验,结果显示所提出改进策略能够突破求解能力的限制,使分支——定价算法在可接受计算时间内求得工业规模问题的最优解.     

Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times

This paper considers a single-machine problem with the sum-of-processing time based learning effect and release times. The objective is to minimize the total weighted completion times. First, a branch-and-bound algorithm incorporating with several dominance properties and two lower bounds are developed for the optimal solution. Then a genetic heuristic-based algorithm is proposed for a near-optimal solution. Finally, a computational experiment is conducted to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 15 jobs, and the average error percentage of the genetic heuristic algorithm is less than 0.105%.     

可重入混合流水车间调度的拉格朗日松弛算法

为了有效提升多重入车间的生产效率,考虑了实际生产中检查和修复过程对于逐层制造的可重入生产系统的重要性,提出了基于拉格朗日松弛算法的可重入混合流水车间的调度方法.首先进行了问题域的描述,并在此基础上以最小化加权完成时间为调度目标,建立数学规划模型.针对该调度问题提出了基于松弛机器能力约束的拉格朗日松弛算法,使松弛问题分解成工件级子问题,并使用动态规划方法建立递归公式,求解工件级子问题.随后,使用次梯度算法求解拉格朗日对偶问题.最后,对各种不同问题规模进行了仿真实验,结果表明,所提出的调度算法能够在合理的时间内获得满意的近优解.     

An exact algorithm for single-machine scheduling without machine idle time

This study proposes an exact algorithm for the general single-machine scheduling problem without machine idle time to minimize the total job completion cost. Our algorithm is based on the Successive Sublimation Dynamic Programming (SSDP) method. Its major drawback is heavy memory usage to store dynamic programming states, although unnecessary states are eliminated in the course of the algorithm. To reduce both memory usage and computational efforts, several improvements to the previous algorithm based on the SSDP method are proposed. Numerical experiments show that our algorithm can optimally solve 300 jobs instances of the total weighted tardiness problem and the total weighted earliness-tardiness problem, and that it outperforms the previous algorithms specialized for these problems.     

Two-agent singe-machine scheduling with release times to minimize the total weighted completion time

In many management situations multiple agents pursuing different objectives compete on the usage of common processing resources. In this paper we study a two-agent single-machine scheduling problem with release times where the objective is to minimize the total weighted completion time of the jobs of one agent with the constraint that the maximum lateness of the jobs of the other agent does not exceed a given limit. We propose a branch-and-bound algorithm to solve the problem, and a primary and a secondary simulated annealing algorithm to find near-optimal solutions. We conduct computational experiments to test the effectiveness of the algorithms. The computational results show that the branch-and-bound algorithm can solve most of the problem instances with up to 24 jobs in a reasonable amount of time and the primary simulated annealing algorithm performs well with an average percentage error of less than 0.5% for all the tested cases.     

基于预防维护的单机调度问题

在两种维护约束下,研究完工时间之和最小化的单机调度问题.第1种维护约束是,固定周期预防维护;第2种维护约束是,机器工作期间可连续加工的最大工件个数受限.对于这种带有约束的调度问题,根据问题的规模,采用4种方法进行求解.针对小规模问题,建立一个二值整数规划模型,并根据最优解的特性制定剪枝规则,进而给出分支定界算法.针对中...     

A tabu method for a two-agent single-machine scheduling with deterioration jobs

In recent 10 years, the multi-agent idea applied in scheduling issues has received continuing attention. However, the study of the multi-agent scheduling with deteriorating jobs is relatively limited. In light of this, this paper deliberates upon a two-agent single-machine scheduling problem with deteriorating jobs. Taking the proposed model, the actual processing time of a job from both the first agent and the second agent is modeled as a linearly increasing function of its starting time. The goal of this paper is to minimize the total weighted number of tardy jobs of the first agent subject to the condition that the maximum lateness of the second agent is allowed to have an upper bound. The complexity of the model concerned in the paper is claimed as an NP-hard one. Following that, several dominance rules and a lower bound are proposed to be applied in a branch-and-bound algorithm for the optimal solution, and a tabu algorithm is applied to find near-optimal solutions for the problem. The simulation results obtained from all the proposed algorithms are also reported.     

A global constraint for total weighted completion time for unary resources

We introduce a novel global constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the constraint, we propose an O(n ⁴) algorithm which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed global constraint significantly improves the performance of constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. We then apply the constraint to the multi-machine job shop scheduling problem with total weighted completion time. Our experiments show an order of magnitude reduction in search effort over the standard weighted-sum constraint and demonstrate that the way in which the job weights are associated with activities is important for performance.     

Tabu search for a class of single-machine scheduling problems

In this paper we develop a tabu search-based solution procedure designed specifically for a certain class of single-machine scheduling problems with a non-regular performance measure. The performance of the developed algorithm is tested for solving the variance minimization problem. Problems from the literature are used to test the performance of the algorithm. This algorithm can be used for solving other problems such as minimizing completion time deviation from a common due date.Scope and purposeScheduling problems with non-regular performance measures has gained a great importance in modern manufacturing systems. These problems are found to be hard to solve and analyze. The purpose of this paper is to present a tabu search approach for solving a certain class of single-machine scheduling problems with non-regular performance measure. Minimizing the variance of completion times and the total deviation from a common due date are two examples of such problems. The proposed approach is found to perform better than the simulated annealing approach for the variance minimization problem.     

Single machine scheduling problems with exponentially time-dependent learning effects

In this paper, we introduce a single-machine scheduling problem with an exponentially time-dependent learning effect. The processing time of a job is assumed to be an exponential function of the total normal processing time of jobs already processed before it. For such a scheduling problem, we first provide the upper bound for the maximum lateness and for the total weighted completion time. Next, we show that problems with the following criteria: makespan, the total completion time, the total weighted completion time, the total earliness/tardiness penalties and the maximum lateness under some agreeable conditions, are polynomially solvable.     

A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents

This paper addresses a two-agent scheduling problem on a single machine where the objective is to minimize the total weighted earliness cost of all jobs, while keeping the earliness cost of one agent below or at a fixed level Q. A mixed-integer programming (MIP) model is first formulated to find the optimal solution which is useful for small-size problem instances. To solve medium- to large-size problem instances, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is then provided to derive the optimal solution. A simulated annealing heuristic algorithm incorporating with a heuristic procedure is developed to derive the near-optimal solutions for the problem. A computational experiment is also conducted to evaluate the performance of the proposed algorithms.     

An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

This study proposes an exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. The algorithm is an extension of the authors' previous algorithm for the single-machine scheduling problem without setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In the first stage of the algorithm, the conjugate subgradient algorithm or the column generation algorithm is applied to a Lagrangian relaxation of the original problem to adjust multipliers. Then, in the second stage, constraints are successively added to the relaxation until the gap between lower and upper bounds becomes zero. The relaxation is solved by dynamic programming and unnecessary dynamic programming states are eliminated to suppress the increase of computation time and memory space. In this study a branching scheme is integrated into the algorithm to manage to solve hard instances. The proposed algorithm is applied to benchmark instances in the literature and almost all of them are optimally solved.     

Minimizing total completion time on a single machine with a flexible maintenance activity

A problem of jointly scheduling multiple jobs and a single maintenance activity on a single machine with the objective of minimizing total completion time is considered in this paper. It is assumed that the machine should be stopped for maintenance which takes a constant duration within a predefined period. The problem is generalized from the one with a fixed maintenance in that it relaxes the starting time of the maintenance from a fixed time point to a predefined period. Both resumable and nonresumable cases are studied. First, three properties of an optimal solution to each of the two cases are identified. Then it is shown that the proposed shortest processing time (SPT) algorithm is optimal for the resumable case. As for the nonresumable case, the conditions under which the SPT algorithm is optimal are also specified. Furthermore, it is shown that relaxing the starting time of the maintenance cannot improve the relative error bound of the SPT algorithm. The focus of the paper is presented afterwards, which is to develop a dynamic programming algorithm and a branch-and-bound algorithm to generate an optimal solution for this case. Experimental results show that these algorithms are effective and complementary in dealing with different instances of the problem.