A constructive heuristic for staff scheduling in the glass industry

In this paper a constructive heuristic for solving the staff scheduling problem of a glass manufacture unit is proposed. Based on simple calculations and algorithms, the developed procedure assigns working shifts and days-off to teams of employees, ensuring the satisfaction of a mandatory sequence of working shifts and the balance of the workload between employees. The computational times for the experiments with the case study company, with three eight-hour working shifts and five teams of employees, fell consistently below 5 seconds for a set of different planning periods. Results are compared with the ones achieved with an optimization model (MIP), demonstrating the good performance of the heuristic, also in terms of the quality of the achieved solutions. The heuristic rarely fails to produce a feasible solution and whenever the solution is feasible then it is also optimal. When tackling problems with a large number of teams, the heuristic maintains the good performance while the MIP model is not able to find any solution within 16 hours of running time. Although it was designed for a particular problem of the glass industry, tests show that the heuristic is flexible enough to be applied to problems with different features, from other activity sectors, encouraging further extensions of this work.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).     

Fair measures of performance: the World Cup of cricket

Luck can play a big part in tournament success, and progress is not necessarily the best measure of performance. A linear model is used to fit least squares ratings to margins of victory in the cricket World Cup. The Duckworth/Lewis rain interruption rules are used to project a winning second innings score and create a margin of victory in runs, equivalent to that used when the team batting first wins. Results show that, while the better teams progressed through the first round of the competition, some injustices occurred in the Super-Six round. This appears to be due to the double counting of selected matches. Ordering teams by average margin of victory gives similar results to the more complicated linear model, and its use as a tie breaker is suggested. Publication of the margin of victory as estimated by the Duckworth/Lewis method for second innings victories in all one-day matches would provide a common margin of victory suitable for analysis.     

Heuristic concentration: Two stage solution construction

By utilizing information from multiple runs of an interchange heuristic we construct a new solution that is generally better than the best local optimum previously found. This new, two stage, approach to combinatorial optimization is demonstrated in the context of the p-median problem. Two layers of optimization are superimposed. The first layer is a conventional heuristic the second is a heuristic or exact procedure which draws on the concentrated solution set generated by the initial heuristic. The intention is to provide an alternative heuristic procedure which, when dealing with large problems, has a higher probability of producing optimal solutions than existing methods. The procedure is fairly general and appears to be applicable to combinatorial problems in a number of contexts.     

Solving a manpower scheduling problem for airline catering using metaheuristics

We study a manpower scheduling problem with job time windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take-off. Jobs (flights) must be serviced within a given time-window by a team consisting of a driver and loader. Each driver/loader has the skills to service some, but not all, of the airline/aircraft/configuration of the jobs. Given the jobs to be serviced and the roster of workers for each shift, the problem is to form teams and assign teams and start-times for the jobs, so as to service as many flights as possible. Only teams with the appropriate skills can be assigned to a flight. Workload balance among the teams is also a consideration. We present model formulations and investigate a tabu search heuristic and a simulated annealing heuristic approach to solve the problem. Computational experiments show that the tabu search approach outperforms the simulated annealing approach, and is capable of finding good solutions.     

Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic

In this paper we propose an approach for solving problems of optimal resource capacity allocation to a collection of stochastic dynamic competitors. In particular, we introduce the knapsack problem for perishable items, which concerns the optimal dynamic allocation of a limited knapsack to a collection of perishable or non-perishable items. We formulate the problem in the framework of Markov decision processes, we relax and decompose it, and we design a novel index-knapsack heuristic which generalizes the index rule and it is optimal in some specific instances. Such a heuristic bridges the gap between static/deterministic optimization and dynamic/stochastic optimization by stressing the connection between the classic knapsack problem and dynamic resource allocation. The performance of the proposed heuristic is evaluated in a systematic computational study, showing an exceptional near-optimality and a significant superiority over the index rule and over the benchmark earlier-deadline-first policy. Finally we extend our results to several related revenue management problems.     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

Analysis of a linearization heuristic for single-machine scheduling to maximize profit

