Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising.     

A METHODOLOGY FOR LABOR SCHEDULING IN A SERVICE OPERATING SYSTEM

In the increasingly competitive services sector, utilization of the labor force can make the difference between profits or losses. Until recently, service operations managers had a limited set of tools, most of them computer-based, for scheduling labor. This paper offers a manual heuristic for labor scheduling that outperforms traditional algorithmic solution approaches. Specifically, this study examines the problem of scheduling employees in service delivery system subject to demand variability. The manual heuristic proposed asigns full-time empolyees to weekly work schedules with the objective of minimizing the total number of labor hours scheduled. The performance of the manual heuristic is compared to the classical algorithmic solution and to a lower bound for a variety of demand distributions and system operating conditions. The heuristic is shown to produce a smaller work force than the classical approach in 106 of the 108 demand-operating condition patterns examined.     

Two approaches to solving the multi-depot vehicle routing problem with time windows in a time-based logistics environment

This paper presents a two-phase heuristic method that can be used to efficiently solve the intractable multi-depot vehicle routing problem with time windows. The waiting time that was ignored by previous researchers is considered in this study. The necessity of this consideration is verified through an initial experiment. The results indicate that the waiting time has a significant impact on the total distribution time and the number of vehicles used when solving test problems with narrow time windows. In addition, to fairly evaluate the performance of the proposed heuristic method, a meta-heuristic method, which extends the unified tabu search of Cordeau et al., is proposed. The results of a second experiment reveal that the proposed heuristic method can obtain a better solution in the case of narrow time windows and a low capacity ratio, while the proposed meta-heuristic method outperforms the proposed heuristic method, provided that wide time windows and a high capacity ratio are assumed. Finally, a well-known logistics company in Taiwan is used to demonstrate the method, and a comparison is made, which shows that the proposed heuristic method is superior to the current method adopted by the case company.     

Marginal analysis production planning

A forward looking with backward recourse production planning heuristic is developed using marginal analysis. In the search for a minimum cost solution, a set of rules derived by Kunreuther and Morton for determining planning horizons is employed. It is shown that the logic of the heuristic is similar to several dynamic lot-sizing models. The marginal analysis production planning (MAPP) heuristic is computationally more efficient than optimizing approaches and gives results that are generally less than 5% more expensive than the optimal solution. In addition, through the notion of level periods, the heuristic permits the user to easily investigate strategies where the work force size and daily production rate remain constant for a specified number of periods.     

The blocking job shop with rail-bound transportation

The blocking job shop with rail-bound transportation (BJS-RT) considered here is a version of the job shop scheduling problem characterized by the absence of buffers and the use of a rail-bound transportation system. The jobs are processed on machines and are transported from one machine to the next by mobile devices (called robots) that move on a single rail. The robots cannot pass each other, must maintain a minimum distance from each other, but can also “move out of the way”. The objective of the BJS-RT is to determine for each machining operation its starting time and for each transport operation its assigned robot and starting time, as well as the trajectory of each robot, in order to minimize the makespan. Building on previous work of the authors on the flexible blocking job shop and an analysis of the feasible trajectory problem, a formulation of the BJS-RT in a disjunctive graph is derived. Based on the framework of job insertion in this graph, a local search heuristic generating consistently feasible neighbor solutions is proposed. Computational results are presented, supporting the value of the approach.     

Cell-to-switch level planning in mobile wireless networks for efficient management of radio resources

A major step in effectively managing radio resources in a cellular network is to design an appropriate scheme for assigning cells to a location area (LA), serviced by a switch, and allocate resources for individual switches. However, this assignment is already proven in the literature to be an NP-hard problem [Merchant A, Sengupta B. Assignment of cells to switches in PCS networks. IEEE/ACM Transactions on Networking 3(5) (1995) 521–6] that requires efficient heuristic search techniques for obtaining real-time solutions. This work presents a state-space search technique, which is a variant of best first search heuristic technique. The algorithm called the block depth first search (BDFS), allocates cells to switches during switch level resource planning. Under various simulated performance criteria, we compare the performance of the proposed technique with other similar procedures in the literature. Our results indicate that the BDFS outperforms the meta-heuristic procedures in terms of both efficiency and quality of solutions. Hence, we conclude that our proposed technique can be effectively used for switch level planning leading to an efficient management of scarce radio resource in cellular networks.     

