基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

An estimation of distribution algorithm for lot-streaming flow shop problems with setup times

Lot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and no-idling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses.     

Container Scheduling: Complexity and Algorithms

We consider the transport of containers through a fleet of ships. Each ship has a capacity constraint limiting the total number of containers it can carry and each ship visits a given set of ports following a predetermined route. Each container has a release date at its origination port, and a due date at its destination port. A container has a size 1 or size 2; size 1 represents a 1 TEU (20‐foot equivalent unit) and size 2 represents 2 TEUs. The delivery time of a container is defined as the time when the ship that carries the container arrives at its destination port. We consider the problem of minimizing the maximum tardiness over all containers. We consider three scenarios with regard to the routes of the ships, namely, the ships having (i) identical, (ii) nested, and (iii) arbitrary routes. For each scenario, we consider different settings for origination ports, release dates, sizes of containers, and number of ports; we determine the computational complexity of various cases. We also provide a simple heuristic for some cases, with its worst case analysis. Finally, we discuss the relationship of our problems with other scheduling problems that are known to be open.     

Sequencing and Scheduling Appointments with Potential Call‐In Patients

This paper studies appointment scheduling for a combination of routine patients who book well in advance and last‐minute patients who call for an appointment later that same day. We determine when these same‐day patients should be scheduled throughout the day, and how the prospect of their arrivals affects the appointment times of the routine patients. By formulating the problem as a stochastic linear program, we are able to incorporate random and heterogeneous service times and no‐show rates, ancillary physician tasks, and appointment delay costs for same‐day patients who prefer to see the doctor as early as possible. We find that the optimal patient sequence is quite sensitive to the no‐show probabilities and the expected number of same‐day patients. We also develop two simple heuristic solutions to this combinatorial sequencing problem.     

P2P应用层数据流量优化

为减少对主干网络带宽的消耗,提出了一套数据流量优化方法。首先通过把Peer间的邻居关系明确划分为物理邻居关系和逻辑邻居关系,并用探路者算法来发现Peer的物理邻居,实现拓扑匹配;然后在数据调度算法中,引入通报/退避机制,把大部分数据传输控制在城域网络内部。通过建立模拟仿真环境进行实验分析,证实了该方法可以减少90%以上的网络数据流量。     

Integrated scheduling and inventory management of an oil products distribution system

The oil supply chain is facing new challenges due to emerging issues such as new alternative energy sources, oil sources scarcity, and price variability with high impact on demand and production and profit margins reduction. Additionally, the existence of large, complex and world wide spread businesses implies a complex system to be managed where distribution can be seen as one of the key areas that needs to be efficiently and effectively managed. Different types of distribution modes characterize the oil supply chain where the pipeline mode is one of the most complex to operate when having multiproduct characteristics. This paper addresses the planning of a generic oil derivatives transportation system characterized by a multiproduct pipeline that connects a single refinery to a storage tank farm. Two alternative mixed integer linear programming models (MILP) that aim to attain a set of planning objectives such as fulfilling costumers’ demands (which is mandatory) while minimizing the medium flow rate are developed. Additionally, final inventory levels are avoided to be excessively low. A real world scenario of a Portuguese company is used to validate and compare the two alternative MILP models developed in this paper.     

Production planning and control in automated manufacturing systems

Automated manufacturing systems (AMSs) have the potential for providing a high level of manufacturing performance. Owing to the high cost of capital investment, a high utilization level of AMSs with the help of suitable production planning and control (PPC) is feature of AMSs. Realizing the potential of PPC in AMSs, an attempt has been made to review the available techniques/methods for solving the problems of production planning, control and scheduling in AMSs. The need for further research on PPC of AMSs is brought to the fore along with future research directions.     

Optimum common cycle for scheduling a single-machine multiproduct system with a budgetary constraint

This paper deals with the single machine multi-product lot size scheduling problem, and has two objectives. The first objective is to minimize the maximum aggregate inventory for the common cycle (CC) scheduling policy. A simple and easy-to-apply rule has been developed which determines the optimal production sequence that achieves this objective. The second objective is to find an optimal common cycle for minimizing the average production and inventory costs per unit time, subject to a given budgetary constraint. A method has been presented that achieves this objective     

Shop floor characteristics influencing the use of advanced planning and scheduling systems

The purpose of this article is to investigate how the manufacturing process, the shop type and the data quality, i.e. the shop floor characteristics, influence the use of advanced planning and scheduling (APS) systems in production activity and control (PAC). The methodology implemented is a multiple case study at three case companies. Each company has different shop floor characteristics, but all use a scheduling module in an APS system, which supports production scheduling. A theoretical framework is developed suggesting how APS system are used in the PAC activities, and which major aspect to consider. The case analysis shows that the scheduling module in APS system, foremost supports sequencing and dispatching. In particular, the shop type is influenced by the decision of how often the APS runs and what freedom is given to the shop floor. The manufacturing process influences how the dispatch list is created. Contrary to the literature presuming that APS systems are most suitable in job shop processes, it is found that the manufacturing process is not a crucial factor when deciding whether APS systems are an appropriate investment. It is found that the level of data quality needed in the APS system depends to a large extent on how the dispatch list is used. For example, is the dispatch list used as a guideline, not a regulation, the need for accurate data in the module is reduced. This article extends the previous literature concerning APS systems by analysing how APS systems influence PAC as a whole and increase the understanding of the challenges of using APS systems in PAC.     

An integrated modelling approach for raw material management in a steel mill

An integrated modelling approach combining optimisation models with simulation is proposed for coordinated raw material management at steel works throughout the whole supply chain management process. The integrated model is composed of three components: ship scheduling, yard operation simulation and material blending models. The ship scheduling model determines which brands, how much and when they should be arrived, and the problem is modelled as mixed integer linear programming. The simulation model is used to simulate the whole processes from ships’ arrivals to the retrieval of the materials through the berthing and unloading the raw materials. Finally, the raw material blending model is developed for determining the brand and quantity of raw materials to be used. The proposed integrated modelling approach for raw material management has been successfully implemented and applied at steelwork to provide shipping schedules and predict future inventory levels at stock yards. By coordinating all the activities throughout the entire raw material supply chain management process, this article proposes an integrated approach to the problem and suggests a guideline by the appropriate simplification. The quantitative nature of the optimisation model and simulation facilitates an assessment of the risk factors in the supply chain, leading to an evaluation of a wide variety of scenarios and the development of multiple contingency plans. Further research is expected to supplement the ship scheduling models with heuristics for the idiosyncratic constraints of maritime transportation.