On Optimal Common Due-Date Determination

Given a set of n independent jobs to be processed on a singlemachine, the problem is to determine the optimal constant flowallowance for the CON due-date assignment method and the optimaljob sequence to minimize an average missed due-date cost. Alinear programming formulation of the problem is proposed andthe optimal due-date is obtained by solving the LP dual problem.It is shown that the optimal job sequence can be determinedanalytically only under a special circumstance. Finally, a numericalexample is given to demonstrate how the results can be appliedto find the optimal solutions.     

Optimal due-date determination and sequencing with random processing times

This paper considers the problem of due-date determination and sequencing of n stochastically independent jobs on a single machine with random processing times. The objective is to find the optimal due-date values for the constant due-date assignment method and the optimal job sequence that minimize the expected value of a total cost function. It is shown that under suitable assumptions the optimal due-date values can be analytically determined and the jobs should be arranged in the SEPT sequence to minimize the cost.     

考虑泊位疏浚的连续型泊位和动态岸桥联合调度

针对集装箱码头泊位需要定期维护的实际特征,研究了泊位疏浚情况下连续型泊位和动态岸桥联合调度问题。首先,建立了一个以船舶周转时间最小为目标的整数线性规划模型;其次,针对问题特性设计了三种启发式算法。为了分析泊位疏浚对码头工作的影响并验证模型正确性和算法有效性,分别对未考虑泊位疏浚和考虑泊位疏浚两种调度情形,进行了小规模与大规模问题输入的多组测试。三种算法在小规模输入上均取得了相同于CPLEX的精确解,从而验证了算法的有效性;进一步通过对比分析这些算法在大规模输入中的运行结果,验证其有效性能。     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

Batch scheduling and common due-date assignment on a single machine

We consider the problem of scheduling n groups of jobs on a single machine where three types of decisions are combined: scheduling, batching and due-date assignment. Each group includes identical jobs and may be split into batches; jobs within each batch are processed jointly. A sequence independent machine set-up time is needed between each two consecutively scheduled batches of different groups. A due-date common to all jobs has to be assigned. A schedule specifies the size of each batch, i.e. the number of jobs it contains, and a processing order for the batches. The objective is to determine a value for the common due-date and a schedule so as to minimize the sum of the due date assignment penalty and the weighted number of tardy jobs. Several special cases of this problem are shown to be ordinary NP-hard. Some cases are solved in O(n log n) time. Two pseudopolynomial dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.     

A Heuristic for Common Due-date Assignment and Job Scheduling on Parallel Machines

In this paper we consider the problem of scheduling a set of simultaneously available jobs on several parallel and identical machines. The problem is to find the optimal due-date, assuming this to be the same for all jobs. We also seek to sequence the jobs such that some are early and some are late so as to minimize a penalty function. For the single-machine problem, we present a simple proof of the well-known optimality result that the optimal due-date coincides with one of the job completion times. We show that the optimal job sequence for the single-machine problem can be easily determined. We prove that the same optimal due-date result can be generalized to the parallel-machine problem. However, determination of the optimal job sequence for such a problem is much more complex, and we present a simple heuristic to find an approximate solution. On the basis of a limited experiment, we observe that the heuristic is very effective in obtaining near-optimal solutions.     

带有资源转移时间的RCPSP资源流模型及算法

本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。     

Optimal Assignment of Total-work-content Due-dates and Sequencing in a Single-machine Shop

This paper considers the problem of optimal assignment of total-work-content due-dates to n jobs and of sequencing them on a single machine to minimize an objective function depending on the assigned due-date multiple value and maximum tardiness penalty. It is shown that both the earliest due-date and shortest processing time orders yield an optimal sequence. A simple analytical solution method is presented to find the optimal due-dates. After the theoretical treatment an illustrative example is presented for discussion.     

Tabu search for solving the black-and-white travelling salesman problem

The black-and-white travelling salesman problem (BWTSP) is an extension to the well-known TSP by partitioning the set of vertices into black and white vertices, and imposing cardinality and length constraints between two consecutive black vertices in a Hamiltonian tour. BWTSP has various applications in aircraft routing, telecommunication network design and logistics. In this paper, we develop several tabu search (TS) heuristics for solving the BWTSP. Our TS is built upon a new efficient neighbourhood structure, which exploits both the permutation and knapsack features of BWTSP. We also embed our TS as a heuristic procedure to improve the upper bound in a mixed-integer linear programming method. Extensive computational experiment on both benchmark and randomly generated instances shows effectiveness and efficiency of our algorithms. Our algorithms are able to obtain optimal and near optimal solutions to small instances in seconds, and find feasible solutions to large instances that have not been solved by the existing methods in the literature.     

