A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search

The job-shop scheduling problem is one of the most arduous combinatorial optimization problems. Flexible job-shop problem is an extension of the job-shop problem that allows an operation to be processed by any machine from a given set along different routes. This paper present a new approach based on a hybridization of the particle swarm and local search algorithm to solve the multi-objective flexible job-shop scheduling problem. The particle swarm optimization is a highly efficient and a new evolutionary computation technique inspired by birds’ flight and communication behaviors. The multi-objective particle swarm algorithm is applied to the flexible job-shop scheduling problem based on priority. Also the presented approach will be evaluated for their efficiency against the results reported for similar algorithms (weighted summation of objectives and Pareto approaches). The results indicate that the proposed algorithm satisfactorily captures the multi-objective flexible job-shop problem and competes well with similar approaches.     

A local search algorithm for the optimization of the stochastic economic lot scheduling problem

This paper describes a model for the stochastic economic lot scheduling problem (SELSP) and a Local Search heuristic to find close to optimal solutions to this model. The SELSP considers multiple products, which have to be scheduled on a single facility with limited capacity and significant setup times and costs. The demand is modeled as a stationary compound renewal process. The objective is to find a schedule that minimizes the long-run average costs for setups and inventories while satisfying a given fill rate. We use a cyclic scheduling approach in which the individual cycle time of each product is a multiple of some basic period (fundamental cycle).For the deterministic version of the SELSP, efficient heuristics have been developed which guarantee the feasibility of the solution by adding an additional constraint to the problem. In our case this is not sufficient, because for the calculation of the average inventory levels and fill rates we need to develop a schedule with detailed timing of the lots. We present an efficient heuristic for this scheduling problem, which can also be used to check the feasibility of the solution. Thereby, the most time-consuming step (the calculation of average inventory levels and fill rates) is only performed for a limited set of candidates.The algorithm was tested on deterministic benchmark problems from literature and on a large set of stochastic instances. We report on the performance of the heuristic in both cases and try to identify the main factors influencing the objective.     

A genetic algorithm based heuristic for two machine no-wait flowshop scheduling problems with class setup times that minimizes maximum lateness

Machine scheduling problem has been extensively studied by researchers for many decades in view of its numerous applications on solving practical problems. Due to the complexity of this class of scheduling problems, various approximation solution approaches have been presented in the literature. In this paper, we present a genetic algorithm (GA) based heuristic approach to solve the problem of two machine no-wait flowshop scheduling problems that the setup time on the machines is class dependent, and the objective is to minimize the maximum lateness of the jobs processed. This class of machine scheduling problems has many practical applications in manufacturing industry, such as metal refinery operations, food processing industry and chemical products production processes, in which no interruption between subsequent processes is allowed and the products can be grouped into families. Extensive computation experiments have been conducted to evaluate the effectiveness of the proposed algorithm. Results show the proposed methodology is suitable to be adopted for the development of an efficient scheduling plan for this class of problems in real life application.     

A hybrid artificial bee colony algorithm for the job shop scheduling problem

The job shop scheduling problem (JSSP) has attracted much attention in the field of both information sciences and operations research. In terms of the objective function, most existing research has been focused on the makespan criterion (i.e., minimizing the overall completion time). However, for contemporary manufacturing firms, the due date related performance is usually more important because it is crucial for maintaining a high service reputation. Therefore, in this study we aim at minimizing the total weighted tardiness in JSSP. Considering the high complexity, a novel artificial bee colony (ABC) algorithm is proposed for solving the problem. A neighborhood property of the problem is discovered, and then a tree search algorithm is devised to enhance the exploitation capability of ABC. According to extensive computational tests, the proposed approach is efficient in solving the job shop scheduling problem with total weighted tardiness criterion.     

Multi-product newsvendor problem with value-at-risk considerations

We consider the single period stochastic inventory (newsvendor) problem with downside risk constraints. The aim in the classical newsvendor problem is maximizing the expected profit. This formulation does not take into account the risk of earning less than a desired target profit or losing more than an acceptable level due to the randomness of demand. We utilize Value at Risk (VaR) as the risk measure in a newsvendor framework and investigate the multi-product newsvendor problem under a VaR constraint. To this end, we first derive the exact distribution function for the two-product newsvendor problem and develop an approximation method for the profit distribution of the N-product case (N>2). A mathematical programming approach is used to determine the solution of the newsvendor problem with a VaR constraint. This approach allows us to handle a wide range of cases including the correlated demand case that yields new results and insights. The accuracy of the approximation method and the effects of the system parameters on the solution are investigated numerically.     

