Multi-objective and prioritized berth allocation in container ports

This paper considers a berth allocation problem (BAP) which requires the determination of exact berthing times and positions of incoming ships in a container port. The problem is solved by optimizing the berth schedule so as to minimize concurrently the three objectives of makespan, waiting time, and degree of deviation from a predetermined priority schedule. These objectives represent the interests of both port and ship operators. Unlike most existing approaches in the literature which are single-objective-based, a multi-objective evolutionary algorithm (MOEA) that incorporates the concept of Pareto optimality is proposed for solving the multi-objective BAP. The MOEA is equipped with three primary features which are specifically designed to target the optimization of the three objectives. The features include a local search heuristic, a hybrid solution decoding scheme, and an optimal berth insertion procedure. The effects that each of these features has on the quality of berth schedules are studied.     

Match-up scheduling under a machine breakdown

When a machine breakdown forces a modified flow shop (MFS) out of the prescribed state, the proposed strategy reschedules part of the initial schedule to match up with the preschedule at some point. The objective is to create a new schedule that is consistent with the other production planning decisions like material flow, tooling and purchasing by utilizing the time critical decision making concept. We propose a new rescheduling strategy and a match-up point determination procedure through a feedback mechanism to increase both the schedule quality and stability. The proposed approach is compared with alternative reactive scheduling methods under different experimental settings.     

Simulation of human ischemic stroke in realistic 3D geometry

In silico research in medicine is thought to reduce the need for expensive clinical trials under the condition of reliable mathematical models and accurate and efficient numerical methods. In the present work, we tackle the numerical simulation of reaction–diffusion equations modeling human ischemic stroke. This problem induces peculiar difficulties like potentially large stiffness which stems from the broad spectrum of temporal scales in the nonlinear chemical source term as well as from the presence of steep spatial gradients in the reaction fronts, spatially very localized. Furthermore, simulations on realistic 3D geometries are mandatory in order to describe correctly this type of phenomenon. The main goal of this article is to obtain, for the first time, 3D simulations on realistic geometries and to show that the simulation results are consistent with those obtain in experimental studies or observed on MRI images in stroke patients.For this purpose, we introduce a new resolution strategy based mainly on time operator splitting that takes into account complex geometry coupled with a well-conceived parallelization strategy for shared memory architectures. We consider then a high order implicit time integration for the reaction and an explicit one for the diffusion term in order to build a time operator splitting scheme that exploits efficiently the special features of each problem. Thus, we aim at solving complete and realistic models including all time and space scales with conventional computing resources, that is on a reasonably powerful workstation. Consequently and as expected, 2D and also fully 3D numerical simulations of ischemic strokes for a realistic brain geometry, are conducted for the first time and shown to reproduce the dynamics observed on MRI images in stroke patients. Beyond this major step, in order to improve accuracy and computational efficiency of the simulations, we indicate how the present numerical strategy can be coupled with spatial adaptive multiresolution schemes. Preliminary results in the framework of simple geometries allow to assess the proposed strategy for further developments.     

Yard template planning in transshipment hubs under uncertain berthing time and position

This paper is concerned with yard management in transshipment hubs, where a consignment strategy is often used to reduce reshuffling and vessel turnaround time. This strategy groups unloaded containers according to their destination vessels. In this strategy, yard template determines the assignment of the spaces (sub-blocks) in the yard to the vessels. This paper studies how to make a good yard template under uncertain environment, for example, uncertain berthing time and berthing positions of the arriving vessels. To reduce the potential traffic congestion of prime movers, the workload distribution of sub-blocks within the yard is considered. A mixed integer programming model is formulated to minimize the expected value of the route length of container transshipping flows in the yard. Moreover, a heuristic algorithm is developed for solving the problem in large-scale realistic environments. Numerical experiments are conducted to validate the efficiency of the proposed algorithm.     

Some Remarks on the Convex Feasibility Problem and Best Approximation Problem