Single machine scheduling with sequence-dependent family setups to minimize maximum lateness

Motivated by a real-life scheduling problem in a steel wire factory in China,this paper considers the single machine scheduling problem with sequence-dependent family setup times to minimize maximum lateness. In view of the NP-hard nature of the problem, structural (dominance and neighbourhood)properties of the problem are described and used in the tabu search algorithms to find optimal or near-optimal schedules. These proposed structural properties quickly exclude unpromising and/or non-improving neighbours from further search.Empirical results on the randomly generated and real-life problem instances from a factory in China show that the proposed heuristic algorithms utilizing the structural properties can obtain optimal or near optimal solutions with a reasonable computational effort.     

On a single-machine optimal constant due-date assignment and sequencing problem

This paper considers the problem of optimal constant due-date assignment and sequencing of jobs in a single-machine shop. We formulate the problem as a general constrained optimization problem and apply the Kuhn-Tucker conditions to find the optimal solution which is shown to be independent of the job sequence.     

Routing and wavelength assignment in optical networks using bin packing based algorithms

This paper addresses the problem of routing and wavelength assignment (RWA) of static lightpath requests in wavelength routed optical networks. The objective is to minimize the number of wavelengths used. This problem has been shown to be NP-complete and several heuristic algorithms have been developed to solve it. We suggest very efficient, yet simple, heuristic algorithms for the RWA problem developed by applying classical bin packing algorithms. The heuristics were tested on a series of large random networks and compared with an efficient existing algorithm for the same problem. Results indicate that the proposed algorithms yield solutions significantly superior in quality, not only with respect to the number of wavelength used, but also with respect to the physical length of the established lightpaths. Comparison with lower bounds shows that the proposed heuristics obtain optimal or near optimal solutions in many cases.     

Extensive Testing of a Hybrid Genetic Algorithm for Solving Quadratic Assignment Problems

A robust search algorithm should ideally exhibit reasonable performance on a diverse and varied set of problems. In an earlier paper Lim et al. (Computational Optimization and Applications, vol. 15, no. 3, 2000), we outlined a class of hybrid genetic algorithms based on the k-gene exchange local search for solving the quadratic assignment problem (QAP). We follow up on our development of the algorithms by reporting in this paper the results of comprehensive testing of the hybrid genetic algorithms (GA) in solving QAP. Over a hundred instances of QAP benchmarks were tested using a standard set of parameters setting and the results are presented along with the results obtained using simple GA for comparisons. Results of our testing on all the benchmarks show that the hybrid GA can obtain good quality solutions of within 2.5% above the best-known solution for 98% of the instances of QAP benchmarks tested. The computation time is also reasonable. For all the instances tested, all except for one require computation time not exceeding one hour. The results will serve as a useful baseline for performance comparison against other algorithms using the QAP benchmarks as a basis for testing.     

Optimal berth allocation and time-invariant quay crane assignment in container terminals

Due to the dramatic increase in the world’s container traffic, the efficient management of operations in seaport container terminals has become a crucial issue. In this work, we focus on the integrated planning of the following problems faced at container terminals: berth allocation, quay crane assignment (number), and quay crane assignment (specific). First, we formulate a new binary integer linear program for the integrated solution of the berth allocation and quay crane assignment (number) problems called BACAP. Then we extend it by incorporating the quay crane assignment (specific) problem as well, which is named BACASP. Computational experiments performed on problem instances of various sizes indicate that the model for BACAP is very efficient and even large instances up to 60 vessels can be solved to optimality. Unfortunately, this is not the case for BACASP. Therefore, to be able to solve large instances, we present a necessary and sufficient condition for generating an optimal solution of BACASP from an optimal solution of BACAP using a post-processing algorithm. In case this condition is not satisfied, we make use of a cutting plane algorithm which solves BACAP repeatedly by adding cuts generated from the optimal solutions until the aforementioned condition holds. This method proves to be viable and enables us to solve large BACASP instances as well. To the best of our knowledge, these are the largest instances that can be solved to optimality for this difficult problem, which makes our work applicable to realistic problems.     

Setting Job-Shop Due-Dates with Service-Level Constraints