Two-stage flowshop earliness and tardiness machine scheduling involving a common due window

This paper studies a non-preemptive two-stage flowshop scheduling problem to minimize the earliness and tardiness under the environment of a common due window. The window size and the window location are considered to be given parameters. The just-in-time problem exists naturally and has many practical applications. The problem is shown to be NP-complete in the strong sense. We develop a branch and bound algorithm and a heuristic to solve the problem. We conduct the computational experiments to test the performances of the algorithms. A strong lower bound is derived for the branch and bound algorithm that can efficiently solve 15 jobs problem for about 5 minutes. The heuristic is shown to be efficient and effective, which can solve the problem of 150 jobs for about 20 seconds and provide near-optimal solution. We justify that the heuristic is an excellent solution approach for large problem instances. We also show that four special cases are either polynomial solvable or NP-complete in the ordinary sense.     

流水工序调度与生产效率的关系模型分析

提出一种基于粒子群算法的流水工序调度任务优化模型。利用流水工序调度任务的特点得到流水工序时间约束条件,利用粒子群算法的原理建立流水工序调度任务优化模型,利用粒子群算法对模型进行求解。仿真实验表明,利用该算法能够得到流水工序调度问题的最优解,提高生产效率。     

Stock rationing under service level constraints in a vertically integrated distribution system

This paper addresses a rationing problem in a two-level, vertically integrated distribution system composed of one manufacturer and several retail points. The motivating case, developed in the vending machine sector and modeled as a newsvendor-like problem, is representative of many real settings where short-term changes in demand can be substantial while capacity modification is not a viable option. The paper provides an analytical discussion of the problem from two different standpoints: a pure profit-maximization perspective and a minimum service-level perspective, both subject to a product availability constraint that affects the service level the company can provide, and the related expected profit. By analyzing the Lagrangean formulation of the problem, we devise efficient computational procedures based on dichotomy search to find the optimal allotments to retailers, maximizing the expected profit and ensuring a minimum service level. Then, we extend the analysis to the evaluation of the highest service level that can be provided, under a product availability constraint. We identify conditions such that the proposed search procedures succeed in finding the optimal solutions, as well as bounds for the search domains. The proposed approach is legitimated under several demand distribution functions subject to a few commonly adopted restrictions that encompass many of the usually adopted continuous distributions. Finally, the paper presents a three-step decision-making framework using the proposed procedures, summarizing the decision paths the manufacturer might follow in order to optimize the allocation decision.     

A tabu search approach for cell scheduling problem with makespan criterion

Scheduling problem in a cellular manufacturing system is treated as the group scheduling problem, assuming that intercellular moves can be eliminated by duplicating machines. However, in a typical CMS, duplicating bottleneck machines may be costly and infeasible. This fact limits the applicability of group scheduling. Scheduling problem in the presence of bottleneck machines is termed as cell scheduling. A mixed-integer linear programming model is proposed for the attempted cell scheduling problem and a nested application of tabu search approach is investigated in this paper to solve the problem heuristically. The effectiveness of the proposed nested tabu search (NTS) algorithm is evaluated on 16 problems selected from the literature. Comparison of the results of NTS with SVS-algorithm reveals the effectiveness and efficiency of the proposed algorithm.     

A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem

The goal of block mining is to obtain a set of genes that contain dependency among gene relationships. Such blocks without overlapping of genes can be further merged to form a new chromosome and the quality of the new chromosome can be greatly improved. Based on this concept, we propose a novel block mining method that is able to locate common structures or to establish new blocks (like a small piece of puzzle) from a set of high fit chromosomes. The identified blocks (puzzles) will also be updated generation by generation through the newly updated high fit chromosomes. We develop a heuristic re-combination procedure to form a new chromosome by re-combining the blocks. We call the new chromosomes generated as artificial chromosomes (ACs) and inject them into the evolutionary process when the convergence slope of the evolutionary process is less than a predefined threshold. This new algorithm retains the regular simple genetic algorithm (SGA) operations of crossover and mutation, and utilizes the ACs generated from elites to speed up the convergence process. Experimental results indicate that the puzzle-based method of chromosome generation is very efficient and effective in solving the traditional permutation flowshop scheduling problem. The new method can be applied to tackle other NP-complete problems such as scheduling and vehicle routing problems.     

