Using genetic algorithm for lot sizing and scheduling problem with arbitrary job volumes and distinct job due date considerations

This paper considers an integrated lot sizing and scheduling problem for a production–distribution environment with arbitrary job volumes and distinct due dates considerations. In the problem, jobs are firstly batch processed on a batching machine at production stage and then delivered to a pre-specified customer at the subsequent delivery stage by a capacitated vehicle. Each job is associated with a distinct due date and a distinct volume, and has to be delivered to the customer before its due date, i.e. delay is not allowed. The processing time of a batch is a constant independent of the jobs it contains. In production, a constant set-up time as well as a constant set-up cost is required before the first job of this batch is processed. In delivery, a constant delivery time as well as a constant delivery cost is needed for each round-trip delivery between the factory and the customer. Moreover, it is supposed that a job that arrives at the customer before its due date will incur a customer inventory cost. The objective is to find a coordinated lot sizing and scheduling scheme such that the total cost is minimised while guaranteeing a certain customer service level. A mixed integer formulation is proposed for this problem, and then a genetic algorithm is developed to solve it. To evaluate the performance of the proposed genetic algorithm, a lower bound on the objective value is established. Computational experiments show that the proposed genetic algorithm performs well on randomly generated problem instances.     

考虑交货期约束的平行机供应链排序问题

针对一个制造商和一个客户组成的供应链,考虑工件有交货期限约束且不允许延迟送达客户处,对平行机加工环境下的供应链排序问题进行了研究。为了实现从日常调度层面对工件加工和工件分批运送进行集成优化,首先,以运送所有工件的总运输成本最小化为目标,构建了问题的混合整数规划模型;然后,分析了问题的复杂性并针对工件的交货期限相同和工件的交货期限不同两种情形分别设计了多项式时间的启发式算法进行求解;最后,通过仿真实验验证了所提算法的有效性。     

Scheduling with compressible and stochastic release dates

In this work we study a one-machine scheduling problem which is featured by: (a) the release date of each job is compressible and stochastic, (b) each job has to be delivered before its due date (deadline) and (c) the manufacturer can expedite the production through overtime at an extra cost. The objective function of the scheduling problem is to minimize the total cost which includes the compressing cost and the overtime production cost. We propose a heuristic algorithm in which the stochastic problem is converted to the deterministic problem by a release-time “converting policy”. We coin a concept of a job's late-release-impact factor (LRIF) and we propose a LRIF based converting policy. We compare the LRIF based converting policy with the ones used in practice, and the numerical test shows that the LRIF based converting policy can obtain the schedule with the lowest actual total cost.     

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

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

A GPU-based Branch-and-Bound algorithm using Integer–Vector–Matrix data structure

Branch-and-Bound (B&B) algorithms are tree-based exploratory methods for solving combinatorial optimization problems exactly to optimality. These problems are often large in size and known to be NP-hard to solve. The construction and exploration of the B&B-tree are performed using four operators: branching, bounding, selection and pruning. Such algorithms are irregular which makes their parallel design and implementation on GPU challenging. Existing GPU-accelerated B&B algorithms perform only a part of the algorithm on the GPU and rely on the transfer of pools of subproblems across the PCI Express bus to the device. To the best of our knowledge, the algorithm presented in this paper is the first GPU-based B&B algorithm that performs all four operators on the device and subsequently avoids the data transfer bottleneck between CPU and GPU. The implementation on GPU is based on the Integer–Vector–Matrix (IVM) data structure which is used instead of a conventional linked-list to store and manage the pool of subproblems. This paper revisits the IVM-based B&B algorithm on the GPU, addressing the irregularity of the algorithm in terms of workload, memory access patterns and control flow. In particular, the focus is put on reducing thread divergence by making a judicious choice for the mapping of threads onto the data. Compared to a GPU-accelerated B&B based on a linked-list, the algorithm presented in this paper solves a set of standard flowshop instances on an average 3.3 times faster.     

基于价值密度和截止期的网格作业调度算法

对商业网格中的作业调度问题进行研究,采用作业的到达时间、计算量、预算和截止期4个参数定义作业的优先级。在此基础上提出基于价值密度和相对截止期的网格作业调度算法,并对其进行仿真。仿真结果表明,该算法在实现价值率、按时完成作业数和加权作业按时完成率3个性能指标上优于现有算法,兼顾了消费者和服务者的利益。     