Scheduling aerial resource operations for the extinction of large-scale wildfires

The significant increase in large-scale wildfire events in recent decades, caused primarily by climate change, has resulted in a growing number of aerial resources being used in suppression efforts. Present-day management lacks efficient and scalable algorithms for complex aerial resource allocation and scheduling for the extinction of such fires, which is crucial to ensuring safety while maximizing the efficiency of operations. In this work, we present a Mixed Integer Linear Programming (MILP) optimization model tailored to large-scale wildfires for the daily scheduling of aerial operations. The main objective is to achieve a prioritized target water flow over all areas of operation and all time periods. Minimal target completion across individual areas and time periods and total water output are also maximized as secondary and ternary objectives, respectively. An efficient and scalable multi-start heuristic, combining a randomized greedy approach with simulated annealing employing large neighborhood search techniques, is proposed for larger instances. A diverse set of problem instances is generated with varying sizes and extinction strategies to test the approaches. Results indicate that the heuristic can achieve (near)-optimal solutions for smaller instances solvable by the MILP, and gives solutions approaching target water flows for larger problem sizes. The algorithm is parallelizable and has been shown to give promising results in a small number of iterations, making it applicable for both night-before planning and, more time-sensitive, early-morning scheduling.     

A heuristic for inventory management of slow-moving items

Abstract. The traditional approach in the study of inventory systems is to give more importance to items whose demands are either large or very difficult to forecast, discounting the importance of inventory items with small demand. The objective of this paper is to present a simple and practical heuristic to the slow-moving items problem. First we provide insight into previous work in this area and also give a brief outline of classical models in stochastic inventory theory. Then we present the proposed approach and detail the heuristic. We summarize the paper with an analysis of the simulation results and finish with the conclusions that are drawn from the results.     

Active Labour Market Programmes,Job Search and Job Finding in Denmark

This paper investigates whether the probability to search for a job and search intensity increase as the start of an Active Labour Market Programme (ALMP) approaches. Further, it investigates whether job search is correlated with job finding. Although previous studies have shown that the chance of job finding increases as the start of an ALMP approaches, it remains an open question what causes this ‘threat effect’. Results show that job search increases as programme start approaches and that there is a positive correlation between job search and job finding. The threat effect can therefore at least partly be attributed to increased job search.     

Automating Knowledge Acquisition and Refinement for Decision Support: A Connectionist Inductive Inference Model*

An important application of expert systems technology is to provide support for nonstructured decision making. Usually, nonstructured decision making is characterized by heavy reliance on heuristic knowledge, which is very difficult to articulate or document, and therefore traditional knowledge acquisition approaches are not very successful. The quality and effectiveness of an expert system supporting unstructured decision making is affected when traditional knowledge acquisition approaches are used. To alleviate this problem a model is proposed that combines inductive inference and neural network computing, and an example is presented that illustrates the potential of this model in unstructured decision support.     

Sequencing Rules for Productivity Improvements in Underground Coal Mining*

In this paper, we report on a unique two-machine, dynamic sequencing problem that was involved in a project designed to improve the productivity of underground coal mining operations. It was discovered that mine output was dependent on the particular sequence of faces the continuous miner and bolter worked. The problem is characterized by two unique features. First, the problem is unique because of the geological and safety constraints that must be satisfied by the sequence. Second, the scheduling problem is dynamic because the available job sets change as work progresses, and the production times change as coal is mined. Three heuristic approaches were developed and tested using mine parameters. The best heuristic had a worst case scenario of being within 2.7 percent of the optimal sequence and only a 1.1 percent chance of determining a better sequence. This heuristic resulted in an 8.1 percent productivity improvement.     