Scheduling a capacitated single machine with time deteriorating job values

We address the scheduling problem with the following characteristics: (i) there is a single machine available, (ii) the machine has limited capacity, and (iii) job value deteriorates with time. The problem is motivated from several real world situations, such as, downloading process of web pages, and scheduling of multiplexes. Since the problem is NP-hard, we propose new heuristics based on a multiplicative piece-wise metric as an approximation of the slope of job value deterioration. Computational results show that the proposed heuristics perform better than other existing heuristics for similar types of problems.     

A new approach to job shop scheduling problems with due date constraints considering operation subcontracts

We consider a kind of job shop scheduling problems with due-date constraints, where temporal relaxation of machine capacity constraint is possible through subcontracts. In practice, this kind of problem is frequently found in manufacturing industries where outsourcing of manufacturing operation is possible through subcontract. We present a heuristic algorithm that addresses the problem by solving a series of smaller subproblems to optimality. For the sake of efficiency, the algorithm repeatedly executes in two steps—(1) improving the sequence of operations and (2) picking out the operations to be subcontracted—on bottleneck machines. Experiments are conducted for example problems, and the result of the experiment confirms the viability of the suggested algorithm.     

Multiple part-type scheduling in flexible robotic cells

This paper considers the scheduling problem arising in two-machine manufacturing cells which repeatedly produce a set of multiple part-types, and where transportation of the parts between the machines is performed by a robot. The cycle time of the cell depends on the robot move sequence as well as the processing times of the parts on the machines. For highly flexible CNC machines, the processing times can be adjusted. To this end, this study tries to find the robot move sequence as well as the processing times of the parts on each machine that jointly minimize the cycle time. The problem of determining the best cycle in a 2-machine cell is first modeled as a traveling salesman problem. Then, an efficient 2-stage heuristic algorithm is constructed and compared with the most common heuristic approach of longest processing time (LPT).     

Tabu search for minimizing total tardiness in a job shop

This paper presents a tabu search approach to minimize total tardiness for the job shop scheduling problem. The method uses dispatching rules to obtain an initial solution and searches for new solutions in a neighborhood based on the critical paths of the jobs. Diversification and intensification strategies are suggested. For small problems the solutions’ quality is evaluated against optimal solution values and for large problems the tabu search performance is compared with two heuristics proposed in the literature.     

A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems—A case study for solar cell industry

This paper studies a solar cell industry scheduling problem which is similar to the traditional hybrid flow shop scheduling (HFS). In a typical HFS with parallel machines problem, the allocation of machine resources for each order should be scheduled in advance and then the optimal multiprocessor task scheduling in each stage could be determined. However, the challenge in solar cell manufacturing is the number of machines can be dynamically adjusted to complete the job within the shortest possible time. Therefore, the paper addresses a multi-stage HFS scheduling problem with characteristics of parallel processing, dedicated machines, sequence-independent setup time, and sequence-dependent setup time. The objective is to schedule the job production sequence, number of sublots, and dynamically allocate sublots to parallel machines such that the makespan time is minimized. The problem is formulated as a mixed integer linear programming (MILP) model. A hybrid approach based on the variable neighborhood search and particle swarm optimization (VNPSO) is developed to obtain the near-optimal solution. Preliminary computational study indicates that the developed VNPSO not only provides good quality solutions within a reasonable amount of time but also outperforms the classic branch and bound method and the current industry heuristic practiced by the case company.     

Constraint-based ACO for a shared resource constrained scheduling problem

We consider a scheduling problem arising in the mining industry. Ore from several mining sites must be transferred to ports to be loaded on ships in a timely manner. In doing so, several constraints must be met which involve transporting the ore and deadlines. These deadlines are two-fold: there is a preferred deadline by which the ships should be loaded and there is a final deadline by which time the ships must be loaded. Corresponding to the two types of deadlines, each task is associated with a soft and hard due time. The objective is to minimize the cumulative tardiness, measured using the soft due times, across all tasks. This problem can be formulated as a resource constrained job scheduling problem where several tasks must be scheduled on multiple machines satisfying precedence and resource constraints and an objective to minimize total weighted tardiness. For this problem we present hybrids of ant colony optimization, Beam search and constraint programming. These algorithms have previously shown to be effective on similar tightly-constrained combinatorial optimization problems. We show that the hybrid involving all three algorithms provides the best solutions, particularly with respect to feasibility. We also investigate alternative estimates for guiding the Beam search component of our algorithms and show that stochastic sampling is the most effective.     