Some algorithms of solving minimax multiprocessor scheduling problem

A problem of constructing schedules of minimal length without interrupts and switches is considered for a multiprocessor system, in which the job execution time depends on the processor assigned to the job. To solve this problem, the branch and bound method is developed. The method is based on efficient algorithms for calculating lower and upper bounds of minimal length of the schedule. For the particular case when processors are identical, their number is fixed and the directive deadline is given, a pseudo-polynomial algorithm is proposed for constructing the admissible schedule. The number of processors required for efficient parallelizing of the algorithm is found.     

An improved approximation algorithm for single machine scheduling with job delivery

In single machine scheduling with release times and job delivery, jobs are processed on a single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jobs. The vehicle can deliver at most c jobs in a shipment. The delivery completion time of a job is defined as the time in which the delivery batch containing the job is delivered to the customer and the vehicle returns to the machine. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. We provide an approximation algorithm for this problem which is better than that given in the literature, improving the performance ratio from 5/3 to 3/2.     

A backward elimination discrete optimization algorithm for model selection in spatio-temporal regression models

Regression models are used in geosciences to extrapolate data and identify significant predictors of a response variable. Criterion approaches based on the residual sum of squares (RSS), such as the Akaike Information Criterion, Bayesian Information Criterion (BIC), Deviance Information Criterion, or Mallows' Cp can be used to compare non-nested models to identify an optimal subset of covariates. Computational limitations arise when the number of observations or candidate covariates is large in comparing all possible combinations of the available covariates, and in characterizing the covariance of the residuals for each examined model when the residuals are autocorrelated, as is often the case in spatial and temporal regression analysis. This paper presents computationally efficient algorithms for identifying the optimal model as defined using any RSS-based model selection criterion. The proposed dual criterion optimal branch and bound (DCO B&B) algorithm is guaranteed to identify the optimal model, while a single criterion heuristic (SCH) B&B algorithm provides further computational savings and approximates the optimal solution. These algorithms are applicable both to multiple linear regression (MLR) and to response variables with correlated residuals. We also propose an approach for iterative model selection, where a single set of covariance parameters is used in each iteration rather than a different set of parameters being used for each examined model. Simulation experiments are performed to evaluate the performance of the algorithms for regression models, using MLR and geostatistical regression as prototypical regression tools and BIC as a prototypical model selection approach. Results show massive computational savings using the DCO B&B algorithm relative to performing an exhaustive search. The SCH B&B is shown to provide a good approximation of the optimal model in most cases, while the DCO B&B with iterative covariance parameter optimization yields the closest approximation to the DCO B&B algorithm while also providing additional computational savings.     

A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service

On-time shipment delivery is critical for just-in-time production and quick response logistics. Due to uncertainties in travel and service times, on-time arrival probability of vehicles at customer locations can not be ensured. Therefore, on-time shipment delivery is a challenging job for carriers in congested road networks. In this paper, such on-time shipment delivery problems are formulated as a stochastic vehicle routing problem with soft time windows under travel and service time uncertainties. A new stochastic programming model is proposed to minimize carrier’s total cost, while guaranteeing a minimum on-time arrival probability at each customer location. The aim of this model is to find a good trade-off between carrier’s total cost and customer service level. To solve the proposed model, an iterated tabu search heuristic algorithm was developed, incorporating a route reduction mechanism. A discrete approximation method is proposed for generating arrival time distributions of vehicles in the presence of time windows. Several numerical examples were conducted to demonstrate the applicability of the proposed model and solution algorithm.     

A novel genetic algorithm for solving production and transportation scheduling in a two-stage supply chain

This study considers the scheduling of products and vehicles in a two-stage supply chain environment. The first stage contains m suppliers with different production speeds, while the second stage is composed of l vehicles, each of which may have a different speed and different transport capacity. In addition, it is assumed that the various output products occupy different percentages of each vehicle’s capacity. We model the situation as a mixed integer programming problem, and, to solve it, we propose a gendered genetic algorithm (GGA) that considers two different chromosomes with non-equivalent structures. Our experimental results show that GGA offers better performance than standard genetic algorithms that feature a unique chromosomal structure. In addition, we compare the GGA performance with that of the most similar problem reported to date in the literature as proposed by Chang and Lee [Chang, Y., & Lee, C. (2004). Machine scheduling with job delivery coordination. European Journal of Operational Research, 158(2), 470–487]. The experimental results from our comparisons illustrate the promising potential of the new GGA approach.     

