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.     

带有线性恶化工件和释放时间的两个代理单机调度问题

研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题. 所有工件在一台机器上加工, 每个代理有各自依赖于自己工件的优化目标. 针对工件释放时间相同与不同两种情况, 研究了有约束的优化模型, 即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界. 当工件具有相同的释放时间, 我们主要考虑的目标函数有: 总加权完工时间和总加权拖期工件数. 当工件具有不同释放时间, 我们考虑的目标函数有: 最大完工时间、总完工时间以及拖期工件数. 对于每一个问题, 我们分析了问题的计算复杂性. 此外, 对于NP难问题的一些特殊情况本文分析了最优解性质, 基于这些性质给出了最优算法.     

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.     

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.     

Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations

This paper addresses a two-agent single-machine scheduling problem with the co-existing sum-of-processing-times-based learning and deteriorating effects. In the proposed model, it is assumed that the actual processing time of a job of the first (second) agent is a decreasing function of the sum-of-processing-times-based learning (or increasing function of the sum-of-processing-times-based deteriorating effect) in a schedule. The aim of this paper is to find an optimal schedule to minimize the total weighted completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. For the proposed model, we develop a branch-and-bound and some ant colony algorithms for an optimal and near-optimal solution, respectively. Besides, the extensive computational experiments are also proposed to test the performance of the algorithms.     

Earliness–tardiness minimization on a single machine to schedule preventive maintenance tasks: metaheuristic and exact methods

In this paper, we consider the problem of scheduling a set of M preventive maintenance tasks to be performed on M machines. The machines are assigned to execute production tasks. We aim to minimize the total preventive maintenance cost such that the maintenance tasks have to continuously be run during the schedule horizon. Such a constraint holds when the maintenance resources are not sufficient. We solve the problem by two exact methods and meta-heuristic algorithms. As exact procedures we used linear programming and branch and bound methods. As meta-heuristics, we propose a local search approach as well as a genetic algorithm. Computational experiments are performed on randomly generated instances to show that the proposed methods produce appropriate solutions for the problem. The computational results show that the deviation of the meta-heuristics solutions to the optimal one is very small, which confirms the effectiveness of meta-heuristics as new approaches for solving hard scheduling problems.     

An exact approach to early/tardy scheduling with release dates

In this paper, we consider the single machine earliness/tardiness scheduling problem with different release dates and no unforced idle time. The problem is decomposed into weighted earliness and weighted tardiness subproblems. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is the sum of the lower bounds for the two subproblems. The lower bounds and several versions of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.     

Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times

A scheduling problem with unrelated parallel machines, sequence and machine-dependent setup times, due dates and weighted jobs is considered in this work. A branch-and-bound algorithm (B&B) is developed and a solution provided by the metaheuristic GRASP is used as an upper bound. We also propose a set of instances for this type of problem. The results are compared to the solutions provided by two mixed integer programming models (MIP) with the solver CPLEX 9.0. We carry out computational experiments and the algorithm performs extremely well on instances with up to 30 jobs.     

Sequencing a single machine with due dates and deadlines: an ILP-based approach to solve very large instances

We consider the problem of minimizing the weighted number of tardy jobs on a single machine where each job is also subject to a deadline that cannot be violated. We propose an exact method based on a compact integer linear programming formulation of the problem and an effective reduction procedure that allows to solve to optimality instances with up to 30,000 jobs in size, and up to 50,000 jobs in size for the special deadline-free case.     

Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective

In this paper, we minimize the weighted and unweighted number of tardy jobs on a single batch processing machine with incompatible job families. We propose two different mixed integer linear programming (MILP) formulations based on positional variables. The second formulation does not contain a big-M coefficient. Two iterative schemes are discussed that are able to provide tighter linear programming bounds by reducing the number of positional variables. Furthermore, we also suggest a random key genetic algorithm (RKGA) to solve this scheduling problem. Results of computational experiments are shown. The second MILP formulation is more efficient with respect to lower bounds, while the first formulation provides better upper bounds. The iterative scheme is effective for the weighted case. The RKGA is able to find high-quality solutions in a reasonable amount of time.     