We consider the problem of schedulingn jobs without preemption on a single machine to maximize total profit, where profit is given by a nonincreasing, concave separable function of job starting times. A heuristic is given in which jobs are sequenced optimally relative to a specific linear approximation of the profit, function. This heuristic always obtains at least 2/3 of the optimal profit, and examples exist where the heuristic obtains only 2/3 of the optimal profit. A large class of alternative linearizations is considrred and shown to give arbitrarily bad results. Work supported in part by NSF Grant ECS 82-05438 to the University of Pennsylvania and ONR Contract N00014-81-C-0302.     

Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem

We study a static stochastic single machine scheduling problem in which jobs have random processing times with arbitrary distributions, due dates are known with certainty, and fixed individual penalties (or weights) are imposed on both early and tardy jobs. The objective is to find an optimal sequence that minimizes the expected total weighted number of early and tardy jobs. The general problem is NP-hard to solve; however, in this paper, we develop certain conditions under which the problem is solvable exactly. An efficient heuristic is also introduced to find a candidate for the optimal sequence of the general problem. Our illustrative examples and computational results demonstrate that the heuristic performs well in identifying either optimal sequences or good candidates with low errors. Furthermore, we show that special cases of the problem studied here reduce to some classical stochastic single machine scheduling problems including the problem of minimizing the expected weighted number of early jobs and the problem of minimizing the expected weighted number of tardy jobs which are both solvable by the proposed exact or heuristic methods.     

A note on the minimum bounded edge-partition of a tree

Minimum bounded edge-partition divides the edge set of a tree into the minimum number of disjoint connected components given a maximum weight for any component. It is an adaptation of the uniform edge-partition of a tree. An optimization algorithm is developed for this NP-hard problem, based on repeated bin packing of inter-related instances. The algorithm has linear running time for the class of ‘balanced trees’ common for the stochastic programming application which motivated investigation of this problem.Fast 2-approximation algorithms are formed for general instances by replacing the optimal bin packing with almost any bin packing heuristic. The asymptotic worst-case ratio of these approximation algorithms is never better than the absolute worst-case ratio of the bin packing heuristic used.     

考虑订单合并和货物转运的多式联运路径优化研究

为了获得运输的规模经济效应,本文研究了一种考虑订单合并和货物转运的零担多式联运路径优化问题。首先,以总运输成本为目标函数,以网络中的运输工具容量、可以提供的运输工具最大数量、运输工具服务的关闭时间以及订单时间窗为约束,构建混合整数规划模型,在模型中允许多个订单进行合并运输并考虑运输过程中的转运成本。其次,由于多式联运路径优化问题是典型的NP-hard问题,为了快速求解该模型,开发了一种可以快速为该问题提供近似最优解和下界的列生成启发式算法。最后,生成并测试了大量算例,结果表明所开发的列生成启发式算法可以在较短的时间内提供高质量的近似最优解。文章所构建的模型和开发的列生成启发式算法可以为零担自营多式联运物流企业提供高效的决策支持。     

Nonconvex piecewise linear knapsack problems

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.     

Generating quadratic assignment test problems with known optimal permutations

The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem of which the travelling-salesman problem is a special case. Although the QAP has been extensively studied during the past three decades, this problem remains very hard to solve. Problems of sizes greater than 15 are generally impractical to solve. For this reason, many heuristics have been developed. However, in the literature, there is a lack of test problems with known optimal solutions for evaluating heuristic algorithms. Only recently Paulubetskis proposed a method to generate test problems with known optimal solutions for a special type of QAP. This paper concerns the generation of test problems for the QAP with known optimal permutations. We generalize the result of Palubetskis and provide test-problem generators for more general types of QAPs. The test-problem generators proposed are easy to implement and were also tested on several well-known heuristic algorithms for the QAP. Computatinal results indicate that the test problems generated can be used to test the effectiveness of heuristic algorithms for the QAP. Comparison with Palubetskis' procedure was made, showing the superiority of the new test-problem generators. Three illustrative test problems of different types are also provided in an appendix, together with the optimal permutations and the optimal objective function values.     

Designing greedy algorithms for the flow-shop problem by means of Empirically Adjusted Greedy Heuristics (EAGH)

