A simulation comparison of process and cellular layouts in a dual resource constrained environment

Cellular manufacturing is an integral part of a comprehensive Group Technology program designed to improved the productivity of batch production systems. It has been suggested that shorter throughput times and accompanying reductions in work-in-process inventory are possible due to the inherent flexibility of cellular layouts with respect to worker scheduling. This research examines the impact of a dual resource (labor and equipment) constrained shop on the relative performance of cell layouts vis-a-vis process layouts. In addition, three operator scheduling rules are tested in the cellular layout. The first rule assigns operators on a first come-first served basis to jobs competing for an operator's services. The second rule requires operators in a cell to select a job from the machine queue with the longest queue of jobs. The third rule has operators remaining at a machine queue until it is empty. In the process layout, operators are assinged to waiting jobs on a first come-first served basis. In the initial experiment, the process layout outperformed the cellular layout on both work-in-process levels and throughout time. Additional experiments investigated the sensitivity of the initial results to changes in shop congestion. The process layout outperformed the cellular layout in all of the experiments. The results may be attributed to lower machine and labor utilization in the cellular layout from the dedication of equipment to limited part families.     

A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints

We study a real-world complex hybrid flow-shop scheduling problem arising from a bio-process industry. There are a variety of constraints to be taken into account, in particular zero intermediate capacity and limited waiting time between processing stages. We propose an exact solution approach for this optimization problem, based on a discrete time representation and a mixed-integer linear programming formulation. The proposed solution algorithm makes use of a new family of valid inequalities exploiting the fact that a limited waiting time is imposed on jobs between two successive production stages. The results of our computational experiments confirm that the proposed method produces good feasible schedules for industrial instances.     

Integrating the lot-sizing and sequencing decisions for scheduling a capacitated flow line

In this paper we consider a general problem of scheduling a single flow line consisting of multiple machines and producing a given set of jobs. The manufacturing environment is characterized by sequence dependent set-up times, limited intermediate buffer space, and capacity constraints. In addition, jobs are assigned with due dates that have to be met. The objectives of the scheduling are: (1) to meet the due dates without violating the capacity constraints, (2) to minimize the makespan, and (3) to minimize the inventory holding costs. While most of the approaches in the literature treat the problem of scheduling in flow lines as two independent sub-problems of lot-sizing and sequencing, our approach integrates the lot-sizing and sequencing heuristics. The integrated approach uses the Silver-Meal heuristic (modified to include lot-splitting) for lot-sizing and an improvement procedure applied to Palmer's heuristic for sequencing, which takes into account the actual sequence dependent set-up times and the limited intermedite buffer capacity. We evaluate the performance of the integrated approach and demonstrate its efficacy for scheduling a real world SMT manufacturing environment.     

Inventory Minimization and Production Scheduling: the Case of a Large Hong Kong Company

The background of this study is a rather classical but complex inventory control/production planning/line scheduling problem of a major soft-drink company in Hong Kong. The issue that stands out for this many-product high-sales manufacturer is the storage space of its central warehouse, which often finds itself in the state of overflow or near capacity with finished goods and work-in-process inventory. This phenomenon can create immediate interruptions of production, capital tie-ups and subsequent potential of lost sales. Another obviously important concern is the meeting of forecast demands. A mathematical modelling approach that entails techniques of multi-period aggregate optimization is proposed to tackle the overall problem. The dual objectives are to achieve better production planning and line scheduling in order to minimize inventory build-up and maximize demand satisfaction. Numerical results for a sample problem are reported as an illustration to this proposed two-phase approach.     

An integrated scheduler for manufacturing planning and control (INSCH)

The most basic problem in a manufacturing process is to create valid scheduling system which determines the sequence of jobs to be processed at each of the series of machine centers. An integrated scheduler (INSCH) is developed for small job shop manufacturing systems while considering high machine utilization, low work-in-process, and reduced job lateness.

As an and to understand the interaction of live jobs with the shop, sequence scheduler is developed to complement production scheduler such as Gantt bar chart. INSCH can achieve better performance than simple static models as shown in an example. It is desirable for INSCH to be applied to small job shop manufacturing companies using micro personal computer with relevant modifications discussed.     

Search heuristics for a parallel machine scheduling problem with ready times and due dates

We consider a problem of scheduling orders on identical parallel machines. An order can be released after a given ready time and must be completed before its due date. An order is split into multiple jobs (batches) and a job is processed on one of the parallel machines. The objective of the scheduling problem is to minimize the holding costs of orders including work-in-process as well as finished job inventories. We suggest two local search heuristics, simulated annealing and taboo search algorithms, for the problem. Performance of the suggested algorithms is tested through computational experiments on randomly generated test problems.     

A water-flow algorithm for flexible flow shop scheduling with intermediate buffers

We investigate the flexible flow shop scheduling problem with limited or unlimited intermediate buffers. A common objective of the problem is to find a production schedule that minimizes the completion time of jobs. Other objectives that we also consider are minimizing the total weighted flow time of jobs and minimizing the total weighted tardiness time of jobs. We propose a water-flow algorithm to solve this scheduling problem. The algorithm is inspired by the hydrological cycle in meteorology and the erosion phenomenon in nature. In the algorithm, we combine the amount of precipitation and its falling force to form a flexible erosion capability. This helps the erosion process of the algorithm to focus on exploiting promising regions strongly. To initiate the algorithm, we use a constructive procedure to obtain a seed permutation. We also use an improvement procedure for constructing a complete schedule from a permutation that represents the sequence of jobs in the first stage of the scheduling problem. To evaluate the proposed algorithm, we use benchmark instances taken from the literature and randomly generated instances of the scheduling problem. The computational results demonstrate the efficacy of the algorithm. We have also obtained several improved solutions for the benchmark instances using the proposed algorithm. We further illustrate the algorithm’s capability for solving problems in practical applications by applying it to a maltose syrup production problem.     

A dynamic and reliability-driven scheduling algorithm for parallel real-time jobs executing on heterogeneous clusters

In this paper, a heuristic dynamic scheduling scheme for parallel real-time jobs executing on a heterogeneous cluster is presented. In our system model, parallel real-time jobs, which are modeled by directed acyclic graphs, arrive at a heterogeneous cluster following a Poisson process. A job is said to be feasible if all its tasks meet their respective deadlines. The scheduling algorithm proposed in this paper takes reliability measures into account, thereby enhancing the reliability of heterogeneous clusters without any additional hardware cost. To make scheduling results more realistic and precise, we incorporate scheduling and dispatching times into the proposed scheduling approach. An admission control mechanism is in place so that parallel real-time jobs whose deadlines cannot be guaranteed are rejected by the system. For experimental performance study, we have considered a real world application as well as synthetic workloads. Simulation results show that compared with existing scheduling algorithms in the literature, our scheduling algorithm reduces reliability cost by up to 71.4% (with an average of 63.7%) while improving schedulability over a spectrum of workload and system parameters. Furthermore, results suggest that shortening scheduling times leads to a higher guarantee ratio. Hence, if parallel scheduling algorithms are applied to shorten scheduling times, the performance of heterogeneous clusters will be further enhanced.     

Maintenance scheduling incorporating dynamics of production system and real-time information from workstations

In this paper, a new approach to maintenance scheduling for a multi-component production system which takes into account the real-time information from workstations including remaining reliability of equipments as well as work-in-process inventories in each workstation is proposed. To model dynamics of the system, other information like production line configuration, cycle times, buffers’ capacity and mean time to repair of machines are also considered. Using factorial experiment design the problem is formulated to comprehensively monitor the effects of each possible schedule on throughput of the production system. The optimal maintenance schedule is searched by genetic algorithm-based optimization engine implemented in a simulation optimization platform. The proposed approach exploits all of makespans of planning horizon to find the best opportunity to perform maintenance actions on degrading machines in a way that maximizes the system throughput and mitigates the production losses caused by imperfect traditional maintenance strategies. Finally the proposed method is tested in a real production line to magnify the accuracy of proposed scheduling method. The experimental results indicate that the proposed approach guarantees the operational productivity and scheduling efficiency as well.     

