考虑任务优先约束的同类岸桥作业调度优化

分析了以箱组为任务对象QCSP与以整贝为任务对象QCSP的异同,指出前者更能均衡各岸桥作业负荷,并减少船舶装卸作业时间。考虑到岸桥具有作业效率差异的特点,将其视为同类平行机调度问题,同时结合任务优先约束、岸桥作业不可相互穿越与安全距离等特有约束,建立了更加符合实际的以箱组为任务对象的岸桥作业调度混合整数规划模型,其优化目标是最小化装卸作业的makespan。针对模型求解的复杂度,设计了一种遗传算法,对算法搜索空间进行了讨论,并推导了问题的低界。实验算例表明所建立的模型能够反映岸桥作业调度过程中作业效率差异及任务优先约束现象,其算法能够在允许的运算时间内获得稳定的满意解,并且优化结果要全面优于以整贝为任务对象QCSP的调度方案。     

DCA for solving the scheduling of lifting vehicle in an automated port container terminal

The container was introduced as a universal carrier for various goods in the 1960s and soon became a standard worldwide transportation. The competitiveness of a container seaport is marked by different success factors, particularly the time in port for ships. Operational problems of container terminals is divided into several problems, such as assignment of vessels, loading/unloading and storage of the containers, quay cranes scheduling cite, planning yard cranes cite and assignment of storage containers cite. In this work, the study will focus on piloting yard trucks. Two different types of vehicles can be used, namely automated guided vehicles (AGVs) and lifting vehicles (LVs). An AGV receives a container from a quay crane and transports containers over fixed path. LVs are capable of lifting a container from the ground by itself. The model that we consider is formulated as a mixed integer programming problem, and the difficulty arises when the number of binary variables increases. There are a lot of algorithms designed for mixed integer programming problem such as Branch and Bound method, cutting plane algorithm, . . . By using an exact penalty technique we treat this problem as a DC program in the context of continuous optimization. Further, we combine the DCA with the classical Branch and Bound method for finding global solutions.     

Determination of the number of automated guided vehicles required at a semi-automated container terminal

This paper describes the development of a minimum flow algorithm to determine the number of automated guided vehicles (AGVs) required at a semi-automated container terminal. At such a terminal the containers are transported by AGVs from the quay cranes to the automated stacking cranes and vice versa. A model and a strongly polynomial time algorithm are developed to solve the case in which containers are available for transport at known time instants.     

Berth and quay crane allocation: a moldable task scheduling model

We study the problem of allocating berths to incoming ships and assigning the necessary quay cranes to the ships at a port container terminal. We formulate the problem as the moldable task scheduling problem by considering the tasks as ships and processors as quay cranes assigned to the ships based on the observation that the berthing duration of a ship depends on the number of quay cranes allocated to it. In the model, the processing speed of a task is considered to be a non-linear function of the number of processors allocated to it. We present a suboptimal algorithm that obtains a feasible solution to the discrete version of the problem from the continuous version, that is, where the tasks may require fractional quantities of the resources. We conducted computational experiments to evaluate the performance of the algorithm. The computational results show that the average behaviour of the algorithm is very good.     

基于两阶段混合动态规划算法的龙门吊路径优化

产业界已出现利用多台轨道式龙门吊同时作业以提升集装箱码头装船效率的情况,由于需要确定每台龙门吊的取箱作业集合以及增加了“避免碰撞”、“顺次移动”等现实约束,故其移动路径规划问题在模型建立与求解上比单台轨道式龙门吊更为复杂。本文针对两台轨道式龙门吊同时作业的情形,建立了龙门吊移动路径网络模型,并开发了基于贪婪算法与动态规划的两阶段混合算法,并通过仿真算例,借助与基于实际调度规则所得到的调度方案的对比,验证了模型及优化算法的有效性与实用性。     

Discrete and geometric Branch and Bound algorithms for?medical image registration

Aiming at the development of an exact solution method for registration problems, we present two different Branch & Bound algorithms for a mixed integer programming formulation of the problem. The first B&B algorithm branches on binary assignment variables and makes use of an optimality condition that is derived from a graph matching formulation. The second, geometric B&B algorithm applies a geometric branching strategy on continuous transformation variables. The two approaches are compared for synthetic test examples as well as for 2-dimensional medical data. The results show that medium sized problem instances can be solved to global optimality in a reasonable amount of time.     

Decision support system for container terminal planning

In this paper we describe a decision support system for capacity planning of container terminals. Typical elements of a container terminal are a quay, cranes,a stack yard and trucks for transport of containers between the quay and the stack yard and vice versa. For each of these elements we can devise models to describe the performance. The decision support system combined a heuristic analysis of these models to a global model to study the interaction between the elements of a container terminal.     