This paper introduces Empirically Adjusted Greedy Heuristics (EAGH), a procedure for designing greedy algorithms for a given combinatorial optimization problem and illustrates the way in which EAGH works with an application to minimize the makespan in the permutation flow-shop problem. The basic idea behind EAGH is that a greedy heuristic can be seen as a member of an infinite set of heuristics, this set being defined by a function that depends on several parameters. Each set of values of the parameters corresponds to a specific greedy heuristic. Then, the best element of the set, for a training set of instances of the problem, is found by applying a non-linear optimization algorithm to a function that measures the quality of the obtained solutions to the instances of the training set, and which depends on the parameters that characterize each specific algorithm. EAGH allows improving known heuristics or finding good new ones.     

Management of periodic demands in distribution systems

The problem of the optimal scheduling of periodic demands for a given facility or commodity is presented and some properties of an integer programming model are discussed. Algorithms (both of implicit enumeration type and heuristic) are also given.     

Optimal batting orders in cricket

Cricket teams are usually listed on the scoreboard in expected batting order, andalthough captains can choose to send in any of the remaining batsmen when awicket falls, they rarely depart from the usual batting order. By optimizing asimplified model using dynamic programming, this paper shows that in all formsof cricket significant increases in expected score result if captains allow avariable batting order and base their decision on the state of the game, ratherthan using a set batting order.     

Single-machine ready times scheduling with group technology and proportional linear deterioration

Scheduling research has increasingly taken the concept of deterioration into consideration. In this paper, we study a single machine group scheduling problem with deterioration effect, where the jobs are already put into groups, before any optimization. We assume that the actual processing times of jobs are increasing functions of their starting times, i.e., the job processing times are described by a function which is proportional to a linear function of time. The setup times of groups are assumed to be fixed and known. For some special cases of minimizing the makespan with ready times of the jobs, we show that the problem can be solved in polynomial time for the proposed model. For the general case, a heuristic algorithm is proposed, and the computational experiments show that the performance of the heuristic is fairly accurately in obtaining near-optimal solutions. The results imply that the average percentage error of the proposed heuristic algorithm from optimal solutions is less than 3%.     

Rating players in test match cricket

In general, the evaluation of player performance in test cricket is based on measures such as batting and bowling averages. These measures have a number of limitations, among which is that they fail to take into account the context in which runs are made or conceded and wickets are taken or given away. Furthermore, batting and bowling averages do not allow the comparison of performances in these two disciplines; this is because batting and bowling performances are measured using different metrics. With these issues in mind, we develop a new player rating system for test cricket. We use multinomial logistic regression to model match outcome probabilities session by session. We then use these probabilities to measure the overall contribution of players to the match outcome based on their individual batting, bowling and fielding contributions during each session. Our measure of contribution has the potential for rating players over time and for determining the ‘best’ player in a match, a series or a calendar year. We use results from 104 matches (2010–2012) to illustrate the method.     

An efficient algorithm for optimal design of area traffic control with network flows

An equilibrium network design (EQND) is a problem of finding the optimal design parameters while taking into account the route choice of users. This problem can be formulated as an optimization by taking the user equilibrium traffic assignment as a constraint. In this paper, the methods solving the EQND problem with signal settings are investigated via numerical calculations on two example road networks. An efficient algorithm is proposed in which improvement on a locally optimal search by combining the technique of parallel tangents with the gradient projection method is presented. As it shows, the method combines the locally optimal search and globally search heuristic achieved substantially better performance than did those other approaches.     

A hybrid constraint programming and enumeration approach for solving NHL playoff qualification and elimination problems

Many sports fans invest a great deal of time into watching and analyzing the performance of their favorite team. However, the tools at their disposal are primarily heuristic or based on folk wisdom. We provide a concrete mechanism for calculating the minimum number of points needed to guarantee a playoff spot and the minimum number of points needed to possibly qualify for a playoff spot in the National Hockey League (NHL). Our approach uses a combination of constraint programming, enumeration, network flows and decomposition to solve the problem efficiently. The technique can successfully be applied to any team at any point of the season to determine how well a team must do to make the playoffs.