Data Intensive and Network Aware (DIANA) Grid Scheduling

In Grids scheduling decisions are often made on the basis of jobs being either data or computation intensive: in data intensive situations jobs may be pushed to the data and in computation intensive situations data may be pulled to the jobs. This kind of scheduling, in which there is no consideration of network characteristics, can lead to performance degradation in a Grid environment and may result in large processing queues and job execution delays due to site overloads. In this paper we describe a Data Intensive and Network Aware (DIANA) meta-scheduling approach, which takes into account data, processing power and network characteristics when making scheduling decisions across multiple sites. Through a practical implementation on a Grid testbed, we demonstrate that queue and execution times of data-intensive jobs can be significantly improved when we introduce our proposed DIANA scheduler. The basic scheduling decisions are dictated by a weighting factor for each potential target location which is a calculated function of network characteristics, processing cycles and data location and size. The job scheduler provides a global ranking of the computing resources and then selects an optimal one on the basis of this overall access and execution cost. The DIANA approach considers the Grid as a combination of active network elements and takes network characteristics as a first class criterion in the scheduling decision matrix along with computations and data. The scheduler can then make informed decisions by taking into account the changing state of the network, locality and size of the data and the pool of available processing cycles.     

A cyclic approach to large-scale short-term planning in chemical batch production

We deal with the scheduling of processes on a multi-product chemical batch production plant. Such a plant contains a number of multi-purpose processing units and storage facilities of limited capacity. Given primary requirements for the final products, the problem consists in dividing the net requirements for the final and the intermediate products into batches and scheduling the processing of these batches. Due to the computational intractability of the problem, the monolithic MILP models proposed in the literature can generally not be used for solving large-scale problem instances. The cyclic solution approach presented in this paper starts from the decomposition of the problem into a batching and a batch-scheduling problem. The complete production schedule is obtained by computing a cyclic subschedule, which is then repeated several times. In this way, good feasible schedules for large-scale problem instances are found within a short CPU time.     

A decision support system for production scheduling in an ion plating cell

Production scheduling is one of the major issues in production planning and control of individual production units which lies on the heart of the performance of manufacturing organizations. Traditionally, production planning decision, especially scheduling, was resolved through intuition, experience, and judgment. Machine loading is one of the process planning and scheduling problems that involves a set of part types and a set of tools needed for processing the parts on a set of machines. It provides solution on assigning parts and allocating tools to optimize some predefined measures of productivity. In this study, Ion Plating industry requires similar approaches on allocating customer's order, i.e. grouping production jobs into batches and arrangement of machine loading sequencing for (i) producing products with better quality products; and (ii) enabling to meet due date to satisfy customers. The aim of this research is to develop a Machine Loading Sequencing Genetic Algorithm (MLSGA) model to improve the production efficiency by integrating a bin packing genetic algorithm model in an Ion Plating Cell (IPC), such that the entire system performance can be improved significantly. The proposed production scheduling system will take into account the quality of product and service, inventory holding cost, and machine utilization in Ion Plating. Genetic Algorithm is being chosen since it is one of the best heuristics algorithms on solving optimization problems. In the case studies, industrial data of a precious metal finishing company has been used to simulate the proposed models, and the computational results have been compared with the industrial data. The results of developed models demonstrated that less resource could be required by applying the proposed models in solving production scheduling problem in the IPC.     

Adaptive data-aware utility-based scheduling in resource-constrained systems