Models for a traveling purchaser problem with additional side-constraints

The traveling purchaser problem (TPP) is the problem of determining a tour of a purchaser that needs to buy several items in different shops such that the total amount of travel and purchase costs is minimized. Motivated by an application in machine scheduling, we study a variant of the problem with additional constraints, namely, a limit on the maximum number of markets to be visited, a limit on the number of items bought per market and where only one copy per item needs to be bought. We present an integer linear programming (ILP) model which is adequate for obtaining optimal integer solutions for instances with up to 100 markets. We also present and test several variations of a Lagrangian relaxation combined with a subgradient optimization procedure. The relaxed problem can be solved by dynamic programming and can also be viewed as resulting from applying a state space relaxation technique to a dynamic programming formulation. The Lagrangian based method is combined with a heuristic that attempts to transform relaxed solutions into feasible solutions. Computational results for instances with up to 300 markets show that with the exception of a few cases, the reported differences between best upper bound and lower bound values on the optimal solutions are reasonably small.     

极小化加权完工时间的多资源工序的资源分配问题

针对现实中广泛存在的多资源工序的资源分配问题,考虑基于资源使用的优先次序约束,以最小化加权完工时间为优化目标,构建一类新的资源分配混合整数线性规划模型.其次,提出Benders分解和禁忌搜索的混合算法,该混合算法以Benders分解为基本框架,将原问题分为提供资源分配方案的主问题和计算工序加权完工时间的子问题,并通过改进数学模型和添加禁忌搜索提高混合算法的收敛速度.最后,通过300个随机仿真算例测试结果表明,在相同时间下求解小规模问题时,所提的Benders分解混合算法能获得距离商业求解器CPLEX最优解平均差距为0.86%的满意解;在求解大规模问题时,所提出的算法的性能表现优于CPLEX、禁忌搜索算法、变邻域搜索算法和Benders分解嵌入遗传算法的混合方法,能给出更好的资源分配方案,与CPLEX相比,上界和下界分别改善了4.74%和9.62%.     

An Enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes

This paper addresses a sequence- and machine-dependent batch scheduling problem on a set of unrelated-parallel machines where the objective is to minimize a linear combination of total weighted completion time and total weighted tardiness. In particular, batch scheduling disregards the group technology assumptions by allowing for the possibility of splitting pre-determined groups of jobs into batches with respect to desired lower bounds on batch sizes. With regard to bounds on batch sizes, the MILP model is developed as two integrated batching and scheduling phases to present the problem. A benchmark of small-size instances on group scheduling shows the superior performance of batch scheduling up to 37% reduction in the objective function value. An efficient meta-heuristic algorithm based on tabu search with multi-level diversification and multi-tabu structure is developed at three levels, which moves back and forth between batching and scheduling phases. To eliminate searching in ineffective neighborhoods and thus enhance computational efficiency of search algorithms, several lemmas are proposed and proven. The results of applying lemmas reflect up to 40% reduction in computational times. Comparing the optimal solutions found by CPLEX and tabu search shows that the tabu search algorithm could find solutions, at least as good as CPLEX but in incredibly shorter computational time. In order to trigger the search algorithm, two different initial solution finding mechanisms have been developed and implemented. Also, due to lack of a qualified benchmark for unrelated-parallel machines, a comprehensive data generation mechanism has been developed in a way that it fairly reflects the real world situations encountered in practice. The machine availability times and job release times are considered to be dynamic and the run time of each job differs on different machines based upon the capability of the machines.     

Variable neighborhood search for two-agent flow shop scheduling problem

