Single facility scheduling with dual criteria: minimizing maximum tardiness subject to minimum number of tardy jobs

This paper considers the static single machine scheduling problem with the objective of minimizing the maximum tardiness of any job subject to the constraint that the total number of lardy jobs is minimum. Based on simple dominance conditions an o(n²) heuristic algorithm is proposed to find an approximate solution to this problem. The effectiveness of the proposed heuristic algorithm is empirically evaluated by solving a large number of problems and comparing them to the optimal solutions obtained through the branch and bound algorithm.     

A heuristic approach to n/ m job shop scheduling: fuzzy dynamic scheduling algorithms

n/m shop scheduling is a ‘ NP-Hard’ problem. Using conventional heuristic algorithms ( priority rules) only, it is almost impossible to achieve an optimal solution. Research has been carried out to improve the heuristic algorithms to give a near-optimal solution. This paper advocates a fuzzy logic based, dynamic scheduling algoridim aimed at achieving this goal. The concept of new membership functions is discussed in die algorithm as a link to connect several priority rules. The constraints to determine the membership function of jobs for a particular priority rule are established, and three membership functions are developed. In order to decide the weight vector of priority rules, an aggregate performance measure is suggested. The methodology for constructing the weight vector is discussed in detail. Experiments have been carried out using a simulation technique to validate the proposed scheduling algorithm.     

Constructing the Maximum Consensus Tree from Rooted Triples

We investigated the problem of constructing the maximum consensus tree from rooted triples. We showed the NP-hardness of the problem and developed exact and heuristic algorithms. The exact algorithm is based on the dynamic programming strategy and runs in O((m + n ²)3 ⁿ ) time and O(2 ⁿ ) space. The heuristic algorithms run in polynomial time and their performances are tested and shown by comparing with the optimal solutions. In the tests, the worst and average relative error ratios are 1.200 and 1.072 respectively. We also implemented the two heuristic algorithms proposed by Gasieniec et al. The experimental result shows that our heuristic algorithm is better than theirs in most of the tests.     

一种考虑动态时间窗的满载问题模型及算法

针对时间约束在满载问题中的复杂性,建立了一个考虑装载时间和次序的具有动态时间窗的满载车辆调度模型,并给出了一个基于动态构造原理的启发式算法。该模型和算法改进了以往满载问题中对时间窗的考虑,使得求解更具有实际派车意义,并且该算法通过参数调整,经过少量迭代即可快速求得最小化总成本的满意解。     

Revised GRASP with path-relinking for the linear ordering problem

The linear ordering problem (LOP) is an NP\mathcal{NP}-hard combinatorial optimization problem with a wide range of applications in economics, archaeology, the social sciences, scheduling, and biology. It has, however, drawn little attention compared to other closely related problems such as the quadratic assignment problem and the traveling salesman problem. Due to its computational complexity, it is essential in practice to develop solution approaches to rapidly search for solution of high-quality. In this paper we propose a new algorithm based on a greedy randomized adaptive search procedure (GRASP) to efficiently solve the LOP. The algorithm is integrated with a Path-Relinking (PR) procedure and a new local search scheme. We tested our implementation on the set of 49 real-world instances of input-output tables (LOLIB instances) proposed in Reinelt (Linear ordering library (LOLIB) 2002). In addition, we tested a set of 30 large randomly-generated instances proposed in Mitchell (Computational experience with an interior point cutting plane algorithm, Tech. rep., Mathematical Sciences, Rensellaer Polytechnic Institute, Troy, NY 12180-3590, USA 1997). Most of the LOLIB instances were solved to optimality within 0.87 seconds on average. The average gap for the randomly-generated instances was 0.0173% with an average running time of 21.98 seconds. The results indicate the efficiency and high-quality of the proposed heuristic procedure.     

O(m2) ALGORITHMS FOR THE TWO AND THREE SUBLOT LOT STREAMING PROBLEM

Lot streaming is the process of splitting a job or lot into sublots to reduce its makespan on a sequence of machines. The goal in the lot streaming problem is to find the optimal size of each sublot that will minimize the makespan. The makespan is defined as the time the last sublot completes its processing on the last machine. If the sizes of these sublots are restricted to remain the same on all machines, the solution is called a consistent sublot solution. However, if the sizes of the sublots are allowed to vary, the solution is referred to as a nonconsistent or variable sublot solution. Also, if the machines must be in operation continuously from the first to the last sublot, the solution is a no idling solution. When setups are explicitly considered in the problem, there will be two cases. If setups on each machine require some portion of the first sublot be present by the machine, the problem is referred to as the attached setup time problem. If setups can be performed ahead of time before the first sublot reaches the particular machine, the corresponding problem is referred to as the detached setup problem. Finally, if the machines are allowed to be idle between the processing of sublots, the resultant solution is an intermittent idling solution. In this paper, the consistent sublot lot streaming problem with intermittent idling and no setups is discussed. The models developed also assume that the number of sublots are fixed and known. The m machine two sublot lot streaming problem is reviewed. An algorithm for the three sublot, m machine problem is derived using a network representation of the problem. The complexity of the algorithm is O (m²). Finally, using the insights from three sublot problem, a heuristic algorithm is provided for the m machine, n sublot problems. The results on the proposed heuristic are very encouraging; average percent deviation from optimal makespan is approximately at 0.76% on 155 randomly generated problems with different m and n values.     

Intelligent scheduling model and algorithm for manufacturing

This paper puts forward an intelligent scheduling model based on Hopfield neural network and a unified algorithm for manufacturing. The energy computation function and its dynamic state equation are derived and discussed in detail about their coefficients (parameters) and steps (Delta t) in iteration towards convergence. The unified model is focused on the structure of the above function and equation, in which the goal and penalty items must be involved and meet different schedule models. The applications to different schedule mode including jobshop static scheduling, scheduling with due-date constraint or priority constraint, dynamic scheduling, and JIT (just in time) scheduling are discussed, and a series of examples with Gantt charts are illustrated.     

Designing a tabu search algorithm for the two-stage flow shop problem with secondary criterion

This paper discusses the process of desigining a tabu search-based heuristic for the two-stage flow shop problem with makespan minimization as the primary criterion and the minimization of total flow time as the secondary criterion. A factorial experiment is designed to analyse thoroughly the effects of four different factors, i.e. the initial solution, type of move, size of neighbourhood and the list size, on the performance of the tabu search-based heuristic. Using the techniques of evolution curves, and response tables and response graphs, coupled with the Taguchi method, the best combination of the factors for the tabu search-based heuristic is identified, and the effectiveness of the heuristic algorithm in finding an optimal solution is evaluated by comparing its performance with the best known heuristic to solve this problem.     

Allocation of buffer capacity to minimize average work-in-process

This paper proposes an efficient heuristic algorithm to solve the problem of allocating the buffers in a production line for given total buffer capacity and the minimum required throughput. While the traditional research has focused on the problem of allocating the buffer capacity to maximize the throughput, the objective of minimizing the average Work-In-Process (WIP) is considered. Minimization of the WIP in the production line has drawn much attention in many practical applications, due to the growing efforts in reducing the production lead times for faster customer response. Two heuristics are proposed and compared to solve the problem. One is a very simple heuristic approach, and the other is a modified 'Non-SEVA' (Non-Standard Exchange Vector Algorithm) which was originally proposed by Seong et al . ( International Journal of Production Research, 33, 1989-2005, 1995) for the throughput maximization problem. Through computational tests, the efficiency of the proposed approach is shown.     

Minimizing number of tardy jobs on a single machine subject to periodic maintenance

This paper considers a single-machine scheduling problem with periodic maintenance. In this study, a schedule consists of several maintenance periods and each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the number of tardy jobs subject to periodic maintenance and nonresumable jobs. Based on the Moore's algorithm, an effective heuristic is developed to provide a near-optimal schedule for the problem. A branch-and-bound algorithm is also proposed to find the optimal schedule. Some important theorems associated with the problem are implemented in the algorithm. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.     

A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization

This article deals with the development of a heuristic for scheduling in a flowshop with the objective of minimizing the makespan and maximum tardiness of a job. The heuristic makes use of the simulated annealing technique. The proposed heuristic is relatively evaluated against the existing heuristic for scheduling to minimize the weighted sum of the makespan and maximum tardiness of a job. The results of the computational evaluation reveal that the proposed heuristic performs better than the existing one.     

Simulated annealing procedure for scheduling competing tasks in flexible manufacturing

This paper presents a simulated annealing SA procedure heuristic for the problem of scheduling N tasks on a machine equipped with an automatic tool changer to minimize the makespan time. The problem is first formulated as a symmetric travelling salesman problem TSP . A local search heuristic procedure is developed, then embedded into SA algorithm to enhance its performance. The implemented SA heuristic has the following features: an exponential acceptance function with non-monotonic cooling schedule, heuristic pre-processing, and a neighbourhood of changing the sequence of a small number of tasks and named the k-interchange procedure. The algorithm is compared with an exact solution method on a set of practical-sized problems. The proposed algorithm performed very well in terms of solution quality and computation time.     

Flow shop scheduling by transportation model

This paper describes the classical problem of scheduling n jobs on m machines in a flow shop. A schedule evaluation algorithm is presented, which for job-pairs, generates a schedule evaluation matrix. The matrix is the input data to a transportation problem, the solution of which gives near-optimal jobsequence and makespan. The performance of the algorithm is discussed.     

Minimization of maximum lateness under linear deterioration

This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be -hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases.     

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising.     

Hospital resident scheduling problem

This paper addresses the resident scheduling problem (RSP) at hospitals concerned with prescribing work-nights for residents while considering departmental staffing and skill requirements as well as residents' preferences. Three scenarios that represent most situations and account for various departmental requirements and needs are described. Although similar scheduling problems are considered in the literature, no analysis exists that adequately deals with the speciffic nature of this problem. The problem is modeled as a mixed-integer program and heuristic solution procedures are developed for the different identified scheduling scenarios. These procedures exploit the inherent network structure of the problem which is an important feature that enhances problem solvability. For the sake of comparison, the problem is also solved exactly via the CPLEX-MIP (version 6.0) package. The contribution of this work is important since many hospitals are still utilizing manual techniques in preparing their own schedules, expending considerable effort and time and yet contending with limited scheduling flexibility.     

A heuristic algorithm for minimizing maintenance workforce level

We develop a heuristic algorithm for minimizing the workforce level required to accommodate all the maintenance jobs requested within a specific time interval. Each maintenance job has its own release and due dates as well as the required man-days, and must be scheduled in a noninterrupted time interval, i.e. without preemption. However, the duration of each job is not fixed, but to be determined within a specific range. We show that this problem can be seen as a variant of the two-dimensional bin-packing problem with some additional constraints. We develop a non-linear mixed integer programming model for the proposed problem, and employ some well-known bin-packing algorithms to develop an efficient heuristic algorithm. In order to evaluate the performance of the proposed heuristic, we present a computationally efficient scheme for getting a good lower bound for the actual minimum. The computational experiment shows that the proposed heuristic algorithm performs quite satisfactorily in practice.     

An efficient scheduling algorithm for the hot coil making in the steel mini-mill

This paper investigates and suggests an efficient solution to the problem of scheduling the steel making line in the Mini Steel Mill, which consists of three major processes: molten steel making, continuous slab casting, and hot charged rolling. Careful synchronization of these processes is a key productivity factor, since a very limited amount of work-in-process inventory is allowed. Since each process must run in batch, the schedule for the Mini-Mill consists of grouping and sequencing of lots for each process. However, each process has its own criteria for judging the quality of its lot grouping, which often conflicts with other processes. An efficient scheduling algorithm for the Mini-Mill is proposed. Numerical experiments with real world data suggest that the proposed algorithm yield satisfactory schedules very efficiently. The algorithm is currently used for the actual scheduling of a Mini-Mill in Korea.     

加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.