Flow shop scheduling problems with decreasing linear deterioration under dominant machines

This paper considers the general, no-wait and no-idle flow shop scheduling problems with deteriorating jobs, respectively. By a deteriorating job, we mean that the processing time is a decreasing function of its execution starting time. The normal processing time proportional to its decreasing rate is assumed and some dominant relationships between machines can be satisfied. It is shown that for the problems to minimize the makespan or the weighted sum of completion time, polynomial algorithms still exist, although these problems are more complicated than the classical ones. When the objective is to minimize the maximum lateness, the solutions of a classical version may not hold.     

Scheduling jobs under decreasing linear deterioration

This paper considers the scheduling problems under decreasing linear deterioration. Deterioration of a job means that its processing time is a function of its execution start time. Optimal algorithms are presented respectively for single machine scheduling of minimizing the makespan, maximum lateness, maximum cost and number of late jobs. For two-machine flow shop scheduling problem to minimize the makespan, it is proved that the optimal schedule can be obtained by Johnson's rule. If the processing times of operations are equal for each job, flow shop scheduling problems can be transformed into single machine scheduling problems.     

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.     

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 two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations

Scheduling with learning effects has received a lot of research attention lately. By learning effect, we mean that job processing times can be shortened through the repeated processing of similar tasks. On the other hand, different entities (agents) interact to perform their respective tasks, negotiating among one another for the usage of common resources over time. However, research in the multi-agent setting is relatively limited. Meanwhile, the actual processing time of a job under an uncontrolled learning effect will drop to zero precipitously as the number of jobs increases or a job with a long processing time exists. Motivated by these observations, we consider a two-agent scheduling problem in which the actual processing time of a job in a schedule is a function of the sum-of-processing-times-based learning and a control parameter of the learning function. The objective is 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. We develop a branch-and-bound and three simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions.     

A two-machine flowshop problem with two agents

The multiple-agent scheduling problems have received increasing attention recently. However, most of the research focuses on deriving feasible/optimal solutions or examining the computational complexity of the intractable cases in a single machine. Often a number of operations have to be done on every job in many manufacturing and assembly facilities (Pinedo, 2002 [1]). In this paper, we consider a two-machine flowshop problem where the objective is to minimize the total completion time of the first agent with no tardy jobs for the second agent. We develop a branch-and-bound algorithm and simulated annealing heuristic algorithms to search for the optimal solution and near-optimal solutions for the problem, respectively.     

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.     

Genetic algorithms for a two-agent single-machine problem with release time

Scheduling with two competing agents has drawn a lot of attention lately. However, it is assumed that all the jobs are available in the beginning in most of the research. In this paper, we study a single-machine problem in which jobs have different release times. The objective is to minimize the total tardiness of jobs from the first agent given that the maximum tardiness of jobs from the second agent does not exceed an upper bound. Three genetic algorithms are proposed to obtain the near-optimal solutions. Computational results show that the branch-and-bound algorithm could solve most of the problems with 16 jobs within a reasonable amount of time. In addition, it shows that the performance of the combined genetic algorithm is very good with mean error percentages of less than 0.2% for all the cases.     

基于异构多核平台的同步数据流图帕累托优化与调度

同步数据流图被广泛用于多媒体和数字信号处理程序等流应用程序的建模。流应用程序须达到一定吞吐量才能流畅运行,利用异构多核处理器来进一步提高流应用程序的吞吐量已经成为当今嵌入式系统的发展趋势,但是提高吞吐量往往伴随着能耗的增加。为了解决这个问题,基于异构多核平台的同步数据流图系统模型,给出了求解所有能耗和吞吐量的帕累托优化点及其相应静态调度的方法。首先将系统模型转换为时间自动机网络,并将分析目标转换为时序逻辑公式;再使用实时模型检测工具UPPAAL寻找解决方案;最后对UPPAAL返回的结果进行分析,找出满足要求的调度。由于模型检测方法可对问题空间进行穷尽搜索,该方法得到的 结果 是精确的。该方法可帮助设计者在系统开发早期了解系统能耗和吞吐量的量化关系,有利于缩短系统的开发周期,降低开发成本。     

一种求解约束多目标优化问题的线性进化算法

针对多目标优化问题,提出了一种新的基于实数编码的线性进化算法.新算法将约束优化问题的高维搜索空间通过线性变换映射到二维空间,在二维空间中探索原优化问题的解,并构造出一种线性适应度函数,重新设计了一种基于密度函数的交叉算子.对二组典型优化问题的测试表明,本算法是可行和有效的,解集分布的均匀性与多样性均较理想.     

具有线性恶化加工时间的调度问题

讨论了工件具有线性恶化加工时间的调度问题.在这类问题中,工件的恶化函数为线性函数.对单机调度问题中目标函数为极小化最大完工时间加权完工时间和,最大延误以及最大费用等问题分别给出了最优算法.对两台机器极小化最大完工时间的Flowshop问题,证明了利用Johnson规则可以得到最优调度.对于一般情况,如果同一工件的工序的加工时间均相等,则Flowshop问题可以转化为单机问题.     