In this paper we investigate several solution algorithms for the convex fea- sibility problem(CFP)and the best approximation problem(BAP)respectively.The algorithms analyzed are already known before,but by adequately reformulating the CFP or the BAP we naturally deduce the general projection method for the CFP from well-known steepest decent method for unconstrained optimization and we also give a natural strategy of updating weight parameters.In the linear case we show the connec- tion of the two projection algorithms for the CFP and the BAP respectively.In addition, we establish the convergence of a method for the BAP under milder assumptions in the linear case.We also show by examples a Bauschke's conjecture is only partially correct.     

不确定环境下基于时间、费用及鲁棒性权衡的多目标项目调度优化

项目调度中的时间和费用是两个重要的指标,而在不确定环境下进度计划的鲁棒性则是保证项目平稳实施的关键。本文研究不确定环境下的多目标项目调度优化问题,以优化项目的工期、鲁棒值和成本为目标安排各活动的开始时间。基于此,作者构建多目标项目调度优化模型,将模型分解为三个子模型分析目标间的权衡关系,然后设计非劣排序遗传算法进行求解,应用精英保留策略和基于子模型权衡关系的优化策略优化算法,进行算法测试和算例参数敏感性分析。最后,应用上述方法研究一个项目实例,计算得到非劣解集,实例的敏感性分析结果进一步验证了三个目标间的权衡关系,据此提出资源的有效利用策略。本文的研究可以为多目标项目调度制定进度计划提供定量化决策支持。     

有服务时长和服务可选择性的快递车辆调度在线策略研究

针对快递揽件需求出现无法提前获知、服务每一个快递需求需要一定的服务时长,且无法接受全部请求的情形,提出带有服务时长和服务可选择性的快递车辆在线调度问题,证明了该问题在线策略竞争比的下界。在正半轴上提出Replan策略,在直线上提出ReOPT策略,在一般网络上提出GRH策略,证明了上述在线策略的竞争比。结果表明,考虑服务时长能够改善在线策略的竞争性能,所提在线策略在实际应用中具有实用性。结论将为快递车辆的科学调度提供理论依据。     

Group-shop scheduling with sequence-dependent set-up and transportation times

This paper considers a group-shop scheduling problem (GSSP) with sequence-dependent set-up times (SDSTs) and transportation times. The GSSP provides a general formulation including the job-shop and the open-shop scheduling problems. The consideration of set-up and transportation times is among the most realistic assumptions made in the field of scheduling. In this paper, we study the GSSP with transportation and anticipatory SDSTs, where jobs are released at different times and there are several transporters to carry jobs. The objective is to find a job schedule that minimizes the makespan, that is, the time at which all jobs are completed and transported to the warehouse (or to the customer). The problem is formulated as a disjunctive programming problem and then prepared in a form of mixed integer linear programming (MILP). Due to the non-deterministic polynomial-time hardness (NP-hardness) of the GSSP, large instances cannot be optimally solved in a reasonable amount of time. Therefore, a genetic algorithm (GA) hybridized with an active schedule generator is proposed to tackle large-sized instances. Both Baldwinian and Lamarckian versions of the proposed hybrid algorithm are then implemented and evaluated through computational experiments.     

考虑机器能耗的绿色作业车间调度问题

针对传统作业车间调度,在保证交货期的前提下,以机器能耗最小为目标研究带有关机/重启策略的绿色车间调度问题。首先建立数学规划模型,然后在遗传算法的框架下,根据问题特点提出了一种局部调整的解码方式,在排产时进行工序的移动并确定其开始加工时刻。最后进行小规模算例运算,验证数学规划模型的有效性,再利用算例对基于局部调整解码和顺序解码的遗传算法进行对比测试,结果表明提出的局部调整解码可以在降低机器能耗的同时提高求解效率。     

The stochastic U-line balancing problem: A heuristic procedure

