工件工序可并行的作业车间调度模型与求解

针对传统作业车间调度模型没有考虑工件工序存在并行性的不足,提出一种以最小化完工时间为目标的工件工序可并行作业车间调度模型,且在模型中考虑了工序加工设备柔性;设计了基于遗传算法的调度算法,其中染色体编码采用分段编码方式,并提出一种适用于工件工序存在并行性的染色体解码方法.实验结果表明,文中算法能够有效地解决工件工序可并行的作业车间调度问题.     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

工序间存在零等待约束的复杂产品调度研究

针对实际装配生产中工序之间存在零等待约束的复杂产品的调度问题, 提出了一种把存在零等待约束的工序虚拟成一个工序的方法. 该方法在提出复杂产品、标准工序、虚拟工序、零等待和扩展加工工艺树的概念基础上, 对扩展加工工艺树中的标准工序采用拟关键路径法和最佳适应调度的车间调度算法进行调度, 对虚拟工序采用移动交换算法在相应设备上分离调度, 将存在零等待约束的调度问题转化为存在虚拟工序的无零等待约束的调度问题. 实例表明, 所提出的调度算法能够较好地解决具有实际意义的工序间存在零等待约束的复杂产品的调度问题, 且易于实现.     

基于拟关键路径的二车间综合调度算法

针对如何将复杂产品工序有效地分配到具有相同设备资源的二车间加工的问题,提出了基于拟关键路径法的二车间综合调度算法。为了让二车间负载平衡并进行充分的并行处理, 尽早结束产品加工,该算法按拟关键路径法(ACPM)对工序排序,再采取二车间加工结束时间接近的预调度策略进行调度。为了减少二车间工序的迁移次数,该算法将入度不小于2的工序放入其紧前工序分配较多的车间;将入度小于2且其紧后工序的入度不小于2的工序分配到能让其尽早结束的车间;对于其他唯一紧前紧后工序与其叶子节点所形成的工序串按预调度策略进行整串调度。实例表明,该算法可以在二次复杂度内较优地实现具有相同设备资源的二车间分布式综合调度。     

基于剪枝分层的柔性加工车间调度算法

针对柔性作业车间调度中工序间存在的冗余调度次序约束关系问题和工序-设备间存在的多加工模式情况,提出基于剪枝分层的柔性加工车间调度算法.该算法首先用有向无环图表示工序及工序间的调度次序关系,采用剪枝法消除图中的冗余弧,采用分层法对图中结点分层;其次对加工模式进行分类,制定工序-设备预约策略和工序-设备预分配策略;最后,采用事件驱动策略,驱动时刻按所提出的柔性加工策略调度工序加工.理论分析和实例表明,所提出的算法具有较好的调度效果.     

两车间可调度工序均衡处理的综合调度算法

在两车间具备相同设备资源的生产条件时,需要考虑产品完成时间和车间之间工序移动次数尽可能少的问题。为此,提出两车间可调度工序均衡处理的综合调度算法。为减少单件复杂产品的完成时间,针对可调度工序的灵活性、并行性和两车间设备相同的条件,采用可调度工序车间均衡策略进行分组。为减少工序移动次数,按分组工序车间确定策略分配工序所在车间,并进行调度。实例结果表明,该算法可实现两车间综合调度,且产品完成时间和车间之间的工序移动次数较少。     

基于混合遗传算法的车间生产计划调度

针对车间环境的动态随机性、多工序问题,研究了调度问题和算法的特征,提出了一种基于混合遗传算法的车间调度方案。在传统遗传算法的基础上,采用交叉算子、变异算子与启发式算子结合,实现了混合遗传算法,避免了传统遗传算法解的不可行性。再把紧急工序作为一个时域段,结合可变时域滚动机制,实现了可插入紧急工序的调度算法,使一道工序不需重新调度也可排入作业计划,避免了不可插入性,节省了时间,提高了效率。结合实例进行仿真分析,结果表明了调度的可行性、正确性、满意度。     

车间调度DSS设计的优化方法