A binary solution method for the multi-product newsboy problem with budget constraint

Multi-product newsboy problem (MPNP) with budget constraint is a classical inventory control/management problem. However, solution methods for MPNP under general demand distributions are limited in the current literature. In this paper, by analyzing properties of the optimal solution to the MPNP with a budget constraint, we develop a solution algorithm for the constrained MPNP. The proposed algorithm is binary in nature, and is applicable to general types of demand distribution functions, discrete as well as continuous. For continuous demand distribution function, our approach can obtain the optimal or near optimal solution to the constrained MPNP with polynomial computation complexity of the o(n) order. On the other hand, for discrete demand distribution functions, it can effectively provide good approximate solution. Numerical experiments are presented to show the performance of our method.     

Managing a Portfolio of Interdependent New Product Candidates in the Pharmaceutical Industry

Highly regulated industries such as pharmaceuticals and agrochemicals face the challenge of maintaining a 0continuous stream of new products. This is difficult because of low probabilities of technical success, high development costs, uncertain market impact, a scarcity of good new product ideas, and limited human and capital resources available to develop them. The problem of evaluating and selecting which new products to develop and then of sequencing or of scheduling them is complicated further by the presence of dependencies between products both in the market place and in the development process itself. This study proposes a portfolio management approach that selects a sequence of projects, which maximizes the expected economic returns at an acceptable level of risk for a given level of resources in a new product development pipeline. A probabilistic network model of distinct activities is used to capture all the activities and resources required in the “process” of developing a new drug. A prioritization scheme suggesting sequences for developing new independent drug candidates with unlimited resources is generated with a conventional bubble chart approach. These sequences initiate a genetic algorithm (GA)‐based search for the optimal sequence in the presence of product dependencies and limited resources. By statistically evaluating the sequences generated during the GA search using a discrete event simulation model, it is possible to construct an economic reward‐risk frontier that illustrates the trade‐offs between expected rewards and risks. The model ideally is suited to answer various “what if” questions relative to changes in the resource level on pipeline performance. The methodology is illustrated with an industrially motivated case study, involving nine interdependent new product candidates targeting three diseases. The dramatic results yield a candidate sequence with an expected return 28 percent higher than the sequence suggested by the bubble chart approach at almost the same level of risk. The synergism among the candidate dependencies, pipeline resources, and economic and technical uncertainties demonstrates the necessity of a computationally intensive approach if the best development strategy is to be realized.     

An integrated distribution routing model in multi-supply center system

A distribution routing problem with time constraint is one of the important problems in distribution and supply center management. This research is concerned with an integrated distribution routing problem for multi-supply centers based on improved genetic algorithm and graphical user interface (GUI)-type programming. In this research, we proposed a method based on a three-step approach: in step 1 a sector clustering model is developed to transfer the multi-supply center problem to single supply center problems which are easier to be solved; in step 2 we developed a vehicle routing model with time constraints and in step 3 we developed a GA-TSP model which can improve the vehicle routing schedules. The objective of the problem is to minimize the logistic cost for a set of customers without being tardy or exceeding the capacity or travel time of the vehicles. For computational purpose, we developed a GUI-type computer program according to the proposed methods and the sample outputs show that the proposed method is very effective on a set of standard test problems, and it could be potentially useful in solving the distribution routing problems.     

Lot sizes in a capacity constrained facility—a simulation study of stationary stochastic demand

This paper considers the scheduling of several different items on a single machine, in literature known as the economic lot scheduling problem, ELSP. One of the characteristics of this problem is that the demand rate is deterministic and constant. However, in a practical situation demand usually varies. In this paper we examine if a deterministic model can be used if demand is stationary stochastic. A dynamic programming approach from Bomberger (Manage. Sci. 12(11) (1966) 778) and a heuristic method from Segerstedt (Int. J. Production Econom. 59(1–3) (1999) 469) are used to calculate lot sizes for four items. The production of these items is simulated with different variations in demand rates. Our conclusion is that a deterministic model of this kind can be used in a practical situation where the demand rate is stationary stochastic, but the models must be complemented by a decision rule; which item to produce and when to produce it. In our tests the heuristic method and the dynamic programming approach perform rather similarly with respect to costs and inventory levels, but the dynamic programming approach results in more backorders when there is small variation in demand rates. This study indicates that the model used for determination of lot sizes is of less importance than the decision rule used for identification of the item to produce and when to produce it.