Many heuristics have been proposed for the assembly line balancing problem due to its computational complexity and difficulty in identifying an optimal solution. Still, the basic line balancing model fails to consider a number of realistic elements. The implementation of a Just-In-Time manufacturing system generally entails the replacement of traditional straight assembly lines with U-shaped lines. An important issue in the U-line balancing problem is the consideration of task time variability due to human factors or various disruptions. In this paper, we consider the stochastic U-line balancing problem. A hybrid heuristic is presented consisting of an initial feasible solution module and a solution improvement module. To gain insight into its performance, we analyze the heuristic under different scenarios of task time variability. Computational results clearly demonstrate the efficiency and robustness of our algorithm.     

Optimal portfolio execution under time-varying liquidity constraints

In this article, we take an algorithmic approach to solve the problem of optimal execution under time-varying constraints on the depth of a limit order book (LOB). Our algorithms are within the resilience model proposed by Obizhaeva and Wang (2013) with a more realistic assumption on the order book depth; the amount of liquidity provided by an LOB market is finite at all times. For the simplest case where the order book depth stays at a fixed level for the entire trading horizon, we reduce the optimal execution problem into a one-dimensional root-finding problem which can be readily solved by standard numerical algorithms. When the depth of the order book is monotone in time, we apply the Karush-Kuhn-Tucker conditions to narrow down the set of candidate strategies. Then, we use a dichotomy-based search algorithm to pin down the optimal one. For the general case, we start from the optimal strategy subject to no liquidity constraints and iterate over execution strategy by sequentially adding more constraints to the problem in a specific fashion until primal feasibility is achieved. Numerical experiments indicate that our algorithms give comparable results to those of current existing convex optimization toolbox CVXOPT with significantly lower time complexity.     

不确定条件下双目标组批生产的交货期设置研究

交货期是调度方法的函数,因而具有不确定性.研究变批量、变批次、变生产能力下,单阶段、双目标有条件相容组批的交货期设置问题,将它转化为订单投放策略和调度模式研究.建立了一个基于目标的双目标订单投放策略数学模型.采用目标序列优先方法进行双目标求解,用两种调度模式求出区间值,进行最优交货期逼近.模式1:松弛掉产品加工约束条件,基于负荷考虑、给出离散生产模式下订单完工率最大的订单排序算法,算法综合考虑了任务紧急程度、可调度性、重要度和流程时间最短四个方面,得到区间的一个端点.模式2是有条件相容的启发式组批调度算法,即通过聚类计算将订单安排问题转化为多队列调度问题,将新来订单的投放转化为某个队列的插单和批量分割问题,不同队列中批的投产顺序由批中优先级最高的订单决定,并在能力约束下进行批量分割计算,得到区间的另一个端点,结合流程可靠性求出区间.实例证明,模式2的交货期设置小,订单完工率和生产率高.     

A penalty-shift-insertion-based algorithm to minimize total flow time in no-wait flow shops

This paper proposes a penalty-shift-insertion (PSI)-based algorithm for the no-wait flow shop scheduling problem to minimize total flow time. In the first phase, a penalty-based heuristic, derived from Vogel’s approximation method used for the classic transportation problem is used to generate an initial schedule. In the second phase, a known solution is improved using a forward shift heuristic. Then the third phase improves this solution using a job-pair and a single-job insertion heuristic. Results of the computational experiments with a large number of randomly generated problem instances show that the proposed PSI algorithm is relatively more effective and efficient in minimizing total flow time in a no-wait flow shop than the state-of-the-art procedures. Statistical significance of better results obtained by the proposed algorithm is also reported.     

Minimizing Weighted Number of Early and Tardy Jobs with a Common Due Window Involving Location Penalty