An integrated hybrid approach to the examination timetabling problem

This paper is derived from an interest in the development of automated approaches to tackle examination timetabling problems effectively. We propose a hybrid approach that incorporates effective heuristic operators within the great deluge algorithm. The latter was chosen because of consistently good performances being reported within the examination timetabling research domain. The additional heuristic procedures further enhance the overall effectiveness of this integrated hybrid approach. These procedures are drawn from methodologies that have appeared in the literature under term the “electromagnetic-like mechanism”. The aim is to move sample points towards a high quality solution while avoiding local optima by utilising a calculated force value. This value, which is calculated dynamically, is treated as a decay rate in determining the level within the great deluge algorithm. To evaluate the proposed algorithm, we carry out experimental work on two types of examination timetabling datasets. All the related results and analysis obtained illustrate that this hybrid approach is effective when compared with existing approaches in the literature.     

On the Rank-Based Selection Strategy for the Group Interview Problem*

For the so-called group interview problem in which several groups of choice alternatives are presented sequentially to the decision maker, the optimal selection strategy is derived that minimizes the expected rank of the selected choice or purchased product. For the case in which the sequence of groups can be rearranged by the decision maker, a simple heuristic procedure is proposed for obtaining a near-optimal sequence of groups, and the performance of the heuristic procedure in a Monte Carlo simulation is accessed. According to the heuristic procedure, the consumer is advised to visit smaller stores first and then move to larger stores later to increase the likelihood of finding a better product. Finally, the optimal selection strategy and the heuristic procedure are compared with those proposed by Chun, Moskowitz, and Plante (1993) and the problem of locating a new store in an area where there are several competing stores is discussed. The optimal selection strategy and the heuristic procedure can be applied to many sequential decision problems such as the consumer search and purchase process.     

Simulated annealing procedure for scheduling competing tasks in flexible manufacturing

This paper presents a simulated annealing SA procedure heuristic for the problem of scheduling N tasks on a machine equipped with an automatic tool changer to minimize the makespan time. The problem is first formulated as a symmetric travelling salesman problem TSP . A local search heuristic procedure is developed, then embedded into SA algorithm to enhance its performance. The implemented SA heuristic has the following features: an exponential acceptance function with non-monotonic cooling schedule, heuristic pre-processing, and a neighbourhood of changing the sequence of a small number of tasks and named the k-interchange procedure. The algorithm is compared with an exact solution method on a set of practical-sized problems. The proposed algorithm performed very well in terms of solution quality and computation time.     

A flexibly structured lot sizing heuristic for a static remanufacturing system

An effective planning of lot sizes is a key strategy to efficiently manage a combined manufacturing/remanufacturing system in the presence of substantial setup costs. Due to its complex interdependencies, optimal policies and solutions have not been identified so far, but several heuristic approaches have been analyzed in recent contributions. The main heuristic shortcuts are forcing equally sized lot sizes over the planning horizon as well as imposing a specific cycle structure, i.e., a sequence of manufacturing batches is followed by a sequence of remanufacturing batches. We are instead proposing a flexibly structured heuristic that allows for differently sized remanufacturing batches. We show in a comprehensive numerical study that our approach outperforms other existing approaches in more than half of all instances by up to 17%.     

Revised GRASP with path-relinking for the linear ordering problem

