Permutation flowshop scheduling to minimize the total tardiness with learning effects

Scheduling with learning effects has received considerable attention recently. Often, numbers of operations have to be done on every job in many manufacturing and assembly facilities. However, it is seldom discussed in the general multiple-machine setting, especially without the assumptions of identical processing time on all the machines or dominant machines. With the current emphasis of customer service and meeting the promised delivery dates, we consider a permutation flowshop scheduling problem with learning effects where the objective is to minimize the total tardiness. A branch-and-bound algorithm and two heuristic algorithms are established to search for the optimal and near-optimal solutions. Computational experiments are also given to evaluate the performance of the algorithms.     

Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem

We consider the multistage hybrid flowshop scheduling problem, in which each stage consists of parallel identical machines. The problem is to determine a schedule that minimizes the makespan for a given set of jobs over a finite planning horizon. Since this problem class is NP-hard in the strong sense, there seems to be no escape from appealing to heuristic procedures to achieve near-optimal solutions to real life problems. First, a series of new global lower bounds to be used to estimate the minimum makespan are derived. Then, two new metaheuristic algorithms first sequence and then allocate jobs to machines based on a particular partition of the shop. The optimization procedure is based on simulated annealing and the variable-depth search. Computational experiments show the efficiency of the proposed procedures.     

Two-machine flowshop scheduling with a truncated learning function to minimize the makespan

Scheduling with learning effects has continued to attract the attention of scheduling researchers. However, the majority of the research on this topic has been focused on the single-machine setting. Moreover, under the commonly adopted learning model in scheduling, the actual processing time of a job drops to zero precipitously as the number of jobs increases, which is at odds with reality. To address these issues, we study a two-machine flowshop scheduling problem with a truncated learning function in which the actual processing time of a job is a function of the job's position in a schedule and the learning truncation parameter. The objective is to minimize the makespan. We propose a branch-and-bound and three crossover-based genetic algorithms (GAs) to find the optimal and approximate solutions, respectively, for the problem. We perform extensive computational experiments to evaluate the performance of all the proposed algorithms under different experimental conditions. The results show that the GAs perform quite well in terms of both efficiency and solution quality.     

A note on constructive heuristics for the flowshop problem with blocking

This paper analyzes 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. As the problem is NP-hard, a constructive heuristic that explores specific characteristics of the problem is developed. The small computational effort of such strategy, which is valuable in practical applications, is one of the reasons that motivated this study. The performance of a combination of the proposed method with existing ones is examined through a comparative study. The new methods outperform the NEH algorithm, currently the best constructive heuristic for this problem, in problems with up to 500 jobs and 20 machines.     

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.     

Heuristics for operational fixed job scheduling problems with working and spread time constraints

Operational fixed job scheduling problems select a set of jobs having fixed ready and processing times and schedule the selected jobs on parallel machines so as to maximize the total weight. In this study, we consider working time and spread time constrained versions of the operational fixed job scheduling problems. The working time constraints limit the total processing load on each machine. The spread time constraints limit the time between the start of the first job and the finish of the last job on each machine. For the working time constrained problem, we present a filtered beam search algorithm that evaluates the promising nodes of the branch and bound tree. For the spread time constrained problem we propose a two phase algorithm that defines the promising sets for the first jobs and finds a solution for each promising set. The results of our computational tests reveal that our heuristic algorithms perform very well in terms of both solution quality and time.     

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.     

Order acceptance and scheduling in a two-machine flowshop

We study the order acceptance and scheduling problem in a two-machine flowshop. The firm receives a pool of orders before a planning period, each of which is characterized by revenue, processing times on machines 1 and 2, a due date, and a tardiness penalty. The firm seeks to decide on the orders to accept and schedule the accepted orders so as to maximize the total net revenue. We formulate the problem as mixed-integer linear programming models, and develop a heuristic and a branch-and-bound (B&B) algorithm based on some derived dominance rules and relaxation techniques. We assess the performance of the B&B algorithm and the heuristic via computational experiments. The computational results show that the B&B algorithm can solve problem instances with up to 20 jobs within a reasonable time while the heuristic is efficient in approximately solving large instances of the problem.     

Simultaneous dock assignment and sequencing of inbound trucks under a fixed outbound truck schedule in multi-door cross docking operations

This paper studies the simultaneous dock assignment and sequencing of inbound trucks for a multi-door cross docking operation with the objective to minimize total weighted tardiness, under a fixed outbound truck departure schedule. The problem is newly formulated and solved by six different metaheuristic algorithms, which include simulated annealing, tabu search, ant colony optimization, differential evolution, and two hybrid differential-evolution algorithms. To evaluate the total weighted tardiness associated with any given inbound-truck sequence and dock assignment, an operational policy is developed. This policy is employed by every metaheuristic algorithm in searching for the optimal dock assignment and sequence. Each metaheuristic algorithm is tested with 40 problems. The major conclusions are: (1) metaheuristic is generally an effective optimization method for the subject problem; (2) population based metaheuristic algorithms are generally more effective than projection based metaheuristic algorithms; (3) proper selection of algorithmic parameters is important and more critical for projection based metaheuristic algorithms than population based algorithms; (4) the two best algorithms are ant colony optimization and hybrid differential evolution 2; among them, ACO takes less time than hybrid 2 and thus can be declared the best among all the six metaheuristic algorithms tested.     

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.     

Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multiprocessor tasks

This paper addresses the problem of multiprocessor task-scheduling in a hybrid flow shop (HFS) problem to minimize the makespan. Due to the complex nature of an HFS problem, it is decomposed into the following two sequential decision problems: determining the job permutation in stage 1, followed by a decoding method to assign jobs into each machine in subsequent stages when designing a heuristic algorithm. The decoding method plays a pivotal role for improving the solution quality of any algorithm for the HFS problem. However, the majority of existing algorithms ignores the problem and is only concerned with the first decision problem. This study emphasizes the importance of the decoding method via a small test, and searches for a number of solid decoding methods that can be incorporated into the cocktail decoding method. Then, this study develops a particle swarm optimization (PSO) algorithm that can be combined with the cocktail decoding method. In the PSO, a variety of job sequences are generated using the PSO procedure in stage 1, and the cocktail decoding method is used to assign the jobs to machines in sequential stages. Moreover, a modified lower bound is introduced. Computational results show that the proposed lower bound is competitive, and with the help of the cocktail decoding method, the proposed PSO, and even the adoption of a standard PSO framework, significantly outperforms the majority of existing algorithms in terms of quality of solutions, especially for large problems.     

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 bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system

We analyze a two-machine flow-shop scheduling problem in which the job processing times are controllable by the allocation of resources to the job operations and the resources can be used in discrete quantities. We provide a bicriteria analysis of the problem where the first criterion is to maximize the weighted number of just-in-time jobs and the second criterion is to minimize the total resource consumption cost. We prove that although the problem is known to be NP-hard even for constant processing times, a pseudo-polynomial time algorithm for its solution exists. In addition, we show how the pseudo-polynomial time algorithm can be converted into a two-dimensional fully polynomial approximation scheme for finding an approximate Pareto solution.     

Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine

This study deals with the problem of scheduling jobs on a single machine to minimize the mean absolute deviation of the job completion time about a large common due window subject to the maximum tardiness constraint. Using the well-known three-field notation, the problem is identified as MAD/large DueWindow/T_max. The common due window is set to be large enough to allow idle time prior to the beginning of a schedule to investigate the effect of the T_max constraint. Penalties arise if a job is completed outside the due window. A branch and bound algorithm and a heuristic are proposed. Many properties of the solutions and precedence relationships are identified. Our computational results reveal that the branch and bound algorithm is capable of solving problems of up to 50 jobs and the heuristic algorithm yields approximate solutions that are very close to the exact solution.     

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.     

Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity

Due-window assignment and production scheduling are important issues in operations management. In this study we investigate the problem of common due-window assignment and scheduling of deteriorating jobs and a maintenance activity simultaneously on a single-machine. We assume that the maintenance duration depends on its starting time. We provide polynomial time solutions for the problem and some of its special cases, where the objective is to simultaneously minimize the earliness, tardiness, due-window starting time, and due-window size costs.     

Logistics scheduling to minimize inventory and transport costs

We study a logistics scheduling problem where a manufacturer receives raw materials from a supplier, manufactures products in a factory, and delivers the finished products to a customer. The supplier, factory and customer are located at three different sites. The objective is to minimize the sum of work-in-process inventory cost and transport cost, which includes both supply and delivery costs. For the special case of the problem where all the jobs have identical processing times, we show that the inventory cost function can be unified into a common expression for various batching schemes. Based on this characteristic and other optimal properties, we develop an O(n) algorithm to solve this case. For the general problem, we examine several special cases, identify their optimal properties, and develop polynomial-time algorithms to solve them optimally.     

Two-machine flow shop scheduling of polyurethane foam production

This paper studies a two-machine flow shop scheduling problem with a supporting precedence relation. The model originates from a real production context of a chemical factory that produces foam-rubber products. We extend the traditional two-machine flow shop by dividing the operations into two categories: supporting tasks and regular jobs. In the model, several different compositions of foam rubber can be mixed at the foam blooming stage, and products are processed at the manufacturing stage. Each job (product) on the second machine cannot start until its supporting tasks (parts) on the first machine are all finished and the second machine is not occupied. The objective is to find a schedule that minimizes the total job completion time. The studied problem is strongly NP-hard. In this paper, we propose a branch-and-bound algorithm incorporating a lower bound and two dominance rules. We also design a simple heuristic and an iterated local search (ILS) algorithm to derive approximate solutions. The performances of the proposed algorithms are examined through computational experiments.     

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.     

Production planning of a hybrid manufacturing-remanufacturing system under uncertainty within a closed-loop supply chain

This paper deals with the production planning and control of a single product involving combined manufacturing and remanufacturing operations within a closed-loop reverse logistics network with machines subject to random failures and repairs. While consumers traditionally dispose of products at the end of their life cycle, recovery of the used products may be economically more attractive than disposal, while remanufacturing of the products also pursues sustainable development goals. Three types of inventories are involved in this network. The manufactured and remanufactured items are stored in the first and second inventories. The returned products are collected in the third inventory and then remanufactured or disposed of. The objective of this research is to propose a manufacturing/remanufacturing policy that would minimize the sum of the holding and backlog costs for manufacturing and remanufacturing products. The decision variables are the production rates of the manufacturing and the remanufacturing machines. The optimality conditions are developed using the optimal control theory based on stochastic dynamic programming. A computational algorithm, based on numerical methods, is used for solving the optimal control problem. Finally, a numerical example and a sensitivity analysis are presented to illustrate the usefulness of the proposed approach. The structure of the optimal control policy is discussed depending on the value of costs and parameters and extensions to more complex reverse logistics networks are discussed.