This paper studies a single machine scheduling problem to minimize the weighted number of early and tardy jobs with a common due window. There are n non-preemptive and simultaneously available jobs. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. The window size is a given parameter but the window location is a decision variable. The objective of the problem is to find a schedule that minimizes the weighted number of early and tardy jobs and the location penalty. We show that the problem is NP-complete in the ordinary sense and develop a dynamic programming based pseudo-polynomial algorithm. We conduct computational experiments, the results of which show that the performance of the dynamic algorithm is very good in terms of memory requirement and CPU time. We also provide polynomial time algorithms for two special cases.     

The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments

This paper studies a dynamic dial-a-ride problem bearing complex constraints on a time-dependent network. A flexible scheduling scheme is proposed to dynamically cope with different stochastic events, such as the travelling time fluctuation, new requests, absences of customers, vehicle breakdowns, cancellations of requests, traffic jams and so on. A fast heuristic is proposed to re-optimize the schedule when a new event occurs. This heuristic consists of a properly organized local search strategy and uses a secondary objective function to drive the search out of local optima. Intensive computational simulations were carried out to evaluate the performance of this scheduling scheme and the influence of different stochastic factors. The simulation results of different scenarios with different percentage of dynamic requests reveal that this scheduling scheme can generate high quality schedules and is capable of coping with various stochastic events.     

单机排序中关于完工前总损失的应急管理

该文研究了扰动环境下的关于完工前总损失的单机排序问题, 也就是这样一个问题: 在时刻 t , 一部分工件已经完工了, 一个扰动发生了, 在这种情形下, 原来的排序已经不是最优排序甚至是不可行排序了. 因此就需要对未完成的工件找一个新的排序. 作者采用的方法与大多数重新排序问题所不同的是: 模型里包含了原始排序与新排序之间的偏差所造成的损失. 作者主要研究了在原始排序中加权最短加工时间规则(WSPT)是最优排序的情形. 根据扰动的类型, 应急管理策略的类型以及目标函数, 研究了几个问题. 对于每个问题, 作者找到了最优排序或者得出了一些重要结果.     

具有质量差异的项目支付进度问题研究——以软件项目为例

目前带有惩罚结构的项目支付进度模型通常以时间或成本为激励因子,来约束承包商保证进度和节约成本,未考虑质量因素对支付进度的影响。质量是项目管理的主要目标和决定项目成败的关键因素,研究质量对项目支付进度的影响有助于激励承包商提高表现从而保证项目质量。以软件项目为例,以软件产品质量为激励因子, 分别从承包商和客户的角度构建现金流净现值最大化为目标的项目支付进度优化模型,分析承包商表现水平及风险规避对双方收益的影响。针对模型的特点设计了遗传算法和禁忌搜索算法的混合算法求解模型。最后通过算例分析表明, 质量激励因子对项目的支付进度和双方的收益均存在较大的影响,为双方协商支付进度提供决策支持。     

A particle swarm optimization for solving lot-sizing problem with fluctuating demand and preservation technology cost under trade credit

In this paper, we consider the effect of preservation technology cost investing on preservation equipment for reducing deterioration rate under two-level trade credit. The preservation technology cost is allowed for periodical upward or downward adjustments due to the time varying demand and the strategy of trade credit within the planning horizon. We establish a deterministic economic order quantity model for a retailer to determine his/her optimal preservation technology cost per replenishment cycle, the trade credit policies, the replenishment number and replenishment schedule that will maximize the present value of total profit. A particle swarm optimization with constriction factor is coded and used to solve the mixed-integer nonlinear programming problem by employing the properties derived from this paper. Some numerical examples are used to illustrate the features of the proposed model.     

Optimization of a highway project planning using a modified genetic algorithm

This paper proposes an optimization method for a national-level highway project planning based on a modified genetic algorithm. The proposed method adds to the existing methods by integrating various planning elements into a single system. A simulation model is used in order to determine the best investment strategy with regard to net present value, time deviation from the initial plan and discrepancy between available resources and investment costs by taking into account economical, social, traffic and political factors. The outcome is a project schedule with an optimized cash flow. The proposed method was tested using the example of the National Highway Programme in Slovenia.