一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序,而且工序的变更又可能导致相当大的调度规模,因此车间调度是一种决策模型,应用该模型设计的车间调度决策支持系统可以在短时间内有效地提供一种优化决策。遗传算法是一种高效并行的全局搜索方法,文章通过对遗传算法关键因素的讨论,研究了SFSDSS设计的优化方法。     

不确定工时下多目标柔性作业车间调度问题的进化求解方法

在实际工业生产中,调度环境的复杂性与不确定性使得调度问题求解难度大大提高.针对加工时间不确定的柔性作业车间调度问题,采用不确定参数描述随机工时波动程度和约束条件允许违背程度,构建工时波动服从指数分布的多目标柔性车间调度模型.基于机会约束规划理论,将不确定调度问题转化为加工时间确定的柔性作业车间调度问题,求解得到一定程度上具有鲁棒性能的调度方案.在执行过程中,采用工序移动调整和重调度方法对作业排产方案进行动态调整.基于双链式编码以及贪婪插入法解码规则,提出了基于变邻域搜索的混合NSGA-Ⅱ算法.针对车间调度问题的多约束性和计算复杂度高等特点,设计了基于机器选择的复合启发式规则,包括依据概率的最小累计机器负载和最短工序加工时间规则,以获取更加接近Pareto前沿的均匀分布初始种群.采用改进工序和设备交叉策略以提高算法的全局搜索能力.此外,基于关键工序和机器选择的多种邻域结构,设计了变邻域搜索策略,以进一步提高算法的局部搜索能力.通过Kacem和Brandimarte标准算例的数值仿真以及与多种代表算法的统计比较,验证了所提算法的有效性.本文所提算法为不确定柔性作业车间调度问题提供了更优的调...     

作业车间调度问题的自适应步进值果蝇算法研究

作业车间调度问题是提高企业的生产效率的一个重要环节.设计了一种自适应步进值果蝇算法,该算法通过基于工序的编码方式形成果蝇个体,并求出每个果蝇个体相对应的最大完工时间,采用了自适应步进值的分类嗅觉搜索方法,对果蝇种群进行优化,最终使果蝇个体快速找到目标函数即味道浓度判定函数的最小值也就是最优的调度方案,从而提高作业车间的调度效率.该算法实现简单,只需要设置两个参数,并且全局寻优能力较强,能够有效地解决作业车间调度问题.     

Memory access schedule minimization for embedded systems

The growing gap between microprocessor speed and DRAM speed is a major problem that computer designers are facing. In order to narrow the gap, it is necessary to improve DRAM’s speed and throughput. To achieve this goal, this paper proposes techniques to take advantage of the characteristics of the 3-stage access of contemporary DRAM chips by grouping the accesses of the same row together and interleaving the execution of memory accesses from different banks. A family of Bubble Filling Scheduling (BFS) algorithms are proposed in this paper to minimize memory access schedule length and improve memory access time for embedded systems.When the memory access trace is known in some application-specific embedded systems, this information can be fully utilized to generate efficient memory access schedules. The offline BFS algorithm can generate schedules which are 47.49% shorter than in-order scheduling and 8.51% shorter than existing burst scheduling on average. When memory accesses are received by the single memory controller in real time, the memory accesses have to be scheduled as they come. The online BFS algorithm in this paper serves this purpose and generates schedules which are 58.47% shorter than in-order scheduling and 4.73% shorter than burst scheduling on average. To improve the memory throughput and further reduce the memory access schedule, an architecture with dual memory controllers is proposed. According to the experimental results, the dual controller algorithm can generate schedules which are 62.89% shorter than in-order scheduling, 14.23% shorter than burst scheduling, and 10.07% shorter than single controller BFS algorithms on average.     

A multi-objectives scheduling algorithm based on cuckoo optimization for task allocation problem at compile time in heterogeneous systems

