A penalty-based heuristic algorithm for the permutation flowshop scheduling problem with sequence-dependent set-up times

This paper considers the permutation flowshop scheduling problem with sequence-dependent set-up times and develops a penalty-based heuristic algorithm to find an approximately minimum makespan schedule. The proposed algorithm determines the penalty in time associated with a particular sequence and selects the sequence with the minimum time penalty as the best heuristic solution. Computational results comparing the effectiveness and efficiency of the proposed penalty-based heuristic algorithm with an existing savings index heuristic algorithm are reported and discussed.     

A local relaxation method for the cardinality constrained portfolio optimization problem

The NP-hard nature of cardinality constrained mean-variance portfolio optimization problems has led to a number of different algorithms with varying degrees of success in reaching optimality given limited computational resources and under the presence of strict time constraints present in practice. The proposed local relaxation algorithm explores the inherent structure of the objective function. It solves a sequence of small, local, quadratic-programs by first projecting asset returns onto a reduced metric space, followed by clustering in this space to identify sub-groups of assets that best accentuate a suitable measure of similarity amongst different assets. The algorithm can either be cold started using a suitable heuristic method such as the centroids of initial clusters or be warm started based on the last output. Results, using a basket of up to 3,000 stocks and with different cardinality constraints, indicates that the proposed algorithm can lead to significant performance gain over popular branch-and-cut methods. One key application of this algorithm is in dealing with large scale cardinality constrained portfolio optimization under tight time constraint, such as for the purpose of index tracking or index arbitrage at high frequency.     

A real delivery problem dealt with Monte Carlo Techniques

In this paper we use Monte Carlo Techniques to deal with a real world delivery problem of a food company in Valencia (Spain). The problem is modeled as a set of 11 instances of the well known Vehicle Routing Problem, VRP, with additional time constraints. Given that VRP is a NP-hard problem, a heuristic algorithm, based on Monte Carlo techniques, is implemented. The solution proposed by this heuristic algorithm reaches distance and money savings of about 20% and 5% respectively. This work has been partially supported by thePlan de Incentivo a la Investigación/98 of the Universidad Politécnica de Valencia, under the project “Técnicas Monte Carlo aplicadas a Problemas de Rutas de Vehículos”.     

Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration

In this paper, we address a two-machine flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes total weighted completion time. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational analysis on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm.     

A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems

This paper approximately solves the high school timetabling problem using a simulated annealing based algorithm with a newly-designed neighborhood structure. In search for the best neighbor, the heuristic performs a sequence of swaps between pairs of time slots, instead of swapping two assignments as in a standard simulated annealing. The computational results show that the proposed heuristic, which is tested on two sets of benchmark instances, performs better than existing approaches.     

基于启发式Q学习的汽车涂装车间作业排序优化

针对汽车涂装车间中的作业优化排序问题,提出一种基于启发式Q学习的优化算法。首先,建立包括满足总装车间生产顺序和最小化喷枪颜色切换次数的多目标整数规划模型。将涂装作业优化排序问题抽象为马尔可夫过程,建立基于启发式Q算法的求解方法。通过具体案例,对比分析了启发式Q学习、Q学习、遗传算法三种方案的优劣。结果表明：在大规模问题域中,启发式Q学习算法具有寻优效率更高、效果更好的优势。本研究为机器学习算法在汽车涂装作业优化排序问题的应用提出了新思路。     

A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times

This article proposes lower bounds, as well as a divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times (MSPS). The heuristic is tested on randomly generated instances and compared with a previously published tabu search algorithm. Results show that the proposed heuristic is much faster than tabu search while providing similar quality solutions.     

Minimizing the Number of Machine Idle Intervals with Minimum Makespan in a Flow-Shop