The job-shop due-date assignment problem arises when a manager needs to ‘promise’ a delivery date to a customer. Previous methods yield due-dates which are either optimistic (unlikely to be achieved) or conservative (the promise will be met, but too easily, because the date given was very pessimistic). This paper investigates the due-date assignment problem with a customer ‘service-level’ constraint, the percentage of time that promised delivery dates are honoured. We formulate a rule to attain this service level, yet maintain as short a due-date lead time as possible. Unlike previous attempts, this due-date rule considers not only the job content and instantaneous shop congestion information, but also implicitly incorporates information on how the jobs will be scheduled (or ‘loaded’) once they are in the shop. We simulate a single-machine shop for various measures of performance under several dispatching priorities, comparing our due-date rule with one reported to yield satisfactory performance. Our rule meets all requirements and is found to be superior for most measures of performance.     

An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate

U-type assembly line is one of the important tools that may increase companies’ production efficiency. In this study, two different modeling approaches proposed for the assembly line balancing problems have been used in modeling type-II U-line balancing problems, and the performances of these models have been compared with each other. It has been shown that using mathematical formulations to solve medium and large size problem instances is impractical since the problem is NP-hard. Therefore, a grouping genetic and simulated annealing algorithms have been developed, and a particle swarm optimization algorithm is adapted to compare with the proposed methods. A special crossover operator that always obtains feasible offspring has been suggested for the proposed grouping genetic algorithm. Furthermore, a local search procedure based on problem-specific knowledge was applied to increase the intensification of the algorithm. A set of well-known benchmark instances was solved to evaluate the effectiveness of the proposed and existing methods. Results showed that while the mathematical formulations can only be used to solve small size instances, metaheuristics can obtain high quality solutions for all size problem instances within acceptable CPU times. Moreover, grouping genetic algorithm has been found to be superior to the other methods according to the number of optimal solutions, or deviations from the lower bound values.     

Upper and lower bounding procedures for the multiple knapsack assignment problem

We formulate the multiple knapsack assignment problem (MKAP) as an extension of the multiple knapsack problem (MKP), as well as of the assignment problem. Except for small instances, MKAP is hard to solve to optimality. We present a heuristic algorithm to solve this problem approximately but very quickly. We first discuss three approaches to evaluate its upper bound, and prove that these methods compute an identical upper bound. In this process, reference capacities are derived, which enables us to decompose the problem into mutually independent MKPs. These MKPs are solved euristically, and in total give an approximate solution to MKAP. Through numerical experiments, we evaluate the performance of our algorithm. Although the algorithm is weak for small instances, we find it prospective for large instances. Indeed, for instances with more than a few thousand items we usually obtain solutions with relative errors less than 0.1% within one CPU second.     

Experimental analysis of heuristics for the bottleneck traveling salesman problem

In this paper we develop efficient heuristic algorithms to solve the bottleneck traveling salesman problem (BTSP). Results of extensive computational experiments are reported. Our heuristics produced optimal solutions for all the test problems considered from TSPLIB, JM-instances, National TSP instances, and VLSI TSP instances in very reasonable running time. We also conducted experiments with specially constructed ‘hard’ instances of the BTSP that produced optimal solutions for all but seven problems. Some fast construction heuristics are also discussed. Our algorithms could easily be modified to solve related problems such as the maximum scatter TSP and testing hamiltonicity of a graph.     

Due-date assignment and parallel-machine scheduling with deteriorating jobs

In this paper we study the problem of scheduling n deteriorating jobs on m identical parallel machines. Each job's processing time is a nondecreasing function of its start time. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of the due-date, earliness and tardiness penalties. We show that this problem is NP-hard, and we present a heuristic algorithm to find near-optimal solutions for the problem. When the due-date penalty is 0, we present a polynomial time algorithm to solve it.     

Minmax scheduling problems with common flow-allowance

In due-date assignment problems with a common flow-allowance, the due-date of a given job is defined as the sum of its processing time and a job-independent constant. We study flow-allowance on a single machine, with an objective function of a minmax type. The total cost of a given job consists of its earliness/tardiness and its flow-allowance cost components. Thus, we seek the job schedule and flow-allowance value that minimize the largest cost among all the jobs. Three extensions are considered: the case of general position-dependent processing times, the model containing an explicit cost for the due-dates, and the setting of due-windows. Properties of optimal schedules are fully analysed in all cases, and all the problems are shown to have polynomial time solutions.