To handle scheduling of tasks on heterogeneous systems, an algorithm is proposed to reduce execution time while allowing for maximum parallelization. The algorithm is based on multi-objective scheduling cuckoo optimization algorithm (MOSCOA). In this algorithm, each cuckoo represents a scheduling solution in which the ordering of tasks and processors allocated to them are considered. In addition, the operators of cuckoo optimization algorithm means laying and immigration are defined so that it is usable for scheduling scenario of the directed acyclic graph of the problem. This algorithm adapts cuckoo optimization algorithm operators to create proper scheduling in each stage. This ensures avoiding local optima while allowing for global search within the problem space for accelerating the finding of a global optimum and delivering a relatively optimized scheduling with the least number of repetitions. Moving toward global optima is done through a target immigration operator in this algorithm and schedules in each repetition are pushed toward optimized schedules to secure global optima. The results of MOSCOA implementation on a large number of random graphs and real-world application graphs with a wide range characteristics show MOSCOA superiority over the previous task scheduling algorithms.     

Scheduling precedence constrained task graphs with non-negligibleintertask communication onto multiprocessors

The multiprocessor scheduling problem is the problem of scheduling the tasks of a precedence constrained task graph (representing a parallel program) onto the processors of a multiprocessor in a way that minimizes the completion time. Since this problem is known to be NP-hard in the strong sense in all but a few very restricted eases, heuristic algorithms are being developed which obtain near optimal schedules in a reasonable amount of computation time. We present an efficient heuristic algorithm for scheduling precedence constrained task graphs with nonnegligible intertask communication onto multiprocessors taking contention in the communication channels into consideration. Our algorithm for obtaining satisfactory suboptimal schedules is based on the classical list scheduling strategy. It simultaneously exploits the schedule-holes generated in the processors and in the communication channels during the scheduling process in order to produce better schedules. We demonstrate the effectiveness of our algorithm by comparing with two competing heuristic algorithms available in the literature     

Scheduling task graphs optimally with A*

Scheduling tasks onto the processors of a parallel system is a crucial part of program parallelisation. Due to the NP-hard nature of the task scheduling problem, scheduling algorithms are based on heuristics that try to produce good rather than optimal schedules. Nevertheless, in certain situations it is desirable to have optimal schedules, for example for time-critical systems or to evaluate scheduling heuristics. This paper investigates the task scheduling problem using the A* search algorithm which is a best-first state space search. The adaptation of the A* search algorithm for the task scheduling problem is referred to as the A* scheduling algorithm. The A* scheduling algorithm can produce optimal schedules in reasonable time for small to medium sized task graphs with several tens of nodes. In comparison to a previous approach, the here presented A* scheduling algorithm has a significantly reduced search space due to a much improved consistent and admissible cost function f(s) and additional pruning techniques. Experimental results show that the cost function and the various pruning techniques are very effective for the workload. Last but not least, the results show that the proposed A* scheduling algorithm significantly outperforms the previous approach.     

A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line

In this paper, the problem of determining cyclic schedules for a material handling hoist in the printed-circuit-board(PCB) electroplating line is considered. The objective of this research is to determine an optimal simple-cycle schedule of the hoist which in turn maximizes the line throughput rate. Previous approaches to the cyclic hoist scheduling problem are all mathematical programming-based approaches to develop cyclic schedules(Mixed Integer Programming, Linear Programming based Branch and Bound, Branch and Bound Search Method and so on). In this paper, a genetic algorithm-based approach for a single hoist scheduling in the PCB electroplating line is described. Through an experiment for the well known example data, the proposed algorithm is shown to be more efficient than the previous mathematical programming-based algorithm.     

On parallelizing the multiprocessor scheduling problem

Existing heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a similar or potentially better solution, is to parallelize the scheduling algorithm. This can be done by partitioning the task graphs and concurrently generating partial schedules for the partitioned parts, which are then concatenated to obtain the final schedule. The problem, however, is nontrivial as there exists dependencies among the nodes of a task graph which must be preserved for generating a valid schedule. Moreover, the time clock for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this paper, we introduce a parallel algorithm that is guided by a systematic partitioning of the task graph to perform scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation and communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. We have implemented the algorithm on the Intel Paragon and compared it with three closely related algorithms. The experimental results indicate that our algorithm yields higher quality solutions while using an order of magnitude smaller scheduling times. The algorithm also exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size     