Integrated production and delivery with single machine and multiple vehicles

This paper considers a class of multi-objective production–distribution scheduling problem with a single machine and multiple vehicles. The objective is to minimize the vehicle delivery cost and the total customer waiting time. It is assumed that the manufacturer’s production department has a single machine to process orders. The distribution department has multiple vehicles to deliver multiple orders to multiple customers after the orders have been processed. Since each delivery involves multiple customers, it involves a vehicle routing problem. Most previous research work attempts at tackling this problem focus on single-objective optimization system. This paper builds a multi-objective mathematical model for the problem. Through deep analysis, this paper proposes that for each non-dominated solution in the Pareto solution set, the orders in the same delivery batch are processed contiguously and their processing order is immaterial. Thus we can view the orders in the same delivery batch as a block. The blocks should be processed in ascending order of the values of their average workload. All the analysis results are embedded into a non-dominated genetic algorithm with the elite strategy (PD-NSGA-II). The performance of the algorithm is tested through random data. It is shown that the proposed algorithm can offer high-quality solutions in reasonable time.     

基于遗传算法的Job Shop调度问题研究

在多平行工作站环境下,为使限定资源分配下的车间调度问题(Job Shop problem,JSP)具有最小总延迟时间;同时又可设定各订单具有不同的开工日(release date)及到期日,提出以可开工时间与结束时间为基础的分解解法,并在遗传算法的基础上构造混合遗传算法(hybrid genetic algorithm,HGA)来实现目标设定。实验结果表明,HGA在问题求解质量与Lingo解的最佳解差异在15%以内,并具备较基本型遗传算法更佳的稳定性。结果显示该算法可帮助管理人员实现智能资源配置与订单调度。     

Minimizing maximum tardiness and delivery costs in a batched delivery system

High delivery costs usually urge manufacturers to dispatch their jobs in batches. However, dispatching the jobs in batches can have profound negative effects on important scheduling objective functions such as minimizing maximum tardiness. This paper considers a single machine scheduling problem with the aim of minimizing the maximum tardiness and delivery costs in a single-machine scheduling problem with batched delivery system. A mathematical model is developed for this problem which can serve to solve it with the help of a commercial solver. However, due to the fact that this model happens to be a mixed integer nonlinear programming model the solver cannot guarantee to reach the global solution. For this reason, a branch and bound algorithm (B&B) is presented to obtain the global solution. Besides, a heuristic algorithm for calculation of the initial upper bound is introduced. Computational results show that the algorithm can be beneficial for solving this problem, especially for large size instances.     

Tabu search and lower bounds for a combined production–transportation problem

In this paper we consider a combined production–transportation problem, where n jobs have to be processed on a single machine at a production site before they are delivered to a customer. At the production stage, for each job a release date is given; at the transportation stage, job delivery should be completed not later than a given due date. The transportation is done by m identical vehicles with limited capacity. It takes a constant time to deliver a batch of jobs to the customer. The objective is to find a feasible schedule minimizing the maximum lateness.     

Single machine scheduling with job delivery to multiple customers

We investigate a single machine scheduling problem with job delivery to multiple customers. In this problem, each job needs to be processed on the single machine, and then delivered by a single vehicle to its customer, where the job has a physical size representing the fraction of space it occupies on the vehicle. The vehicle delivers a shipment from the machine to a customer and has to return back to the machine for delivering the next shipment. It takes different constant time for the round trips between the machine and the different customers. The goal is to minimize the makespan, by that time all the jobs are processed and delivered to their respective customers, and the vehicle returns back to the machine. We propose a 2-approximation algorithm for the general case; when there are only two customers, we present an improved 5/3-approximation algorithm. The design and performance analysis of these two algorithms integrate several known results and techniques for the single machine scheduling problem, the bin-packing problem, and the knapsack problem.     

Minimizing the number of tardy jobs under piecewise-linear deterioration