This paper considers a selected sequence in a permutation flow-shop. The objective is to minimize the number of machine idle intervals with minimum makespan (or total production time) for this selected sequence. There are at least two advantages of minimizing the number of machine idle intervals. The first reduces the number of times necessary to restart machines. The second achieves a longer period of idle time for each idle interval, and hence the idle time may be used more efficiently. An integer programming formulation is presented to provide the optimal solution. A heuristic algorithm is also proposed to solve large-sized problems. The heuristic finds the optimal solution for the three-machine case and is found to provide the optimal or near-optimal solution for other cases.     

Single-machine total completion time scheduling with a time-dependent deterioration

In this paper, we consider the single-machine scheduling problems with a time-dependent deterioration. By the time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. The objective is to minimize the total completion time. We develop a mixed integer programming formulation for the problem. The complexity status of this problem remains open. Hence, we use the smallest normal processing time (SPT) first rule as a heuristic algorithm for the general cases and analyze its worst-case error bound. Two heuristic algorithms utilize the V-shaped property are also proposed to solve the problem. Computational results are presented to evaluate the performance of the proposed algorithms.     

Vehicle routing and scheduling with time-varying data: A case study

A heuristic algorithm is described for vehicle routing and scheduling problems to minimise the total travel time, where the time required for a vehicle to travel along any road in the network varies according to the time of travel. The variation is caused by congestion that is typically greatest during morning and evening rush hours. The algorithm is used to schedule a fleet of delivery vehicles operating in the South West of the United Kingdom for a sample of days. The results demonstrate how conventional methods that do not take time-varying speeds into account when planning, except for an overall contingency allowance, may still lead to some routes taking too long. The results are analysed to show that in the case study using the proposed approach can lead to savings in CO₂ emissions of about 7%.     

A heuristic multi-start decomposition approach for optimal design of serial machining lines

We study an optimal design problem for serial machining lines. Such lines consist of a sequence of stations. At every station, the operations to manufacture a product are grouped into blocks. The operations within each block are performed simultaneously by the same spindle head and the blocks of the same station are executed sequentially. The inclusion and exclusion constraints for combining operations into blocks and stations as well as the precedence constraints on the set of operations are given. The problem is to group the operations into blocks and stations minimizing the total line cost. A feasible solution must respect the given cycle time and all given constraints. In this paper, a heuristic multi-start decomposition approach is proposed. It utilizes a decomposition of the initial problem into several sub-problems on the basis of a heuristic solution. Then each obtained sub-problem is solved by an exact algorithm. This procedure is repeated many times, each time it starts with a new heuristic solution. Computational tests show that the proposed approach outperforms simple heuristic algorithms for large-scale problems.     

军事物流系统中定位-运输路线安排模型及算法

考虑到战时物资需求的紧迫性和保障资源的有限性,从决策者的角度出发,以军事物流系统总体供应时间最短为目标,构建了两级军事配送网络的定位-运输路线安排模型,并给出一种启发式算法.算法分为两个阶段,首先利用蚁群算法和线性规划的方法解决运输路线安排问题,然后运用贪婪搜索算法解决军事物流配送中心选址问题.最终,将两种算法结合起来进行逐步搜索,从而得到模型的解,并运用实例说明了算法的有效性和可行性.     

Single facility scheduling with multiple job classes

This paper considers a static single facility scheduling problem where jobs are divided into several mutually exclusive classes. The jobs in a given class need not be processed together. In addition to a known processing time for each job, there is a switching time involved which depends on the class of the job immediately preceding a job. A heuristic algorithm is proposed to find a minimum mean flow time schedule. The effectiveness of the proposed heuristic algorithm is empirically evaluated and found to indicate that the solutions obtained from this heuristic algorithm are often close to optimal.     

Scheduling and lot sizing models for the single-vendor multi-buyer problem under consignment stock partnership