An Integrated Approach to Locality-Conscious Processor Allocation and Scheduling of Mixed-Parallel Applications

Complex parallel applications can often be modeled as directed acyclic graphs of coarse-grained application tasks with dependences. These applications exhibit both task and data parallelism, and combining these two (also called mixed parallelism) has been shown to be an effective model for their execution. In this paper, we present an algorithm to compute the appropriate mix of task and data parallelism required to minimize the parallel completion time (makespan) of these applications. In other words, our algorithm determines the set of tasks that should be run concurrently and the number of processors to be allocated to each task. The processor allocation and scheduling decisions are made in an integrated manner and are based on several factors such as the structure of the task graph, the runtime estimates and scalability characteristics of the tasks, and the intertask data communication volumes. A locality-conscious scheduling strategy is used to improve intertask data reuse. Evaluation through simulations and actual executions of task graphs derived from real applications and synthetic graphs shows that our algorithm consistently generates schedules with a lower makespan as compared to Critical Path Reduction (CPR) and Critical Path and Allocation (CPA), two previously proposed scheduling algorithms. Our algorithm also produces schedules that have a lower makespan than pure task- and data-parallel schedules. For task graphs with known optimal schedules or lower bounds on the makespan, our algorithm generates schedules that are closer to the optima than other scheduling approaches.     

Multi-objective optimization model for multi-project scheduling on critical chain

In this paper, a multi-project scheduling in critical chain problem is addressed. This problem considers the influence of uncertainty factors and different objectives to achieve completion rate on time of the whole projects. This paper introduces a multi-objective optimization model for multi-project scheduling on critical chain, which takes into consideration multi-objective, such as overall duration, financing costs and whole robustness. The proposed model can be used to generate alternative schedules based on the relative magnitude and importance of different objectives. To respond to this need, a cloud genetic algorithm is proposed. This algorithm using randomness and stability of Normal Cloud Model, cloud genetic algorithm was designed to generate priority of multi-project scheduling activities and obtain plan of multi-project scheduling on critical chain. The performance comparison shows that the cloud genetic algorithm significantly outperforms the previous multi-objective algorithm.     

A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem

Cash transportation vehicle routing and scheduling are essential for security carriers to minimize their operating costs and ensure safe cash conveyance. In real operations, to increase cash conveyance safety, there must be significant variation in daily cash transportation vehicle routes and schedules, making such vehicle routes and schedules difficult to formulate. However, for convenient planning purposes, security carriers normally plan such routes and schedules based on personal experience, without considering variations in routes and schedules from a system perspective. As a result, the obtained routes and schedules are neither safe nor efficient for transporting cash. In this study, a model is developed where the time–space network technique is utilized to formulate the potential movements of cash transportation vehicles among all demand points in the dimensions of time and space. This model incorporates a new concept of similarity of time and space for routing and scheduling, which is expected to help security carriers formulate more flexible routing and scheduling strategies. This is helpful to reduce the risk of robbery. Mathematically, the model is formulated as an integer multiple-commodity network flow problem. A solution algorithm, based on a problem decomposition/collapsing technique, coupled with the use of a mathematical programming software, is developed to efficiently solve the problem. The case study results show that our model and solution algorithm could be useful references for security carriers in actual practice.     

一种云计算环境下的工作流双向调度方法

为降低云计算中工作流调度的时间和成本,提出了一种双向调度算法,以实现后向Backward和前向Forward的双向调度。首先,Backward算法按照每个任务的最迟开始时间进行后向调度;此基础上,为降低虚拟机调度费用,Forward算法尽可能地提前调度每个任务,且在前向调度过程中充分考虑到工作流deadline、最大cost及传输时间的限制,从而实现对虚拟机的动态调度。由实验可知,本算法比BDA算法以及ICPCP算法更节约虚拟机调度成本,提高了调度的灵活性。