Combining Metaheuristics and Exact Methods for Solving Exactly Multi-objective Problems on the Grid

This paper presents a parallel hybrid exact multi-objective approach which combines two metaheuristics – a genetic algorithm (GA) and a memetic algorithm (MA), with an exact method – a branch and bound (B&B) algorithm. Such approach profits from both the exploration power of the GA, the intensification capability of the MA and the ability of the B&B to provide optimal solutions with proof of optimality. To fully exploit the resources of a computational grid, the hybrid method is parallelized according to three well-known parallel models – the island model for the GA, the multi-start model for the MA and the parallel tree exploration model for the B&B. The obtained method has been experimented and validated on a bi-objective flow-shop scheduling problem. The approach allowed to solve exactly for the first time an instance of the problem – 50 jobs on 5 machines. More than 400 processors belonging to 4 different administrative domains have contributed to the resolution process during more than 6 days.      

Minimizing sum of completion times on a single machine with sequence-dependent family setup times

This paper presents a branch-and-bound (B&B) algorithm for minimizing the sum of completion times in a single-machine scheduling setting with sequence-dependent family setup times. The main feature of the B&B algorithm is a new lower bounding scheme that is based on a network formulation of the problem. With extensive computational tests, we demonstrate that the B&B algorithm can solve problems with up to 60 jobs and 12 families, where setup and processing times are uniformly distributed in various combinations of the [1,50] and [1,100] ranges.     

Scheduling linear deteriorating jobs to minimize the number of tardy jobs

In this paper a problem of scheduling a single machine under linear deterioration which aims at minimizing the number of tardy jobs is considered. According to our assumption, processing time of each job is dependent on its starting time based on a linear function where all the jobs have the same deterioration rate. It is proved that the problem is NP-hard; hence a branch and bound procedure and a heuristic algorithm with O(n ²) is proposed where the heuristic one is utilized for obtaining the upper bound of the B&B procedure. Computational results for 1,800 sample problems demonstrate that the B&B method can solve problems with 28 jobs quickly and in some other groups larger problems are also solved. Generally, B&B method can optimally solve 85% of the samples which shows high performance of the proposed method. Also it is shown that the average value of the ratio of optimal solution to the heuristic algorithm result with the objective ??(1 ? Ui) is at most 1.11 which is more efficient in comparison to other proposed algorithms in related studies in the literature.     

The design of corporate tax structures

We consider the corporate tax structuring problem (TaxSP), a combinatorial optimization problem faced by firms with multinational operations. The problem objective is nonlinear and involves the minimization of the firm's overall tax payments i.e. the maximization of shareholder returns. We give a dynamic programming (DP) formulation of this problem including all existing schemes of tax-relief and income-pooling. We apply state space relaxation and state space descent to the DP recursions and obtain an upper bound to the value of optimal TaxSP solutions. This bound is imbedded in a B&B tree search to provide another exact solution procedure. Computational results from DP and B&B are given for problems up to 22 subsidiaries. For larger size TaxSPs we develop a heuristic referred to as the Bionomic Algorithm (BA). This heuristic is also used to provide an initial lower bound to the B&B algorithm. We test the performance of BA firstly against the exact solutions of TaxSPs solvable by the B&B algorithm and secondly against results obtained for large-size TaxSPs by Simulated Annealing (SA) and Genetic Algorithms (GA). We report results for problems of up to 150 subsidiaries, including some real-world problems for corporations based in the US and the UK. Support for this work was provided by the IST Framework 5 Programme of the European Union, Contract IST2000-29405, Eurosignal ProjectMathematics Subject Classification (2000): 90C39, 91B28     

On estimating workload in interval branch-and-bound global optimization algorithms

In general, solving Global Optimization (GO) problems by Branch-and-Bound (B&B) requires a huge computational capacity. Parallel execution is used to speed up the computing time. As in this type of algorithms, the foreseen computational workload (number of nodes in the B&B tree) changes dynamically during the execution, the load balancing and the decision on additional processors is complicated. We use the term left-over to represent the number of nodes that still have to be evaluated at a certain moment during execution. In this work, we study new methods to estimate the left-over value based on the observed amount of pruning. This provides information about the remaining running time of the algorithm and the required computational resources. We focus on their use for interval B&B GO algorithms.     

Global Optimization Issues in Multiparametric Continuous and Mixed-Integer Optimization Problems

In this paper, a number of theoretical and algorithmic issues concerning the solution of parametric nonconvex programs are presented. In particular, the need for defining a suitable overestimating subproblem is discussed in detail. The multiparametric case is also addressed, and a branch and bound (B&B) algorithm for the solution of parametric nonconvex programs is proposed.     

A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints

In this paper, we consider a two-machine flowshop scheduling problem in which the waiting time of each job between the two machines cannot be greater than a certain time period. For the problem with the objective of minimizing makespan, we identify several dominance properties of the problem and develop a branch-and-bound (B&B) algorithm using the dominance properties. Computational tests are performed on randomly generated test problems for evaluation of performance of the B&B algorithm, and results show that the algorithm can solve problems with up to 150 jobs in a reasonable amount of CPU time.     

Yard crane scheduling in port container terminals

Yard cranes are the most popular container handling equipment for loading containers onto or unloading containers from trucks in container yards of land scarce port container terminals. However, such equipment is bulky, and very often generates bottlenecks in the container flow in a terminal because of their slow operations. Hence, it is essential to develop good yard crane work schedules to ensure a high terminal throughput. This paper studies the problem of scheduling a yard crane to perform a given set of loading/unloading jobs with different ready times. The objective is to minimize the sum of job waiting times. A branch and bound algorithm is proposed to solve the scheduling problem optimally. Efficient and effective algorithms are proposed to find lower bounds and upper bounds. The performance of the proposed branch and bound algorithm is evaluated by a set of test problems generated based on real life data. The results show that the algorithm can find the optimal sequence for most problems of realistic sizes.     

A co-operative parallel heuristic for mixed zero–one linear programming: Combining simulated annealing with branch and bound

This paper considers the exact approach of branch and bound (B&B) and the metaheuristic known as simulated annealing (SA) for processing integer programs (IP). We extend an existing SA implementation (GPSIMAN) for pure zero–one integer programs (PZIP) to process a wider class of IP models, namely mixed zero–one integer programs (MZIP). The extensions are based on depth-first B&B searches at different points within the SA framework. We refer to the resultant SA implementation as MIPSA. Furthermore, we have exploited the use of parallel computers by designing a co-operative parallel heuristic whereby concurrent executions of B&B and MIPSA, linked through a parallel computer, exchange information in order to influence their searches. Results reported for a wide range of models taken from a library of MIP benchmarks demonstrate the effectiveness of using a parallel computing approach which combines B&B with SA.     

Modeling and solution of the joint quay crane and truck scheduling problem

This paper addresses the joint quay crane and truck scheduling problem at a container terminal, considering the coordination of the two types of equipment to reduce their idle time between performing two successive tasks. For the unidirectional flow problem with only inbound containers, in which trucks go back to quayside without carrying outbound containers, a mixed-integer linear programming model is formulated to minimize the makespan. Several valid inequalities and a property of the optimal solutions for the problem are derived, and two lower bounds are obtained. An improved Particle Swarm Optimization (PSO) algorithm is then developed to solve this problem, in which a new velocity updating strategy is incorporated to improve the solution quality. For small sized problems, we have compared the solutions of the proposed PSO with the optimal solutions obtained by solving the model using the CPLEX software. The solutions of the proposed PSO for large sized problems are compared to the two lower bounds because CPLEX could not solve the problem optimally in reasonable time. For the more general situation considering both inbound and outbound containers, trucks may go back to quayside with outbound containers. The model is extended to handle this problem with bidirectional flow. Experiment shows that the improved PSO proposed in this paper is efficient to solve the joint quay crane and truck scheduling problem.     

Global solution of semi-infinite programs

Optimization problems involving a finite number of decision variables and an infinite number of constraints are referred to as semi-infinite programs (SIPs). Existing numerical methods for solving nonlinear SIPs make strong assumptions on the properties of the feasible set, e.g., convexity and/or regularity, or solve a discretized approximation which only guarantees a lower bound to the true solution value of the SIP. Here, a general, deterministic algorithm for solving semi-infinite programs to guaranteed global optimality is presented. A branch-and-bound (B&B) framework is used to generate convergent sequences of upper and lower bounds on the SIP solution value. The upper-bounding problem is generated by replacing the infinite number of real-valued constraints with a finite number of constrained inclusion bounds; the lower-bounding problem is formulated as a convex relaxation of a discretized approximation to the SIP. The SIP B&B algorithm is shown to converge finitely to –optimality when the subdivision and discretization procedures used to formulate the node subproblems are known to retain certain convergence characteristics. Other than the properties assumed by globally-convergent B&B methods (for finitely-constrained NLPs), this SIP algorithm makes only one additional assumption: For every minimizer x* of the SIP there exists a sequence of Slater points x_n for which (cf. Section 5.4). Numerical results for test problems in the SIP literature are presented. The exclusion test and a modified upper-bounding problem are also investigated as heuristic approaches for alleviating the computational cost of solving a nonlinear SIP to guaranteed global optimality.     

On parallel Branch and Bound frameworks for Global Optimization

Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity.