Design of cooperative algorithms for multi-objective optimization: application to the flow-shop scheduling problem

This is a summary of the main results presented in the author’s PhD thesis. This thesis was supervised by El-Ghazali Talbi, and defended on 21 June 2005 at the University of Lille (France). It is written in French and is available at http://www.lifl.fr/~basseur/These.pdf. This work deals with the conception of cooperative methods in order to solve multi-objective combinatorial optimization problems. Many cooperation schemes between exact and/or heuristic methods have been proposed in the literature. We propose a classification of such schemes. We propose a new heuristic called adaptive genetic algorithm (AGA), that is designed for an efficient exploration of the search space. We consider several cooperation schemes between AGA and other methods (exact or heuristic). The performance of these schemes are tested on a bi-objective permutation flow-shop scheduling problem, in order to evaluate the interest of each type of cooperation.     

Complexity of flow time minimization in a crossdock truck scheduling problem with asymmetric handover relations

We address a novel truck scheduling problem arising in crossdocking logistics, in which inbound trucks carry items (pallets) which must be sorted and loaded onto outbound trucks. We minimize the utilisation of the warehouse by focusing on the synchronisation between the different related trucks. The problem is to assign the trucks to the doors of the warehouse and sequence them, in order to minimize the total time spent in the system by the pallets. We discuss the complexity of the problem, showing that even with a single door the problem is NP-hard in general, and discuss some special cases.     

A polynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line

This paper addresses cyclic hoist scheduling in a no-wait electroplating line where a part visits some processing tanks more than once and multiple duplicate tanks are used at some production stages. We prove that such an extended problem can be solved in polynomial time.     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

An acyclic days-off scheduling problem

This paper studies the days off scheduling problem when the demand for staffing fluctuates from day to another and when the number of total workdays is fixed in advance for each employee. The scheduling problem is then to allocate rests to employees with different days off policies: (1) two or three consecutive days off for each employee per week and (2) at least three consecutive days off for each employee per month. For each one, we propose a polynomial time algorithm to construct a solution if it exists. Received: April 2005 / Revised version: October 2005 AMS classification: 60K25, 60K30     

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to find the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m⁵logm).     

A polynomial time algorithm for a chance-constrained single machine scheduling problem

This paper gives an O(n√nlog³n) time algorithm for the chance-constrained sequencing problem on a single machine, where n is the number of jobs and the objective is to minimize the number of jobs which are early with probability not smaller than α (a given constant) against the common due time d.     

Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences

In the paper a single machine time-dependent scheduling problem is considered. The processing time p_j of each job is described by a function of the starting time t of the job, p_j=1+α_jt, where the job deterioration rate α_j?0 for j=0,1,…,n and t?0. Jobs are nonpreemptable and independent, there are no ready times and no deadlines. The criterion of optimality of a schedule is the total completion time.First, the notion of a signature for a given sequence of job deterioration rates is introduced, two types of the signature are defined and their properties are shown. Next, on the basis of these properties a greedy polynomial-time approximation algorithm for the problem is formulated. This algorithm, starting from an initial sequence, iteratively constructs a new sequence concatenating the previous sequence with new elements, according to the sign of one of the signatures of this sequence.Finally, these results are applied to the problem with job deterioration rates which are consecutive natural numbers, α_j=j for j=0,1,…,n. Arguments supporting the conjecture that in this case the greedy algorithm is optimal are presented.     

Approximation algorithms for scheduling problems with a modified total weighted tardiness objective

We study the approximability of minimum total weighted tardiness with a modified objective which includes an additive constant. This ensures the existence of a positive lower bound for the minimum value. Moreover the new objective has a natural interpretation in just-in-time production systems.     

实时系统中单处理器调度算法的优化设计研究

研究实时系统的建模与调度问题是运筹与控制领域研究的热点问题, 对实时系统中的单处理器的调度算法进行了分析与研究, 特别是对其中的单调速率算法和最早时间限优先算法进行了深入的研究, 指出单调速率算法是一种典型的静态调度算法, 并且证明了单调速率算法是单处理器最优的静态优先级调度算法, 同时还指出最早时间限优先算法是一种典型的动态优先级调度算法,证明了最早时间限优先算法是单处理器的最优的动态优先级调度算法. 最后, 为了更好地进行实时系统的建模与调度, 引入了一种新的对任务执行行为进行抽象的方法--T-LET平面方法, 利用这种方法建立了单处理器流调度模型和BLREF调度算法, 并指出这种模型和算法都具有很强的几何背景.     

