Scheduling of a Two-machine Flowshop with Travel Time Between Machines

We consider the classical two-machine flowshop sequencing problem with the following additional constraint. When a job is completed on the first machine it must be transported to the second machine; a single transporter is available. A completed job on the first machine will block the machine if the transporter is in transit. A constructive algorithm to minimize makespan is presented in the paper.     

Scheduling of a Two-machine Flowshop with Processing Time Linearly Dependent on Job Waiting-time

This paper deals with the problem of finding the minimum finish-time schedule in a two-machine flowshop, where the processing times of jobs are linearly dependent on the job waiting-times. The problem is shown to be NP-hard. A heuristic algorithm is presented, and the worst-case bounds are derived for the different variations of the algorithm.     

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

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

一种可控的两台机流水作业排序问题

在经典的两台机流水作业排序问题F_2‖C_(max)的基础上进行修改,将工件J_j在两台机上的加工时间由常数A_j和B_j改成A_j(x)=a_j+c_jx和B_j(x)=b_j-d_jx,其中x是某区间上的可控(决策)变量.排序的目标是,选择适当的x(对应相应的加工时间是A_j(x)、B_j(x))(j=1,2,…,n)及相应的工件的加工顺序σ=[σ(1),σ(2),…,σ(n)],使时间表长(即最后一个工件J_σ(n)在第二台机上的完工时间)G_(max达到最小.给出了解决问题的有效方法.     

Two-Stage Flowshop Scheduling Problem with Bicriteria

The two-stage flowshop scheduling problem with the objective of minimizing total flowtime subject to obtaining the optimal makespan is discussed. A branch-and-bound algorithm and two heuristic algorithms have been developed. The results of the experimental investigation of the effectiveness of the algorithms are also presented.     

Two-Stage,Hybrid Flowshop Scheduling Problem

This paper describes the two-stage flowshop problem when there are identical multiple machines at each stage, and shows that the problem is NP-complete. An efficient heuristic algorithm is developed for finding an approximate solution of a special case when there is only one machine at stage 2. The effectiveness of the proposed heuristic algorithm in finding a minimum makespan schedule is empirically evaluated and found to increase with the increase in the number of jobs.     

Adaptive Control Model and Algorithms for the Dynamic Flowshop Scheduling Problem

1.IntroductionProductionschedulingcanbedefinedgenerallyastheallocationoftheresourcesinaproductionsystemovertimetoperformtheoperationsneededtotransformrawmaterialsilltoproducts.Aneffectiveandefficientschedulingsystemisnecessarytowellachievethepotentialsofaproductionfacility.Productionschedulingproblemsareextremelycomplex.Thecomplexityismainlyduetothefollowingtwofeaturesoftheproblem(Liu,1995).InterconnectedDecisions:Thecomponentsofaproductionsystem,e.g.,machines,ma-tenalhandlingdevicesandstora…     

Total Completion Time in a Two-machine Flowshop with Deteriorating Tasks

This paper deals with two-machine flowshop problems with deteriorating tasks, i.e. tasks whose processing times are a nondecreasing function that depend on the length of the waiting periods. We consider the so-called Restricted Problem. This problem can be defined as follows: for a given permutation of tasks, find an optimal placement on two machines so that the total completion time is minimized. We will show that the Restricted Problem is nontrivial. We give some properties for the optimal placement and we propose an optimal placement algorithm.      

A Branch-and-Bound Algorithm to Minimize the Makespan in a Flowshop with Blocking

This work addresses the minimization of the makespan criterion for the flowshop problem with blocking. In this environment there are no buffers between successive machines, and therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. We propose a lower bound which exploits the occurrence of blocking. A branch-and-bound algorithm that uses this lower bound is described and its efficiency is evaluated on several problems. Results of computational experiments are reported.     

A “Branch-and-Bound” Algorithm for the Exact Solution of the Three-Machine Scheduling Problem

By combining Roy's graph-theoretical interpretation of the problem of job scheduling on machines and some general results of his theory with the “branch-and-bound” method recently applied by Little et al. to the travelling salesman problem an algorithm has been obtained for the exact solution of the scheduling problem in the case of three machines. The working of the algorithm has been illustrated by numerical examples and possibilities of further investigations have been indicated.     

Adapting Branch-and-Bound for Real-World Scheduling Problems

Many sequencing and scheduling problems can be formulated as 0-1 integer programs and, in theory, solved using a branch-and-bound approach. In practice, real-world instances of these problems are usually solved using heuristics. In this paper we demonstrate the benefits of incorporating an intuitive, user-controlled variable-tolerance into a depth-first branch-and-bound algorithm. The tolerance comprises two components: a variable depth tolerance and a variable breadth tolerance. A sample scheduling problem is thoroughly analysed to illustrate empirically parameter impact on solution quality and execution time. Then, results based on several real-world problems are discussed.     

A Genetic Approach for Solving a Scheduling Problem in a Robotized Analytical System

We consider a robotized analytical system in which a chemical treatment has to be performed on a given set of identical samples. The objective is to carry out the chemical treatment on the whole set of samples in the shortest possible time. All constraints have to be satisfied since a modification of the chemical process could create unexpected reactions.We have developed a new robust method governed by a genetic algorithm to solve this scheduling problem. The crossover mechanism of this evolutionary method is based on an extension of the uniform crossover introduced by Syswerda (1989).The proposed approach can be adapted to other combinatorial problems where decisions, based on rules, have to be taken at each step of a constructive method.     

A No-Wait Flowshop Scheduling Heuristic to Minimize Makespan

The scheduling problem in the no-wait or constrained flowshop, with the makespan objective, is considered in this article. A simple heuristic algorithm is proposed on the basis of heuristic preference relations and job insertion. When evaluated over a large number of problems of various sizes, the solutions given by the proposed heuristic are found to be fairly accurate and much superior to those given by the two existing heuristics.     

Branch-and-Bound Algorithms for a Regional Water Authority Distribution Problem

A problem put forward recently by a Regional Water Authority differs from the well-known Capacitated Warehouse Location Problem only in that there are both weeks of normal demand levels and weeks of peak demand levels. We describe how Lagrangian relaxation based branch-and-bound algorithms have been adapted for the new problem. Computational results are given, enabling a comparison of the different approaches tried.     

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

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

Two-Machine Flowshop Batching and Scheduling

We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution.     

Some Applications of the “Branch-and-Bound” Algorithm to the Machine Scheduling Problem

The "branch-and-bound" algorithm for the exact solution of a three-machine scheduling problem proposed by Lomnicki has been generalized to the case of an arbitrary number of machines (under the assumption of an identical order on all the machines) and it has been adapted for an electronic computer. The flow chart of this algorithm used in the programming of calculations has been given and the efficiency of the method has been illustrated by some experimental evaluations of optimum job sequencing.     

A Branch-and-Bound Approach for Solving a Class of Generalized Semi-infinite Programming Problems

A nonconvex generalized semi-infinite programming problem is considered, involving parametric max-functions in both the objective and the constraints. For a fixed vector of parameters, the values of these parametric max-functions are given as optimal values of convex quadratic programming problems. Assuming that for each parameter the parametric quadratic problems satisfy the strong duality relation, conditions are described ensuring the uniform boundedness of the optimal sets of the dual problems w.r.t. the parameter. Finally a branch-and-bound approach is suggested transforming the problem of finding an approximate global minimum of the original nonconvex optimization problem into the solution of a finite number of convex problems.     

A Tabu Search Approach for the Resource Constrained Project Scheduling Problem

An appropriate tabu search implementation is designed to solve the resource constrained project scheduling problem. This approach uses well defined move strategies and a structured neighbourhood, defines appropriate tabu status and tenure and takes account of objective function approximation to speed up the search process. A sound understanding of the problem has helped in many ways in designing and enhancing the tabu search methodology. The method uses diversification, intensification and handles infeasibility via strategic oscillation.The above methodology is tested on existing problems from the literature and also on parametrically generated problems with encouraging results. For comparison of results, optimal solutions are used in the former and lower bounds obtained by Lagrangian heuristics are used in the latter.     

A Branch-and-Bound Algorithm to Solve a Multi-level Network Optimization Problem

Multi-level network optimization problems arise in many contexts such as telecommunication, transportation, and electric power systems. A model for multi-level network design is formulated as a mixed-integer program. The approach is innovative because it integrates in the same model aspects of discrete facility location, topological network design, and dimensioning. We propose a branch-and-bound algorithm based on Lagrangian relaxation to solve the model. Computational results for randomly generated problems are presented showing the quality of our approach. We also present and discuss a real world problem of designing a two-level local access urban telecommunication network and solving it with the proposed methodology.