Multi-agent scheduling in flow shop environment is seldom considered. In this paper flow shop scheduling problem with two agents is studied and its feasibility model is considered, in which the goal is to minimize the makespan of the first agent and the total tardiness of the second agent simultaneously under the given upper bounds. A simple variable neighborhood search (VNS) algorithm is proposed, in which a learning neighborhood structure is constructed to produce new solutions and a new principle is applied to decide if the current solution can be replaced with the new one. VNS is tested on a number of instances and the computational results show the promising advantage of VNS when compared to other algorithms of the problem.     

Two-agent scheduling with learning consideration

In traditional scheduling, job processing times are assumed to be known and fixed over the entire process. However, repeated processing of similar tasks improves workers’ skills. In fact, scheduling with learning effects has received considerable attention recently. On the other hand, it is assumed that there is a common objective for all the jobs. In many management situations, multiple agents pursuing different objectives compete on the usage of a common processing resource. In this paper, we studied a single-machine two-agent scheduling problem with learning effects where the objective is to minimize the total tardiness of jobs from the first agent given that no tardy job is allowed for the second agent. A branch-and-bound algorithm incorporated several properties and a lower bound is developed to search for the optimal solution. In addition, two heuristic algorithms are also proposed to search for the near-optimal solutions. A computational experiment is conducted to evaluate the performance of the proposed algorithms.     

Single machine weighted earliness–tardiness penalty problem with a common due date

In this paper, we have considered a class of single machine job scheduling problems where the objective is to minimize the weighted sum of earliness–tardiness penalties of jobs. The weights are job-independent but they depend on whether a job is early or tardy. The restricted version of the problem where the common due date is smaller than a critical value, is known to be NP-complete. While dynamic programming formulation runs out of memory for large problem instances, depth-first branch-and-bound formulation runs slow for large problems since it uses a tree search space. In this paper, we have suggested an algorithm to optimally solve large instances of the restricted version of the problem. The algorithm uses a graph search space. Unlike dynamic programming, the algorithm can output optimal solutions even when available memory is limited. It has been found to run faster than dynamic programming and depth-first branch-and-bound formulations and can solve much larger instances of the problem in reasonable time. New upper and lower bounds have been proposed and used. Experimental findings are given in detail.Scope and purposeA class of single machine problems arising out of scheduling jobs in JIT environment has been considered in this paper. The objective is to minimize the total weighted earliness–tardiness penalties of jobs. In this paper, we have presented a new algorithm and conducted extensive empirical runs to show that the new algorithm performs much better than the existing approaches in solving large instances of the problem.     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

Minimizing maximum tardiness and delivery costs in a batched delivery system

High delivery costs usually urge manufacturers to dispatch their jobs in batches. However, dispatching the jobs in batches can have profound negative effects on important scheduling objective functions such as minimizing maximum tardiness. This paper considers a single machine scheduling problem with the aim of minimizing the maximum tardiness and delivery costs in a single-machine scheduling problem with batched delivery system. A mathematical model is developed for this problem which can serve to solve it with the help of a commercial solver. However, due to the fact that this model happens to be a mixed integer nonlinear programming model the solver cannot guarantee to reach the global solution. For this reason, a branch and bound algorithm (B&B) is presented to obtain the global solution. Besides, a heuristic algorithm for calculation of the initial upper bound is introduced. Computational results show that the algorithm can be beneficial for solving this problem, especially for large size instances.     

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.     

Solving a two-agent single-machine scheduling problem considering learning effect

Scheduling with multiple agents and learning effect has drawn much attention. In this paper, we investigate the job scheduling problem of two agents competing for the usage of a common single machine with learning effect. The objective is to minimize the total weighted completion time of both agents with the restriction that the makespan of either agent cannot exceed an upper bound. In order to solve this problem we develop several dominance properties and a lower bound based on a branch-and-bound to find the optimal algorithm, and derive genetic algorithm based procedures for finding near-optimal solutions. The performances of the proposed algorithms are evaluated and compared via computational experiments.