The complexity of mean flow time scheduling problems with release times

We study the problem of preemptive scheduling of n} jobs with given release times on m identical parallel machines. The objective is to minimize the average flow time. In this paper, show that when all jobs have equal processing times then the problem can be solved in polynomial time using linear programming. Our algorithm can also be applied to the open-shop problem with release times and unit processing times. For the general case (when processing times are arbitrary), we show that the problem is unary NP-hard. P. Baptiste and C. Dürr: Supported by the NSF/CNRS grant 17171 and ANR/Alpage. P. Brucker: Supported by INTAS Project 00-217 and by DAAD PROCOPE Project D/0427360. M. Chrobak: Supported by NSF grants CCR-0208856 and INT-0340752. S. A. Kravchenko: Supported by the Alexander von Humboldt Foundation.     

Scheduling jobs with equal processing times and time windows on identical parallel machines

We present a linear programming approach to the problem of scheduling equal processing time jobs with release dates and deadlines on identical parallel machines. The known algorithm with complexity O(n ³log log n) of B. Simons schedules all the jobs while minimizing both the maximum completion time and the mean flow time. Our approach permits also to minimize the weighted sum of completion times and total tardiness in polynomial time for the problems without deadlines. The complexity status of these problems was open. Contract/grant sponsor: Alexander von Humboldt Foundation.     

Fast computation of equispaced Pareto manifolds and Pareto fronts for multiobjective optimization problems

In this paper, we consider the problem of generating a well sampled discrete representation of the Pareto manifold or the Pareto front corresponding to the equilibrium points of a multi-objective optimization problem. We show how the introduction of simple additional constraints into a continuation procedure produces equispaced points in either of those two sets. Moreover, we describe in detail a novel algorithm for global continuation that requires two orders of magnitude less function evaluations than evolutionary algorithms commonly used to solve this problem. The performance of the methods is demonstrated on problems from the current literature.     

A simulation-based scheduling system for real-time optimization and decision making support

This paper presents an industrial application of simulation-based optimization (SBO) in the scheduling and real-time rescheduling of a complex machining line in an automotive manufacturer in Sweden. Apart from generating schedules that are robust and adaptive, the scheduler must be able to carry out rescheduling in real time in order to cope with the system uncertainty effectively. A real-time scheduling system is therefore needed to support not only the work of the production planner but also the operators on the shop floor by re-generating feasible schedules when required. This paper describes such a real-time scheduling system, which is in essence a SBO system integrated with the shop floor database system. The scheduling system, called OPTIMISE scheduling system (OSS), uses real-time data from the production line and sends back expert suggestions directly to the operators through Personal Digital Assistants (PDAs). The user interface helps in generating new schedules and enables the users to easily monitor the production progress through visualization of production status and allows them to forecast and display target performance measures. Initial results from this industrial application have shown that such a novel scheduling system can help both in improving the line throughput efficiently and simultaneously supporting real-time decision making.     

The normalized normal constraint method for generating the Pareto frontier

The authors recently proposed the normal constraint (NC) method for generating a set of evenly spaced solutions on a Pareto frontier – for multiobjective optimization problems. Since few methods offer this desirable characteristic, the new method can be of significant practical use in the choice of an optimal solution in a multiobjective setting. This papers specific contribution is two-fold. First, it presents a new formulation of the NC method that incorporates a critical linear mapping of the design objectives. This mapping has the desirable property that the resulting performance of the method is entirely independent of the design objectives scales. We address here the fact that scaling issues can pose formidable difficulties. Secondly, the notion of a Pareto filter is presented and an algorithm thereof is developed. As its name suggests, a Pareto filter is an algorithm that retains only the global Pareto points, given a set of points in objective space. As is explained in the paper, the Pareto filter is useful in the application of the NC and other methods. Numerical examples are provided.     

动态多目标优化进化算法及性能分析

针对动态多目标优化问题提出了一种求解的新进化算法。首先,构建了一种近似估计新环境下动态多目标优化问题的Pareto核迁移估计模型。其次,当探测到问题环境发生改变时,算法利用以前环境搜索到的Pareto核的有效信息通过Pareto核迁移估计模型对新环境下的进化种群进行近似估计;当问题的环境未发生变化时,引入了带区间分割的变异算子和非劣解存档保优策略,以提高算法的搜索效率。最后计算机仿真表明新算法对动态多目标优化问题十分有效。     

线性规划在车间动态排产中的应用与实现

本文基于线性规划思想提出了一套快速实现车间最优动态排产的方法,该方法在确保订单不延迟的情况下,能够有效合理地安排生产过程。本文通过对车间工序建立数学模型,应用改进的算法对所有订单进行评估,确定所有订单的每道工序的最早发生时间和最迟发生时间,从而实现车间最优动态排产。本算法适用于严格按订单组织生产的企业,企业可以利用该算法对订单进行评估,确定是否可以接受该订单以及订单最佳投产时间。本文提出的方法已经在四川省某制造业信息化示范企业投入实际应用。