A time-dependent multiple criteria single-machine scheduling problem

We introduce a nonpreemptive single-machine scheduling model with time-dependent multiple criteria. We formulate the problem as a knapsack problem and propose a dynamic programming (DP)-based algorithm to finding all efficient schedules. An illustrative example is enclosed.     

Makespan minimization for parallel machines scheduling with multiple availability constraints

The problem of makespan minimization for parallel machines scheduling with multiple planned nonavailability periods in the case of resumable jobs is considered. In the current state of the literature, there is a limited number of models and algorithms dealing with this problem and only for very small problem size, and nonavailability limited to some machines. The problem is first formulated as a mixed integer linear programming model and optimally solved using CPLEX for small to moderately large size problems with multiple availability constraints on all machines. An implicit enumeration algorithm using the lexicographic order is then designed to solve large-scale problems. Numerical results are obtained for several experiments and they show the validity and performance improvements procured by both the MILP model and the new enumeration algorithm.     

考虑碳排放的多机可持续调度问题

考虑多机器生产环境下,研究在加工空档期允许关闭机器的可持续调度问题。同时对工件的指派、工件的开始加工时刻和机器在空档期是否开关机进行决策,以最小化碳排放为目标建立数学规划模型。设计了禁忌搜索混合算法求解模型,首先通过一个企业案例验证了模型和算法的有效性,然后通过仿真算例分析了算法的效率。计算结果表明,可持续调度方式在机器调度层面为企业减少了大量的碳排放。     

考虑空重箱转换的港口集装箱甩挂运输问题研究

针对港口堆场与内陆腹地客户之间的空重集装箱运输问题,本文结合甩挂运输的特点将客户的进出港需求拆分为相互关联的空箱和重箱任务,实现单个决策期内运输系统中集装箱的状态转换与回收工作。状态转换受集装箱货物装卸时间影响,因此需要合理调度牵引车路线,以满足前置任务约束。针对此类问题的特点,本文建立了空重箱运输任务整合的整数规划模型,并设计了基于集群选择的改进蚁群算法进行求解。最后,通过不同规模的仿真算例与现有数学模型及优化算法对比结果可知,本文所提出的改进蚁群算法在此类问题的最优解搜索中具有良好的稳定性和求解效率。     

基于动态列生成算法的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

基于情景分析的应急疏散车辆配置模型

在情景模式影响疏散点疏散人员数量及疏散最晚完成时间限制的条件下,研究了避难所应急疏散车辆配置计划及各种情景模式下的车辆出车任务安排,以疏散车辆出车安排为下层模型,以期望疏散总时间最小化车辆配置计划为上层模型建立了车辆配置及出车任务安排的双层规划模型。设计了结合CPLEX内置算法的模拟退火算法,最后用算例进行了仿真研究。     

随机活动工期下求解资源约束项目最大期望净现值的动态调度算法

本文研究了随机活动工期下如何调度资源约束项目使得项目的期望净现值最大。首先对问题进行了界定,建立了相应的优化模型,其次针对问题的特点设计了一种动态规划算法。在算法设计的过程中,本文通过对项目网络图结构及不同状态最优值之间关系的分析,优化了动态规划算法状态的生成过程及状态最优值的求解过程,从而加快了算法的求解。使用随机生成的540个不同规模、不同结构的仿真案例对算法的有效性进行了验证,并分析了项目网络特征对算法效率的影响。实验发现：项目的次序强度对算法所需时间有着较大的影响,随着项目次序强度的减小,生成的状态数量会增加,从而计算时间也会增加。本文的研究可以为不确定环境下的项目调度提供决策支持。     

智能制造环境下的备件生产与运输协同调度问题研究

智能制造和即时配送环境下的备件生产与运输协同调度问题是目前国内研究的一大热点,这是因为备件供应链响应速度已成为当前备件制造企业赢得客户的关键因素。为了提高客户满意度,尽可能缩短从客户下达定制化生产订单到订单配送完成的时间,本文建立了以所有客户总等待时间最短为目标的混合整数规划模型和集合覆盖模型,推导了最优解性质,并设计改进的分支定价算法求得最优解。通过将小规模算例结果与CPLEX进行对比,验证了模型和算法的有效性。多组算例测试结果表明,所提出的模型和算法可以有效提升智能制造环境下的备件供应链运作效率。     

Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays

This paper addresses a certain type of scheduling problem that arises when a parallel computation is to be executed on a set of identical parallel processors. It is assumed that if two precedence-related tasks are processed on two different processors, due to the information transferring, there will be a task-dependent communication delay between them. For each task, a processing time, a due date and a weight is given while the goal is to minimize the total weighted late work. An integer linear mathematical programming model and a branch-and-bound algorithm have been developed for the proposed problem. Comparing the results obtained by the proposed branch-and-bound algorithm with those obtained by CPLEX, indicates the effectiveness of the method.     

稀疏线性规划研究

稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题;其次采用交替方向乘子法(ADMM)求解该问题;最后证明了算法在近似问题上的收敛性.数值实验表明,算法在大规模数值算例上的表现优于已有的混合遗传算法;同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性.     

A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem

This paper considers the mobile facility routing and scheduling problem with stochastic demand (MFRSPSD). The MFRSPSD simultaneously determines the route and schedule of a fleet of mobile facilities which serve customers with uncertain demand to minimize the total cost generated during the planning horizon. The problem is formulated as a two-stage stochastic programming model, in which the first stage decision deals with the temporal and spatial movement of MFs and the second stage handles how MFs serve customer demands. An algorithm based on the multicut version of the L-shaped method is proposed in which several lower bound inequalities are developed and incorporated into the master program. The computational results show that the algorithm yields a tighter lower bound and converges faster to the optimal solution. The result of a sensitivity analysis further indicates that in dealing with stochastic demand the two-stage stochastic programming approach has a distinctive advantage over the model considering only the average demand in terms of cost reduction.     

Power generator scheduling by dynamic programming

Dynamic programming is applied to the problem of determining an optimal short-run schedule for a series of power generating units to meet a time varying system load. Typical scheduling procedures include a priority ordering constraint which requires that units be committed to or removed from power production in a fixed order. A dynamic programming model which relaxes this constraints yields a large combinatorial problem whose state space depends on the number of feasible combinations of generating units. Reduction of storage requirements is achieved through the implementation of data structure techniques. An example of the dynamic programming procedure with data from an actual system suggests significant coast reductions. A comparison with a case in the literature also results in significant savings. Perhaps more important, however, are the substantial energy savings, in light of the current emphasis on energy conservation.     

Machine scheduling with resource dependent processing times

We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with Graham’s list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algorithm for bin packing. We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming relaxations.     

Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints

This paper considers a single machine scheduling problem with the learning effect and multiple availability constraints that minimizes the total completion time. To solve this problem, a new binary integer programming model is presented, and a branch-and-bound algorithm is also developed for solving the given problem optimally. Since the problem is strongly NP-hard, to find the near-optimal solution for large-sized problems within a reasonable time, two meta-heuristics; namely, genetic algorithm and simulated annealing are developed. Finally, the computational results are provided to compare the result of the binary integer programming, branch-and-bound algorithm, genetic algorithm and simulated annealing. Then, the efficiency of the proposed algorithms is discussed.     

Optimizing the supply chain configuration for make-to-order manufacturing

We consider a make-to-order (MTO) manufacturer who has won multiple contracts with specified quantities to be delivered by certain due dates. Before production starts, the company must configure its supply chain and make sourcing decisions. It also needs to plan the starting time for each production task under limited availability of resources such as machines and workforce. We develop a model for simultaneously optimizing such sourcing and planning decisions while exploiting their tradeoffs. The resulting multi-mode resource-constrained project scheduling problem (MMRCPSP) with a nonlinear objective function is NP-complete. To efficiently solve it, a hybrid Benders decomposition (HBD) algorithm combining the strengths of both mathematical programming and constraint programming is developed. The HBD exploits the structure of the model formulation and decomposes it into a relaxed master problem handled by mixed-integer nonlinear programming (MINLP), and a scheduling feasibility sub-problem handled by constraint programming (CP). Cuts are iteratively generated by solving the feasibility sub-problem and added back to the relaxed master problem, until an optimal solution is found or infeasibility is proved. Computational experiments are conducted to examine performance of the model and algorithm. Insights about optimal configuration of MTO supply chains are drawn and discussed.     

工件优先级图为非连接图且含环的单机总加权拖期调度问题

为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。     

Hybrid simulated annealing and MIP-based heuristics for stochastic lot-sizing and scheduling problem in capacitated multi-stage production system

This paper addresses lot sizing and scheduling problem of a flow shop system with capacity constraints, sequence-dependent setups, uncertain processing times and uncertain multi-product and multi-period demand. The evolution of the uncertain parameters is modeled by means of probability distributions and chance-constrained programming (CCP) theory. A new mixed-integer programming (MIP) model with big bucket time approach is proposed to formulate the problem. Due to the complexity of problem, two MIP-based heuristics with rolling horizon framework named non-permutation heuristic (NPH) and permutation heuristic (PH) have been performed to solve this model. Also, a hybrid meta-heuristic based on a combination of simulated annealing, firefly algorithm and proposed heuristic for scheduling is developed to solve the problem. Additionally, Taguchi method is conducted to calibrate the parameters of the meta-heuristic and select the optimal levels of the algorithm’s performance influential factors. Computational results on a set of randomly generated instances show the efficiency of the hybrid meta-heuristic against exact solution algorithm and heuristics.     

Four-Day Workweek Scheduling with Two or Three Consecutive Days Off

A four-day workweek days-off scheduling problem is considered. Out of the three days off per week for each employee, either two or three days must be consecutive. An optimization algorithm is presented which starts by utilizing the problem's special structure to determine the minimum workforce size. Subsequently, workers are assigned to different days-off work patterns in order to minimize either the total number or the total cost of the workforce. Different procedures must be followed in assigning days-off patterns, depending on the characteristics of labor demands. In some cases, optimum days-off assignments are determined without requiring mathematical programming. In other cases, a workforce size constraint is added to the integer programming model, greatly improving computational performance.