This paper addresses the problem of the dynamic scheduling of data-intensive multiprocessor jobs. Each job requires some number of CPUs and some amount of data that needs to be downloaded into a local storage. The completion of each job brings some benefit (utility) to the system, and the goal is to find the optimal scheduling policy that maximizes the average utility per unit of time obtained from all completed jobs. A co-evolutionary solution methodology is proposed, where the utility-based policies for managing local storage and for scheduling jobs onto the available CPUs mutually affect each other’s environments, with both policies being adaptively tuned using the Reinforcement Learning (RL) methodology. The simulation results demonstrate that the performance of the scheduling policies increases significantly as a result of being tuned with RL, to the point that they significantly outperform the best scheduling algorithm suggested in the literature for jobs with soft-deadline utility functions.     

面向MapReduce计算模式的中间数据通信优化

针对MapReduce计算模式在Map阶段结束后会产生海量中间数据,导致存在大量跨越机架交换机的数据通信问题,提出一种优化Map密集型作业的中间数据通信优化方法。首先,提取MapReduce计算作业的运行前调度信息的特征并且量化数据通信活跃度;然后,采用朴素贝叶斯分类模型实现分类预测,将历史作业的运行数据作为样本来训练分类模型;最后,根据作业分类预测结果把通信活跃的作业集中映射到同一机架中,通过提高通信局部性来优化性能瓶颈。实验结果表明,所提方案对Shuffle子过程稠密的作业优化效果明显,能够提高4%~5%的计算性能;此外,在多用户运行情况下能降低4.1%中间数据通信延迟。所提方法可有效降低大数据计算过程中的通信延迟,提高异构集群的计算性能。     

A multi-objective evolutionary algorithm guided by directed search for dynamic scheduling

This paper considers dynamic multi-objective machine scheduling problems in response to continuous arrival of new jobs, under the assumption that jobs can be rejected and job processing time is controllable. The operational cost and the cost of deviation from the baseline schedule need to be optimized simultaneously. To solve these dynamic scheduling problems, a directed search strategy (DSS) is introduced into the elitist non-dominated sorting genetic algorithm (NSGA-II) to enhance its capability of tracking changing optimums while maintaining fast convergence. The DSS consists of a population re-initialization mechanism (PRM) to be adopted upon the arrival of new jobs and an offspring generation mechanism (OGM) during evolutionary optimization. PRM re-initializes the population by repairing the non-dominated solutions obtained before the disturbances occur, modifying randomly generated solutions according to the structural properties, as well as randomly generating solutions. OGM generates offspring individuals by fine-tuning a few randomly selected individuals in the parent population, employing intermediate crossover in combination with Gaussian mutations to generate offspring, and using intermediate crossover together with a differential evolution based mutation operator. Both PRM and OGM aim to strike a good balance between exploration and exploitation in solving the dynamic multi-objective scheduling problem. Comparative studies are performed on a variety of problem instances of different sizes and with different changing dynamics. Experimental results demonstrate that the proposed DSS is effective in handling the dynamic scheduling problems under investigation.     

混合存储模式下MapReduce作业调度

在异构Hadoop集群场景中, 为了缓和由于纠删码和副本存储模式混合使用, 以及服务器节点本身实时算力差异造成的MapReduce作业处理效率低下的问题, 本文实现了一种根据数据存储情况和节点实时负载来在多并发场景下动态调节MapReduce作业任务分配情况的调度策略. 该策略通过修改当前Hadoop框架中的数据存储选址策略并对节点任务并发量进行动态控制, 在多作业并发时实现更加均衡的作业间资源分配. 实验结果表明, 相较于Hadoop默认的两种作业调度策略, 本文提出的调度模式能够将作业完成时间缩短约17%, 并有效避免部分作业面临的饥饿现象.     

Coordinated Logistics Scheduling for In-House Production and Outsourcing