The linear ordering problem (LOP) is an NP\mathcal{NP}-hard combinatorial optimization problem with a wide range of applications in economics, archaeology, the social sciences, scheduling, and biology. It has, however, drawn little attention compared to other closely related problems such as the quadratic assignment problem and the traveling salesman problem. Due to its computational complexity, it is essential in practice to develop solution approaches to rapidly search for solution of high-quality. In this paper we propose a new algorithm based on a greedy randomized adaptive search procedure (GRASP) to efficiently solve the LOP. The algorithm is integrated with a Path-Relinking (PR) procedure and a new local search scheme. We tested our implementation on the set of 49 real-world instances of input-output tables (LOLIB instances) proposed in Reinelt (Linear ordering library (LOLIB) 2002). In addition, we tested a set of 30 large randomly-generated instances proposed in Mitchell (Computational experience with an interior point cutting plane algorithm, Tech. rep., Mathematical Sciences, Rensellaer Polytechnic Institute, Troy, NY 12180-3590, USA 1997). Most of the LOLIB instances were solved to optimality within 0.87 seconds on average. The average gap for the randomly-generated instances was 0.0173% with an average running time of 21.98 seconds. The results indicate the efficiency and high-quality of the proposed heuristic procedure.     

A hybrid heuristic for the uncapacitated single allocation hub location problem

The uncapacitated single allocation hub location problem (USAHLP), with the hub-and-spoke network structure, is a decision problem in regard to the number of hubs and location–allocation. In a pure hub-and-spoke network, all hubs, which act as switching points for internodal flows, are interconnected and none of the non-hubs (i.e., spokes) are directly connected. The key factors for designing a successful hub-and-spoke network are to determine the optimal number of hubs, to properly locate hubs, and to allocate the non-hubs to the hubs. In this paper two approaches to determine the upper bound for the number of hubs along with a hybrid heuristic based on the simulated annealing method, tabu list, and improvement procedures are proposed to resolve the USAHLP. Computational experiences indicate that by applying the derived upper bound for the number of hubs the proposed heuristic is capable of obtaining optimal solutions for all small-scaled problems very efficiently. Computational results also demonstrate that the proposed hybrid heuristic outperforms a genetic algorithm and a simulated annealing method in solving USAHLP.     

考虑人车混采的道路信息采集的路径规划研究

本文考虑了道路信息外业采集的任务要求,人车混采的采集方式以及路网特性等方面,为道路信息采集人员的路径规划建立了满足人车混采约束的整数规划模型;提出了分阶段的转化算法,将其逐步转化为有限时间容量限制的弧路径问题(TCARP)。TCARP问题是一种NP-hard问题,精确求解算法无法在合理时间内得到问题的最优解,因此本文设计了求解TCARP问题的两种快速启发式算法TPS和TUH及其随机化版本;考虑到实际采集问题的大规模特性,在两种快速启发式算法的基础上构造GRASP-PA寻优算法。最后分别结合不同规模的基准算例和实际采集算例证明了本文所构造的算法的有效性。     

无人仓系统储位分配问题的优化模型与算法

考虑到无人仓系统补货阶段货架上只有部分空余储位的特点，研究了补货商品储位分配问题的优化模型与算法。以同一货架上存放的商品之间关联度之和最大化为目标建立了混合整数规划模型；结合贪婪算法和邻域搜索算法设计了求解模型的两阶段方法。第一阶段利用贪婪算法求初始可行解；第二阶段利用邻域搜索算法对初始可行解进行优化。利用一个具体算例验证了邻域搜索算法的优化效果，结果显示，通过邻域搜索算法对初始可行解的优化，可以使目标函数值至少提升27%。进一步利用多个小规模算例分析了两阶段算法的近似比和求解速度，验证了算法的快速有效性。本文的研究结果不仅解决了货架初始状态非空情况下的储位分配问题，同样适合解决货架初始状态为空的情况，因此更加符合实际场景，可以作为无人仓管理信息系统的核心模型和算法。     

Testing Systems of Identical Components

We consider the problem of testing sequentially the components of a multi-component reliability system in order to figure out the state of the system via costly tests. In particular, systems with identical components are considered. The notion of lexicographically large binary decision trees is introduced and a heuristic algorithm based on that notion is proposed. The performance of the heuristic algorithm is demonstrated by computational results, for various classes of functions. In particular, in all 200 random cases where the underlying function is a threshold function, the proposed heuristic produces optimal solutions.