We consider a centralized supply chain composed of a single vendor serving multiple buyers and operating under consignment stock arrangement. Solving the general problem is hard as it requires finding optimal delivery schedule to the buyers and optimal production lot sizes. We first provide a nonlinear mixed integer programming formulation for the general scheduling and lot sizing problem. We show that the problem is NP-hard in general. We reformulate the problem under the assumption of ‘zero-switch rule’. We also provide a simple sequence independent lower bound to the solution of the general model. We then propose a heuristic procedure to generate a near-optimal delivery schedule. We assess the cost performance of that heuristic by conducting sensitivity analysis on the key model parameters. The results show that the proposed heuristic promises substantial supply-chain cost savings that increase as the number of buyers increases.     

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.     

Charging scheduling problem of an M-to-N electric vehicle charger

This study investigates a real case of charging scheduling of an electric vehicle charger with multiple ports called M-to-N charger. The charger is designed for a multi-unit dwelling facility and can charge N electric vehicles simultaneously despite the supplied charging capacity being limited to only M electric vehicles. The electric vehicles arrive at the charger randomly and stay for their desired length of time, during which they must be charged as much as possible with minimum electric cost. The scheduling problem considers four objectives: maximizing the total charging amount, minimizing the total charging cost, minimizing the charging completion time, and maximizing the charging balance among the electric vehicles. A mixed-integer linear programming model and a relaxation-based heuristic algorithm are developed. Computational experiment results show that the proposed heuristic algorithm can generate schedules within 8 s for this case study by using an open-source linear programming solver. Compared with the mixed-integer programming algorithm, the proposed heuristic algorithm can provide solutions with less than 7% charging amount gap and 4% price gap. The proposed heuristic algorithm is successfully implemented in a real M-to-N charger.     

A school bus scheduling problem

This paper introduces a school bus scheduling problem wherein trips for each school are given. A trip consists of a sequence of bus stops and their designated school. Each school has its fixed time window within which trips should be completed. A school bus can serve multiple trips for multiple schools. The school bus scheduling problem seeks to optimize bus schedules to serve all the given trips considering the school time windows. We first model the problem as a vehicle routing problem with time windows (VRPTW) by treating a trip as a virtual stop. Two assignment problem based exact approaches are then proposed for special cases and a heuristic algorithm is proposed for more general cases. Benchmark problems and computational experiments are presented. Computational experiments show the effectiveness of the proposed approaches.     

最小化总反馈长度的耦合活动排程研究

耦合活动的排程直接影响新产品开发的周期和成本,因而受到了学者和研发管理人员的普遍关注。本文针对最小化总反馈长度这一耦合活动排程常用目标,将遗传算法与局部搜索算法相结合,提出了一种新的混合优化算法,并系统分析了参数对算法性能的影响。然后将算法应用到实际案例和大量随机算例中,实验结果表明混合优化算法较大幅度提高了现有局部搜索算法解的质量;同等情形下,混合优化算法所获得解比单纯运用遗传算法所获得解更好。     

A bicriteria flowshop scheduling with a learning effect

In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a two-machine flowshop. The objective is to find a sequence that minimizes a weighted sum of total completion time and makespan. Total completion time and makespan are widely used performance measures in scheduling literature. To solve this scheduling problem, an integer programming model with n² + 6n variables and 7n constraints where n is the number of jobs is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 30 jobs can be solved. A heuristic algorithm and a tabu search based heuristic algorithm are presented to solve large size problems. Experimental results show that the proposed heuristic methods can solve this problem with up to 300 jobs rapidly. According to the best of our knowledge, no work exists on the bicriteria flowshop with a learning effect.     

A simplex-based labelling algorithm for the linear fractional assignment problem

This paper constructs an algorithm to solve the fractional assignment problem. Algorithms that are currently used are mostly based on parametric approaches and must solve a sequence of optimization procedures. They also neglect the difficulties caused by degeneracy. The proposed algorithm performs optimization once and overcomes degeneracy. The main features of the algorithm are an effective initial heuristic approach, a simple labelling procedure and an implicit primal-dual schema. A numerical example is presented and demonstrates that the proposed algorithm is easy to apply. Computational results are compared with those from other developed methods. The results show that the proposed algorithm is efficient.