目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法

单台机器带一个维修时间段的排序问题,目标是最小化所有工件的运输时间和.在这篇文章里,重新研究了该问题,并给出了一个时间复杂性为O（n³）的近似算法,将性能比从3/2改进到5/4.     

Optimal receiver scheduling algorithms for a multicast problem

This paper studies a multicast problem arising in wavelength division multiplexing single-hop lightwave networks, as well as in Video-on-Demand systems. In this problem, the same message of duration Δ has to be transmitted to a set of n receivers which are not all available simultaneously. The receivers can be partitioned into subsets, each served by a different transmission, with the objective of minimizing their overall waiting cost. When there is a single data channel available for transmission, a dynamic programming algorithm is devised which finds an optimal solution in O(nlogn+min{n²,nΔ²}) time, improving over a previously known O(n³) time algorithm. When multiple data channels are available for transmission, an optimal O(n) time algorithm is proposed which finds an optimal solution if the message has constant transmission duration, whereas an NP-completeness proof is given if the message has arbitrary transmission duration.     

A combined branch-and-bound and genetic algorithm based approach for a flowshop scheduling problem

In this paper, we study the application of a meta-heuristic to a two-machine flowshop scheduling problem. The meta-heuristic uses a branch-and-bound procedure to generate some information, which in turn is used to guide a genetic algorithm's search for optimal and near-optimal solutions. The criteria considered are makespan and average job flowtime. The problem has applications in flowshop environments where management is interested in reducing turn-around and job idle times simultaneously. We develop the combined branch-and-bound and genetic algorithm based procedure and two modified versions of it. Their performance is compared with that of three algorithms: pure branch-and-bound, pure genetic algorithm, and a heuristic. The results indicate that the combined approach and its modified versions are better than either of the pure strategies as well as the heuristic algorithm.     

Solving a school bus scheduling problem with integer programming

In many rural areas in Germany pupils on the way to school are a large if not the largest group of customers in public transport. If all schools start more or less at the same time then the bus companies need a high number of vehicles to serve the customer peak in the morning rush hours. In this article, we present an integer programming model for the integrated coordination of the school starting times and the public bus services. We discuss preprocessing techniques, model reformulations, and cutting planes that can be incorporated into a branch-and-cut algorithm. Computational results show that in our test counties a much lower number of buses would be sufficient if the schools start at different times.     

可中断的多任务平行机排序问题

Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190: 40-51)研究了如下问题: 有 n 个订单, 其中每个订单 i 含有 n_i 个不同的工件. 所有的订单在零时刻已经到达, 并且工件的加工是可中断的. 每个订单 i有一个权重 \omega_i, 定义订单 i 的完工时间 C_i 为订单 i 最后一个完工工件的完工时间. 目标是找到一个可行排序使得加权总完工时间\sum\limits_{i=1}^n \omega_iC_i 最小. Leung等证明了这个问题是NP-难的, 给出了一个近似算法, 并且分析了该算法的最坏情况界. 但是定理2的证明存在一些错误. 证明了尽管定理2的证明过程存在错误, 但是其结论仍然正确. 另外, 对上述模型的一种特殊情形给出了更好的近似算法.     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

Flow-shop scheduling with setup and assembly operations

A scheduling model for a production system including machining, setup and assembly operations is considered. Production of a number of single-item products is ordered. Each product is made by assembling a set of several different parts. First, the parts are manufactured in a flow-shop consisting of multiple machines. Then, they are assembled into products on a single assembly stage. Setup operation and setup time are needed when a machine starts processing the parts or it changes items. The operations are partitioned into several blocks. Each block consists of the machining operations, the setup operations, and the assembly operation(s) for one or several products. The parts of the same item in a block are processed successively. The objective function is the mean completion time for all products. We consider a problem to partition the operations into blocks and sequence the parts in each block so as to minimize the objective function. Solution procedures using pseudo-dynamic programming and a branch-and-bound method are proposed. Computational experiments are carried out to evaluate the performance of the solution procedures. It has been found that a good near-optimal schedule is obtained efficiently by the proposed solution procedures.     

储存时间有上限的两阶段供应链排序问题

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是NP-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.     

工件满足一致性的同类机在线分批排序问题

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q_2|r_ir_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_ir_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.