In this paper, we consider a single machine scheduling problem with piecewise-linear deterioration where its objective is to minimize the number of tardy jobs, in which the processing time of each job depends on its starting time where all the jobs have a specific deterioration rate. The problem is known to be NP-hard; therefore a Branch and Bound algorithm and a heuristic algorithm with O(n²) are proposed. The proposed heuristic algorithm has been utilized for solving large scale problems and upper bound of the B&B algorithm. Computational experiments on 1840 problems demonstrate that the Branch and Bound procedure can solve problems with 28 jobs and 85.4% of all the sample problems optimally showing the high capability of the proposed procedure. Also it is shown that the average value of the ratio of optimal answer to the heuristic algorithm result with the objective ∑(1-_Ui)$\sum (1-U_i)$ is at last 1.08 which is more efficient in contrast to other proposed algorithms in related studies in the literature. According to high efficacy of the heuristic algorithm, large scale samples are also being solved and the results are presented. A specific form of this problem is also being considered and it is proven that the B&B procedure can handle problems with more jobs even up to 44 jobs.     

METAHEURISTIC APPROACH FOR THE MULTI-DEPOT VEHICLE ROUTING PROBLEM

Distribution logistics comprises all activities related to the provision of finished products and merchandise to a customer. The focal point of distribution logistics is the shipment of goods from the manufacturer to the consumer. The products can be delivered to a customer directly either from the production facility or from the trader's stock located close to the production site or, probably, via additional regional distribution warehouses. These kinds of distribution logistics are mathematically represented as a vehicle routing problem (VRP), a well-known nondeterministic polynomial time (NP)-hard problem of operations research. VRP is more suited for applications having one warehouse. In reality, however, many companies and industries possess more than one distribution warehouse. These kinds of problems can be solved with an extension of VRP called multi-depot VRP (MDVRP). MDVRP is an NP-hard and combinatorial optimization problem. MDVRP is an important and challenging problem in logistics management. It can be solved using a search algorithm or metaheuristic and can be viewed as searching for the best element in a set of discrete items. In this article, cluster first and route second methodology is adapted and metaheuristics genetic algorithms (GA) and particle swarm optimization (PSO) are used to solve MDVRP. A hybrid particle swarm optimization (HPSO) for solving MDVRP is also proposed. In HPSO, the initial particles are generated based on the k-means clustering and nearest neighbor heuristic (NNH). The particles are decoded into clusters and multiple routes are generated within the clusters. The 2-opt local search heuristic is used for optimizing the routes obtained; then the results are compared with GA and PSO for randomly generated problem instances. The home delivery pharmacy program and waste-collection problem are considered as case studies in this paper. The algorithm is implemented using MATLAB 7.0.1.     

A branch and bound algorithm for the response time variability problem

The response time variability problem (RTVP) is an NP-hard scheduling problem that has been studied intensively recently and has a wide range of real-world applications in mixed-model assembly lines, multithreaded computer systems, network environments and others. The RTVP arises whenever products, clients or jobs need to be sequenced in order to minimise the variability in the time between two successive points at which they receive the necessary resources. To date, the best exact method for solving this problem is a mixed integer linear programming (MILP) model, which solves to optimality most of instances with up to 40 units to be scheduled in a reasonable amount of time. The goal of this paper is to increase the size of the instances that can be solved to optimality. We have designed an algorithm based on the branch and bound (B&B) technique to take advantage of the particular features of the problem. Our computational experiments show that the B&B algorithm is able to solve larger instances with up to 55 units to optimality in a reasonable time.     

A group priority earliest deadline first scheduling algorithm

In most priority scheduling algorithms, the number of priority levels is assumed to be unlimited. However, if a task set requires more priority levels than the system can support, several jobs must in practice be assigned the same priority level. To solve this problem, a novel group priority earliest deadline first (GPEDF) scheduling algorithm is presented. In this algorithm, a schedulability test is given to form a job group, in which the jobs can arbitrarily change their order without reducing the schedulability. We consider jobs in the group having the same priority level and use shortest job first (SJF) to schedule the jobs in the group to improve the performance of the system. Compared with earliest deadline first (EDF), best effort (BE), and group-EDF (gEDF), simulation results show that the new algorithm exhibits the least switching, the shortest average response time, and the fewest required priority levels. It also has a higher success ratio than both EDF and gEDF.