Learning and forgetting effects on a group scheduling problem

This paper proposes to investigate learning and forgetting effects on the problem of scheduling families of jobs on a single machine to minimize total completion time of jobs. A setup time is incurred whenever the single machine transfers job processing from a family to another family. To analyze the impact of learning and forgetting on this group scheduling problem, we structure three basic models and make some comparisons through computational experiments. The three models, including no forgetting, total forgetting and partial forgetting, assume that the processing time of a job is dependent on its position in a schedule. Some scheduling rules and a lower bound are derived in order to constitute our branch-and-bound algorithm for searching an optimal sequence. In addition, an efficient and simply-structured heuristic is also built to find a near-optimal schedule.     

已知工件最大加工时间的平行机排序问题

研究了已知工件最大加工时间，目标为极小化最大机器负载的半在线平行机排序问题．证明了对于一般的m（〉6）台机器，任意的半在线算法的竞争比至少是（√33＋3）／6．同时还设计了一个半在线算法，算法的竞争比为2-1／（m-1）．     

多车场有时间窗的多车型车辆调度及其禁忌算法研究

本文针对物流配送中的多车场车辆调度问题提出了两种多车场的处理方法，介绍了多车场车辆调度问题中容量、时间窗、多车型等多种约束的处理方法，并且根据具体约束情况设计了禁忌算法，对多车场有时间窗的多车型车辆调度问题加以实现，给出了一个具有代表性的算例试验结果和结果分析，通过试验表明了此方法对优化有时间窗的多车型车辆调度问题的有效性．     

一种新的两道工序柔性流水车间排序问题

本文针对F_2(p),h11.1|m_1=1,m_2=μ≥2|C_(max)这一问题给出了几种近似算法,并对每种近似算法进行了最坏情形分析,给出了最坏情形界.     

A two pass heuristic algorithm for scheduling ‘blocked out’ units in continuous process industry

This paper addresses the problem of scheduling cascaded ‘blocked out’ continuous processing units separated by finite capacity storage tanks. The raw materials for the product lines arrive simultaneously on the input side of the first unit. But every unit can process only one product line at a time, thus giving rise to the possibility of spillage of raw material due to limited storage capacity. The need to process multiple product lines and the added constraint of multiple intermediate upliftment dates aggravate the problem. This problem is quite common in petrochemical industry. The paper provides a MINLP (Mixed Integer Non-Linear Programming) formulation of the problem. However, for any realistic scheduling horizon, the size of the problem is too large to be solved by standard packages. We have proposed a depth first branch and bound algorithm, guided by heuristics, to help planners in tackling the problem. The suggested algorithm could output near optimal solutions for scheduling horizons of 30 time periods when applied to real life situations involving 3 units and 3 product lines. Preliminary version of the paper appeared in the proceedings of MISTA, 2005.     

A general model for cyclic machine scheduling problems

A general framework for modeling and solving cyclic scheduling problems is presented. The objective is to minimize the cycle time. The model covers different cyclic versions of the job-shop problem found in the literature, robotic cell problems, the single hoist scheduling problem and tool transportation between the machines.It is shown that all these problems can be formulated as mixed integer linear programs which have a common structure. Small instances are solved with CPLEX. For larger instances tabu search procedures have been developed. The main ideas of these methods are indicated.     

Ant colony optimization for power plant maintenance scheduling optimization—a five-station hydropower system

A number of algorithms have been developed for the optimization of power plant maintenance schedules. However, the true test of such algorithms occurs when they are applied to real systems. In this paper, the application of an Ant Colony Optimization formulation to a hydropower system is presented. The formulation is found to be effective in handling various constraints commonly encountered in practice. Overall, the results obtained using the ACO formulation are better than those given by traditional methods using engineering judgment, which indicates the potential of ACO in solving realistic power plant maintenance scheduling problems.     

Resolution approach for multi-objective problems with uncertain demands

The job-shop scheduling problem (JSP) is one of the hardest problems (NP-complete problem). In a lot of cases, the combination of goals and resource exponentially increases search space. The objective of resolution of such a problem is generally, to maximize the production with a lower cost and makespan. In this paper, we explain how to modify the objective function of genetic algorithms to treat the multi-objective problem and to generate a set of diversified “optimal” solutions in order to help decision maker. We are interested in one of the problems occurring in the production workshops where the list of demands is split into firm (certain) jobs and predicted jobs. One wishes to maximize the produced quantity, while minimizing as well as possible the makespan and the production costs. Genetic algorithms are used to find the scheduling solution of the firm jobs because they are well adapted to the treatment of the multi-objective optimization problems. The predicted jobs will be inserted in the real solutions (given by genetic algorithms). The solutions proposed by our approach are compared to the lower bound of the cost and makespan in order to prove the quality and robustness of our proposed approach.     

A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows

This paper presents a solution methodology for the heterogeneous fleet vehicle routing problem with time windows. The objective is to minimize the total distribution costs, or similarly to determine the optimal fleet size and mix that minimizes both the total distance travelled by vehicles and the fixed vehicle costs, such that all problem’s constraints are satisfied. The problem is solved using a two-phase solution framework based upon a hybridized Tabu Search, within a new Reactive Variable Neighborhood Search metaheuristic algorithm. Computational experiments on benchmark data sets yield high quality solutions, illustrating the effectiveness of the approach and its applicability to realistic routing problems. This work is supported by the General Secretariat for Research and Technology of the Hellenic Ministry of Development under contract GSRT NM-67.     

二机器流水作业排序问题全部最优解的结构

排序问题F2||Cmax,Johnson条件只是最优解的充分条件，不是必要的．本文绘出一个充分必要条件，由此得到生成全部最优解的算法．主要理论是基于一种序论方法．