In this paper, we address a new scheduling model for a firm with an option of outsourcing. A job can be processed by either in-house production or outsourcing. All outsourced jobs have to be transported back to the firm in batches, and the transportation costs have to be taken into account. We model the situation as a scheduling problem with transportation considerations. We discuss four commonly used objective functions, and solve them by dynamic programming algorithms. Note to Practitioners-An efficient supply chain management needs the coordination of production and transportation. Such problems exist in many different scenarios. This research considers a particular problem for a firm that has an option of using a subcontractor to fulfill part of its orders. The production schedule has to be coordinated with logistics issues for the transportation from the subcontractor to the firm. The purposes of this paper are twofold. First, we build models and provide optimal solutions for the specific cases discussed in this paper. Second, we hope to raise the issue of coordinated logistics scheduling, and motivate future research on more complicated models.     

Period of Processing on Serial Production Line, Optimal Scheduling and Application

In this paper, we study period of processing on serial production line when batch jobs are processed under non-blocking optimal control. For the state that different jobs can be completed on different or same machines, we give expression of period of processing. Then we present an optimal scheduling problem, and put forward an algorithm to solve this problem. Finally we apply these results to hot-metal rolling serial production line at TaiYuan steel company, China, and obtain an optimal scheduling table of different kinds of steel plates.     

SEED: solar energy‐aware efficient scheduling for data centers

It is well known that data centers are consuming a large amount of energy that incurs significant financial and environmental costs. Recently, there has been an increasing interest in utilizing green energy for data centers, where green energy sources include solar and wind. This paper studies the crucial problem of maximizing the utilization of green energy through scheduling complex jobs in data centers in order to reduce the use of traditional brown energy. However, it is highly challenging for data centers to make use of green energy. First, the availability of typical green energy is variable to dynamic changes of natural environments, for example, weather. Second, although predictions can be made for the future availability of green energy, it is inevitable that such predictions have errors. Third, jobs are associated with strict deadlines, and it is required that jobs are completed before their deadlines. Finally, because the reliability in a data center relies upon temperature, the awareness of temperature should be taken into account while maximizing the green energy. In this paper, we consider online scheduling of jobs whose arrivals to the data center system dynamically. In addition, we explicitly take the power consumption of switches into account when scheduling jobs onto computing nodes. Two solar energy‐aware algorithms called SEEDMin and SEEDMax have been proposed. Then, we extend SEED to RSEED with the awareness of reliability. To evaluate the effectiveness of the proposed algorithms, comprehensive simulations have been conducted, and the proposed algorithms are compared with other state‐of‐art algorithms. Experimental results demonstrate that both SEEDMin and SEEDMax can significantly increase the utilization of solar energy without violating job deadlines and overall energy budget. The amount of solar energy utilized by SEEDMin and SEEDMax is 33.4%and35.3% larger than that of two traditional scheduling algorithms, MinMin and MinMax, respectively. Also, it can be seen that RSEED greatly improves the reliability by decreasing the temperature. Copyright © 2013 John Wiley & Sons, Ltd.     

一种作业弹性与截止时间感知的作业调度算法

针对采用MapReduce模型的大数据分析作业的调度问题进行深入研究，并分析现有任务调度算法的缺陷，现有算法没有考虑资源分配对于作业截止时间的影响，也未考虑不同类型作业截止时间的敏感性问题。因作业的完成时间随着分配资源的不同而改变，故称之为弹性作业，截止时间敏感性是指不同类型作业对截止时间要求的严格程度不同。针对以上问题，提出一种截止时间感知的弹性作业调度算法（DA）。该算法将作业依据截止时间敏感程度进行分类，在基于作业整体执行时间预测的基础上，通过调控不同的资源分配策略来改变作业完成时间，同时结合用户对于截止时间的需求及作业预执行的收益来提前规划作业的资源分配及调度次序使得整体收益最大化。将算法在仿真拥有210个物理节点的集群中进行实验，实验表明该算法满足了截止时间的限制并使得作业整体收益值平均提高了2.37倍。