Search

In this paper, we address the assembly flowshop scheduling problem, which is a generalisation of two well-known scheduling problems in the literature: the three-stage Assembly Scheduling Problem (ASP) and its variant with two stages denoted as the two-stage ASP. For this problem, we prove several theoretical results which are used to propose a speed-up procedure. This acceleration mechanism can be applied in any insertion-based method for the problem under study and, consequently, also for their special cases. In addition, we propose four efficient constructive heuristics for the problem, based on both Johnson’s algorithm and the NEH heuristic. These proposals are compared against 47 algorithms existing in the literature for related problems. The results show the excellent performance of the proposals.

Purpose This paper aims to define the class of fragment constructive heuristics used to compute feasible solutions for the traveling salesman problem (TSP) into edge-greedy and vertex-greedy subclasses. As these subclasses of heuristics can create subtours, two known methodologies for subtour elimination on symmetric instances are reviewed and are expanded to cover asymmetric problem instances. This paper introduces a third novel subtour elimination methodology, the greedy tracker (GT), and compares it to both known methodologies. Design/methodology/approach Computational results for all three subtour elimination methodologies are generated across 17 symmetric instances ranging in size from 29 vertices to 5,934 vertices, as well as 9 asymmetric instances ranging in size from 17 to 443 vertices. Findings The results demonstrate the GT is the fastest method for preventing subtours for instances below 400 vertices. Additionally, a distinction between fragment constructive heuristics and the subtour elimination methodology used to ensure the feasibility of resulting solutions enables the introduction of a new vertex-greedy fragment heuristic called ordered greedy. Originality/value This research has two main contributions: first, it introduces a novel subtour elimination methodology. Second, the research introduces the concept of ordered lists which remaps the TSP into a new space with promising initial computational results.

Scheduling in distributed production system has become an active research field in recent years. This paper investigates the distributed assembly blocking flow-shop scheduling problem (DABFSP), which consists of two stages: production and assembly. The first stage is processing jobs in several identical factories. Each factory has a series of machines no intermediate buffers existing between adjacent ones. The second stage assembles the processed jobs into the final products through a single machine. The objective is to minimize the maximum completion time or makespan of all products. To address this problem, a constructive heuristic is proposed based on a new assignment rule of jobs and a product-based insertion procedure. Afterwards, an iterated local search (ILS) is presented, which integrates an integrated encoding scheme, a multi-type perturbation procedure containing four kinds of perturbed operators based on problem-specific knowledge and a critical-job-based variable neighborhood search. Finally, a comprehensive computational experiment and comparisons with the closely related and well performing methods in the literature are carried out. The experimental and comparison results show that the proposed constructive heuristic and ILS can solve the DABFSP effectively and efficiently.

In this paper, production scheduling for rotomoulded plastics manufacturing in a multi-machine environment is considered. The objective is to minimise total tardiness. The problem has some commonality with hybrid flow shop scheduling with batching, where additional constraints are needed to control which machines may be used at each stage. The problem is shown to be NP-hard and is formulated as a mixed integer program. Given consequently large solve times to obtain optimal solutions, simulated annealing and tabu search algorithms were developed alongside a constructive heuristic to obtain near-optimal solutions within a practical time-frame. The solution algorithms were tuned and tested using randomly generated problem instances. The best results in terms of solution quality were generally obtained by simulated annealing. The problem instances were generated to be representative of a real production environment located in Queensland, Australia.

The problem of routing and wavelength assignment in optical networks consists in minimizing the number of wavelengths that are needed to route a set of demands, such that demands routed using lightpaths that share common links are assigned to different wavelengths. We present a biased random-key genetic algorithm for approximately solving the problem of routing and wavelength assignment of sliding scheduled lightpath demands in optical networks. In this problem variant, each demand is characterized not only by a source and a destination, but also by a duration and a time window in which it has to be met. Computational experiments show that the numerical results obtained by the proposed heuristic improved upon those obtained by a multistart constructive heuristic. In addition, the biased random-key genetic algorithm obtained much better results than an existing algorithm for the problem, finding solutions that use roughly 50% of the number of wavelengths determined by the latter.

In a recent paper, a solution approach to the Maximum Happy Vertices Problem has been proposed. The approach is based on a constructive heuristic improved by a matheuristic local search phase. We propose a new procedure able to outperform the previous solution algorithm both in terms of solution quality and computational time. Our approach is based on simple ingredients implying as starting solution generator an approximation algorithm and as an improving phase a new matheuristic local search. The procedure is then extended to a multi-start configuration, able to further improve the solution quality at the cost of an acceptable increase in computational time.

Due to the extensive applications of the flowshop sequence-dependent group scheduling problem(FSDGSP), especially in the manufacturing industry, there has been a growing interest in the research of it. In this paper, a constructive heuristic called JPALRx is proposed for solving FSDGSP with total flow time criterion. In the JPALRx, a sequence of part families is determined by a jigsaw puzzle inspired algorithm considering major family setup times. Afterwards, a job sequence within each part family is obtained by using a heuristic algorithm called LRx. Furthermore, an insert operator based on family is used to further improve the quality of the solution obtained. The experimental results demonstrate the effectiveness and efficiency of JPALRx.

There has been intensive research on tiebreakers for insertion-based constructive heuristics in the permutation flow shop scheduling problem when the objective is to minimize the makespan. In this paper we analyze the space of all possible tie-breaking rules for the most common insertion orders, and evaluate the efficacy of existing tiebreakers based on this analysis. We find that an optimal tie breaker would produce results that are about 1% better than current best tie breakers. We propose a constructive heuristic based on a truncated cyclic best-first search in the space of all tie breakers and show that it closely approximates the solutions that such an optimal tie breaker can achieve.

As the number and severity of snowfall events continue to grow, the need to direct road maintenance intelligently during these snowfall events will also grow. In several locations, local governments lack the resources to treat all roadways completely during snow events. Furthermore, some governments utilize only traffic data to determine which roads should be treated. As a result, many schools, businesses, and government offices must be unnecessarily closed, which directly impacts the social, educational, and economic well-being of citizens and institutions. In this work, we propose a mixed integer programming (MIP) formulation to allocate resources to manage snowfall on roads using meteorological, geographical, and environmental parameters. Given that MIPs often scale poorly with problem size, we also present a constructive heuristic designed for the problem. Additionally, we evaluate the impacts of an increase in budget for winter road maintenance on snow control resources.

In this paper, we address the multiple operating room (OR) surgical case sequencing problem (SCSP). The objective is to maximise total OR utilisation during standard opening hours. This work uses a case study of a large Australian public hospital with long surgical waiting lists and high levels of non-elective demand. Due to the complexity of the SCSP and the size of the instances considered herein, heuristic techniques are required to solve the problem. We present constructive heuristics based on both a modified block scheduling policy and an open scheduling policy. A number of real-time reactive strategies are presented that can be used to maintain schedule feasibility in the case of disruptions. Results of computational experiments show that this approach maintains schedule feasibility in real-time, whilst increasing operating theatre (OT) utilisation and throughput, and reducing the waiting time of non-elective patients. The framework presented here is applicable to the real-life scheduling of OT departments, and we provide recommendations regarding implementation of the approach.

We propose a polylithic method for medium-term scheduling of a large-scale industrial plant operating in a continuous mode. The method combines a decomposition approach, a genetic algorithm (GA) an...

The effective scheduling of multiple agile earth observation satellites plays a key role in improving the efficiency of the agile satellite observation system. Due to the complex constraints and large solution space (increases exponentially with the problem size), it has been a big challenge to effectively solve the multiple agile satellites scheduling problem. In this study, an edge computing framework is proposed in order to solve this problem in a flexible manner. In this framework, a central node and several edge nodes are included. The central node corresponds to the operation center of the satellite observation system while each edge node corresponds to an agile satellite. The central node filters tasks for edge nodes according to the time of scheduling period and visible time windows. Tasks in each edge node are scheduled according to the order of scheduling periods by a constructive heuristic algorithm based on the density of residual tasks (HADRT). The efficiency of this algorithm is proved. The time and space complexity are analyzed in detail. The proposed method is compared with other three advanced methods, and the experimental results show that HADRT could achieve higher task completion rate and reward rate than other algorithms with acceptable computing time.

As the first and the most time consuming step of product recovery, disassembly is described as the systematic separation of constituent parts from end-of-life products through a series of operations. In this context, designing and balancing disassembly lines are critical in terms of the efficiency of product recovery. Recent research on disassembly line balancing (DLB) has focused on classical stations where only one worker is allocated. However, such a line results in larger space requirement and longer disassembly lead time. In this paper, disassembly line balancing problem (DLBP) with multi-manned stations is introduced to the relevant literature as a solution to overcome these disadvantages. A mixed integer linear programming (MILP) model and two novel framework heuristic algorithms are developed to minimise the number of workers and workstations. MILP model has been applied to a dishwasher disassembly system. The application results indicate the superiority of establishing multi-manned stations over classical disassembly system design with single-worker stations with shorter disassembly lead time (80.9%) and line length (60.2%). Moreover, the proposed heuristics have been compared on newly generated test problems (instances) for DLBP. The results validate that the heuristics provide acceptable solutions in a reasonable amount of time even for large-sized problems.

Increasing global energy consumption, large variations in its cost and the environmental degradation effects are good reasons for the manufacturing industries to become greener. Green shop floor sc...

The distributed hybrid flowshop scheduling problem (DHFSP) is derived from the hybrid flowshop scheduling problem (HFSP), which involves two scheduling assignment decisions—assignment of jobs to factories and scheduling jobs in each factory. DHFSP is encountered in many practical industry applications recently. The standard DHFSP has never been discussed in any previous literature, and it is addressed first addressed in this work. In this paper, the mixed-integer linear programming (MILP) model is proposed. An improved discrete artificial bee colony (DABC) algorithm for minimizing makespan is proposed as well. Novel encoding and decoding methods are developed for DHFSP. The constructive heuristic, an improved NEH heuristic, is employed to build high quality and diversified solutions for the initial population. Two neighborhood search methods based on swap and insertion neighborhood structures are proposed for DHFSP. Comprehensive computational comparisons and statistical analysis demonstrate the effectiveness of the proposed DABC algorithm when compared with a genetic algorithm (GA) and an iterated greedy (IG) algorithm.

A state estimation process is highly influenced by the level of the measurement redundancies. However, due to financial and operational constraints, redundancy is in practice limited, making the power systems metering design a challenging problem. Therefore, for the first time, a methodology to design a metering system for state estimation in power systems is proposed, in which the metering placement is modeled as a combinatorial constrained optimization problem, where the final goal is to maximize the system redundancy – expressed by observability indicators – subjected to investment constraints. A Genetic Algorithm and a Greedy Randomized Adaptive Search Procedure, combined with a constructive heuristic are investigated for the metering design problem. Tests with IEEE-14, IEEE-30, IEEE-118 bus systems and part of a real Brazilian system are carried out to evaluate the performance of the proposed methodology. The results also show that, for the IEEE-118 bus system, 30% of the total cost of the measurements and RTUs is required to ensure observability, whereas 32% and 60% are necessary to eliminate the network critical measurements and to obtain a system without critical sets, respectively.

With the trend of manufacturing globalization, distributed production has attracted wide attention from the industry and academia. Nevertheless, there has been little research on the distributed hybrid flowshop scheduling (DHFS) problem. To make up for the gap, this study aims to solve the DHFS problem, in which multiple factories with hybrid flowshop scheduling (HFS) problems are considered. This problem consists of two subproblems: 1) how to choose a factory for each job and 2) how to schedule all jobs within the assigned factories. To solve the DHFS problem, a mathematical model is formulated. Then, inspired by successful applications of brain storm optimization (BSO) algorithm in different fields, we try to solve the DHFS with a hybrid BSO (HBSO). In the proposed algorithm, firstly, a new approach to calculate the distance in the procedure of clustering is embedded. Then, a novel constructive heuristic based on the Nawaz-Enscore-Ham (NEH) method, called distributed NEH, is proposed. Moreover, an improved crossover operator based on the partial-mapped crossover (PMX) is designed for the distributed scheduling problem. Finally, the 20 large-scale instances based on the realistic production data are randomly generated to test the performance of the proposed algorithm. The experimental results verify that the proposed algorithm is efficient and effective for solving the considered DHFS problems in comparison with the other recently published efficient algorithms.

This paper addresses the hybrid flow shop scheduling problem to minimise makespan, a well-known scheduling problem for which many constructive heuristics have been proposed in the literature. Nevertheless, the state of the art is not clear due to partial or non homogeneous comparisons. In this paper, we review these heuristics and perform a comprehensive computational evaluation to determine which are the most efficient ones. A total of 20 heuristics are implemented and compared in this study. In addition, we propose four new heuristics for the problem. Firstly, two memory-based constructive heuristics are proposed, where a sequence is constructed by inserting jobs one by one in a partial sequence. The most promising insertions tested are kept in a list. However, in contrast to the Tabu search, these insertions are repeated in future iterations instead of forbidding them. Secondly, we propose two constructive heuristics based on Johnson’s algorithm for the permutation flowshop scheduling problem. The computational results carried out on an extensive testbed show that the new proposals outperform the existing heuristics.

The quest for a lower operational cost of daily scheduling cascade hydropower generation is subject to imperfections in the representation of reality due to it multiple uncertainties. One way to reduce uncertainties is to improve the representation of the hydrological processes and the operation of the electrical components of the system. A complementary strategy to deal with the difficulty of representing hydrological processes is to move from a deterministic approach to a probabilistic approach considering scenarios. These two proposals usually lead to high-dimensional problems that require Mixed Integer Nonlinear Programming for solving. This work proposes the use of simple Constructive Heuristics to solve this kind of problem guarding the non-linear formulations. The GAMS software was used to represent a hydropower cascade with individualized turbine with multiple inflow scenarios as presented in the formulation bellow. For each scenario s:Z is the objective function. a is a coefficient considered in the proposed Constructive Heuristic. Q is the outflow of the turbine. H is the set of hydropower plants. U is the set of turbines. t is the set of hours considered in the problem. s is the set of considered scenarios. α is a conversion term. τ is the time delay of the hydropower plants. β is the set of hydropower plants located upstream of a hydropower plant. I is the incremental flow. V is the volume of the reservoir. D is the power demand. Pg is power generated per turbine. Pmin and Pmax are the thresholds of power of the turbine. Pst is the net power generated by the turbine. Pgg are the electrical losses of the generator. Pmt are the mechanical losses of the generator. f1, f2, f3, f4, f5, f6, f7 and f8 are functions. HH is the hydraulic net head. UP is the upstream level. Down is the downstream level. Lo are the hydraulic and mechanical losses. ρ is the turbine efficiency curve. The CONOPT solver was selected for it resolution. The Constructive Heuristic scheme considers a continuous variable “a” to represent if the turbine is opened or closed. After the first resolution of the problem with Nonlinear Programming, the integer part number of turbines for each power plant is fixed. The fractional part is tested for all the possible configurations and the best outcome is chosen. The results of the Constructive Heuristic were compared with other similar works with perfect correspondence. The system was tested for 51 ECMWF precipitation forecast scenarios as input of the hydrologic model MGB (Large Basin Model) with coherent results. The proposal is a feasible approach to reach unique optimal solutions for high-dimensional non-linear problems considering integer variables.

In the previous chapter, we arrived at the inconvenient conclusion that no polynomial-time algorithm exists for solving the graph colouring problem. The fact that graph colouring is “intractable” in this way implies that there is a limited amount that we can say about the chromatic number of an arbitrary graph. One simple rule is that, given a graph G with n vertices and m edges, if \(m>\lfloor n^2/4\rfloor \) then \(\chi (G)\ge 3\), since any graph meeting this criterion must contain a triangle and therefore cannot be bipartite [1]. However, as we saw in the previous chapter, even the problem of deciding whether \(\chi (G)=3\) is \(\mathcal {NP}\)-complete for arbitrary graphs. In this chapter, we will review several upper and lower bounds on the chromatic number. We will also examine five different constructive heuristics for the graph colouring problem.

This paper deals with the distributed flowshop group scheduling problem to minimize the total flowtime. By analyzing the problem-specific knowledge, the longest processing time rule (LPT) and the shortest processing time rule (SPT), we present a total of 20 constructive heuristics including 8 simple heuristics, 8 combinative heuristics, and 4 NEH-based heuristics for solving the problem at a reasonable computational effort. We carry out extensive computational evaluations based on the 405 instances. The results show that the proposed algorithms are very effective for solving the problem under consideration. Among them, the NEH-based heuristic using SPT in the job sorting process and LPT in the group sorting process performs best.

In this paper, we address the exact solution of the vertex bisection problem (VBP). We propose two novel B&B algorithms to solve VBP, which include new upper and lower bound constructive heuristics, and an efficient strategy to explore the combinatorial search space. The computational results show that the proposed algorithms clearly outperforms the state-of-the-art B&B algorithm in quality and efficiency. The two proposed B&B versions differ in the exploration strategy and the storage of the search tree. Also, we provide four new solutions, previously unknown. We consider that the main contributions of this work can be adapted to solve combinatorial problems in other related domains.

The tasks of rational cutting-packaging have long attracted the attention of researchers and practitioners in various industries. They are classified as NP-complete problems. In this paper, three-dimensional orthogonal cutting-packing is considered as the main one. The mathematical model is given. The paper presents a heuristic algorithm. The features of the method are the direct solution of the problem, and not its reduction to problems of a smaller dimension; the use of layered strategies; filling in the so-called priority axes; analysis of voids and consideration of ways to combine them; use of several parallelepipeds. The performed computational experiments confirm the effectiveness of the proposed method.

We propose a new memetic algorithm to minimize the makespan for the flowshop scheduling problem in two variants: the classic permutation setting and the no-wait statement. Our algorithm hybridizes the local search technique into the framework of a steady-state genetic algorithm. A local search heuristic is applied on each iteration and explores the insertion neighborhood. The execution of the local search is parallelized using the CUDA framework for Graphics Processing Units. The initial population is constructed by means of greedy constructive heuristics. A computational experiment on the benchmark instances shows that the proposed algorithm yields results competitive to those of well-known algorithms for the flowshop problem.

Hybrid flow shop (HFS) systems represent the typical flow shop production system with parallel machines on at least one stage of operation. This paper considers unrelated machines and anticipatory sequence-dependent setup times where job families can be formed based on similar setup characteristics. This results in the opportunity to save setups if two jobs of the same family are scheduled consecutively. Three constructive heuristic approaches, aiming at minimization of makespan, total completion time and the total number of setup procedures, are implemented based on the algorithm of Nawaz, Enscore and Ham (NEH).

Flowshop scheduling problem with bicriteria of makespan and idle time under no-wait constraint is addressed in this paper. The problem of flowshop scheduling environment with criteria of minimum makespan and idle time is NP-hard under no-wait constraint; therefore, heuristic algorithms are key to obtain the solutions of these problems near to optimal. The paper describes a heuristic technique to schedule the sequence of n jobs on m machine in no-wait flowshop environment with objective of minimizing both makespan and idle time. Computation results show the better solution quality of proposed heuristic approach over existing constructive heuristics.

With growth in air transportation expected to continue, the mitigation of operational inefficiency and consequent delays is becoming increasingly important. Slot allocation, as a means of demand management at congested airports, has a significant impact on wider airport operations. This requires sophisticated approaches, to intelligently allocate scarce airport resources to unevenly distributed traffic demand for the use of airport facilities. This paper presents a novel heuristic approach to solve the single airport slot allocation problem. The approach has been tested on real-world data from three medium-sized airports. We introduce a constructive heuristic framework which is able to generate feasible solutions to the model. Within this framework, a number of ordering heuristics are developed to order slot requests to be scheduled, and an allocation algorithm is developed to allocate slots to a request determined by the ordering heuristic. Experimental results suggest that the order in which slot requests are scheduled has a significant impact on the solution quality.

Balancing trade-offs between production cost and holding cost is critical for production and operations management. Utilization of a production line affects production cost, which relates to makespan, and work-in-process (WIP) inventories in a production line affect holding cost, which relate to flowtime. There are trade-offs between two objectives, to minimize makespan and to minimize flowtime. Without addressing trade-off balancing issues in flow shop scheduling, WIP inventories are still high in manufacturing, generating unnecessary holding cost. However, utilization is coupled with WIP inventories. Low WIP inventory levels might lower utilization and generate high production cost. Most existing constructive heuristics focus only on single-objective optimization. In the current literature, the NEH heuristic proposed by Nawaz, Enscore, and Ham (1983) is the best constructive heuristic to minimize makespan, and the LR heuristic proposed by Liu and Reeves (2001) is the best to minimize flowtime. In this paper, we propose a current and future deviation (CFD) heuristic to balance trade-offs between makespan and flowtime minimizations. Based on 5400 randomly generated instances, 120 instances in Taillard’s benchmarks, and one-year historical records of operating room scheduling from University of Kentucky HealthCare (UKHC), our CFD heuristic outperforms the NEH and LR heuristics on trade-off balancing, and achieves the most stable performances from the perspective of statistical process control (SPC).

This paper considers the allocation of slots for a network of coordinated (congested) airports, where the term “slot” refers to a time on a specific day when a carrier is given permission to use the full range of airport infrastructure for the purpose of landing and take-off at a slot-controlled airport. We take into account the existing IATA rules and guidelines: priorities of requests for slots, the capacity limitations at each airport, the minimal turnaround time between arrival and subsequent departure of the same aircraft, and allocation to series of slots rather than to individual slots. Given the complexity of the problem, we propose an approach that consists of (i) a constructive heuristic procedure to generate a feasible and coherent allocation of slots for each airport from the network, and (ii) an iterative heuristic to improve the quality of an initial feasible solution in terms of the schedule delay (time difference between allocated time slots and airline requests). To evaluate whether the approach would be practical in real operation, we perform tests on a set of generated benchmark instances that span an entire scheduling season. The instances differ by the number of airports in the network and by the distribution of requests among airports from a given network - the largest number of airports forming a network is 100, while the maximum total number of aircraft movements considered on a half-yearly basis exceeds 4.6 · 10 6 . We provide computational comparisons with solutions obtained when each airport from a network is considered independently (the en-route constraint is ignored). These results reveal that the consideration of the en-route constraint, which ensures a coherent allocation of slots at origin and destination airports, introduces only a minor degradation in the schedule delay and in the number of unaccommodated requests. Furthermore, we investigate the heuristic performance for reduced-capacity scenarios.

We introduce a new generalization of the traveling salesman problem with pickup and delivery, that stems from applications in maritime logistics, in which each node represents a port and has a known draft limit. Each customer has a demand, characterized by a weight, and pickups and deliveries are performed by a single ship of given weight capacity. The ship is able to visit a port only if the amount of cargo it carries is compatible with the draft limit of the port. We present an integer linear programming formulation and we show how classical valid inequalities from the literature can be adapted to the considered problem. We introduce heuristic procedures and a branch-and-cut exact algorithm. We examine, through extensive computational experiments, the impact of the various cuts and the performance of the proposed algorithms.

The objective of the weapon target assignment (WTA) problem is to maximize the total damage of targets or minimize the total consumption of weapons. However, the existing studies of the WTA problem did not consider the uncertainty of weapon adequacy in practical battlefield scenarios. In this paper, we study a novel WTA problem, called the WTA problem with uncertainty (WTAU), and the uncertainty refers to the uncertainty of weapon adequacy. The objective of the WTAU is to find a WTA scheme to maximize the total value of destroyed targets by using as few weapons as possible in situations where the adequacy of weapons is uncertain. To address the uncertainty of weapons adequacy, we formulate the WTAU problem as a nonlinear integer programming model. To improve the computing efficiency, we design a two-stage hybrid heuristic search (TSHHS) algorithm based on prior WTAU knowledge. In the first stage of the TSHHS algorithm, a logarithmic transformation method is employed to obtain the optimal target destruction (TD) scheme and an initial WTA scheme. In the second stage, a constructive heuristic method based on the maximum marginal return (MMRBH) and a simple optimization (SimpleO) method are developed to obtain a promising WTA scheme. Moreover, we perform extensive experiments to analyze the performance of the proposed method. The results of numerical experiments show that the proposed method can provide a high-quality WTA scheme with a short computing time in scenarios involving adequate or inadequate weapons.

In this paper, we address the 2-stage assembly scheduling problem where there are m machines in the first stage to manufacture the components of a product and one assembly station (machine) in the second stage. The objective considered is the minimisation of the total completion time. Since the NP-hard nature of this problem is well-established, most previous research has focused on finding approximate solutions in reasonable computation time. In our paper, we first review and derive a number of problem properties and, based on these ideas, we develop a constructive heuristic that outperforms the existing constructive heuristics for the problem, providing solutions almost in real-time. Finally, for the cases where extremely high-quality solutions are required, a variable local search algorithm is proposed. The computational experience carried out shows that the algorithm outperforms the best existing metaheuristic for the problem. As a summary, the heuristics presented in the paper substantially modify the state-of-the-art of the approximate methods for the 2-stage assembly scheduling problem with total completion time objective.

In recent years, stricter environmental regulations, as well as an increased public concern, have progressively forced new landfills to be located more and more away from urban centers. This has stimulated the use of solid waste transfer stations, where the solid waste is transferred from small collection vehicles to large transportation vehicles. In this paper, we tackle the problem of determining the routes for both collection and transportation vehicles, as well as their synchronization at the transfer stations. We divide the problem into two phases and propose an exact approach utilizing a mathematical formulation, as well as a constructive heuristic and a matheuristic for the first phase, and a heuristic approach for the second phase. Computational results show that the approach combining the matheuristic for the collection phase with the heuristic for the transportation phase is able to achieve consistent reductions in terms of number of collection vehicles needed.

Dynamic lotsizing and scheduling on multiple lines to meet the customer due dates is significant in multi-line production environments. Therefore, this study investigates dynamic lotsizing and scheduling problems in multiple flexible machining lines considering mixed products. In addition, uncertainty in demand and machine failure is considered. A mathematical model is proposed for the considered problem with an aim to maximize the probability of completion of product models from different customer orders. A constructive heuristic method (CHLP) is proposed to solve the current problem. The proposed heuristic involves the steps to distribute different customer order demands among multiple lines and schedule them considering balancing of makespan between the lines. The performance of CHLP is measured with famous heuristics from the literature, based on the test problem instances. Results indicate that CHLP gives better results in terms of quality of results as compared to other famous literature heuristics.

The scheduling problems under distributed production or flexible assembly settings have achieved increasing attention in recent years. This paper considers scheduling the integration of these two environments and proposes an original distributed flowshop scheduling problem with flexible assembly and set-up time. Distributed production stage is deployed several homogeneous flowshop factories that process the jobs to be assembled into final products in the flexible assembly stage. The objective is to find a schedule, including a production subschedule for jobs and an assembly subschedule for products, to minimise the makespan. Such a scheduling problem involves four successive decisions: assigning jobs to production factories, sequencing jobs at every factory, designating an assembly machine for each product and sequencing products on each assembly machine. The computational model is first established, and then a constructive heuristic (TPHS) and two hybrid metaheuristics (HVNS and HPSO) are proposed. Numer...

This article is about seeking a good feasible solution in a reasonable amount of computation time to the three-dimensional Multiple Bin Size Bin Packing Problem (MBSBPP). The MBSBPP studied considers additional constraints encountered in real world air transportation situations, such as cargo stability and the particular shape of containers. This MBSBPP has already been formulated as a Mixed Integer linear Programming problem, but as yet only poor results have been achieved for even fairly small problem sizes. The goal of the work this paper describes is to develop heuristics that are able to quickly provide good initial feasible solutions for the MBSBPP. Three methodologies are considered, which are based on the decomposition of the original problem into easier subproblems: the matheuristics Relax-and-Fix, Insert-and-Fix and Fractional Relax-and-Fix. They have been parametrised on real data sets and then compared to each other. In particular, two of these techniques show promising results in reasonable computational times.

This study brings an implementation of a metaheuristic procedure to solve the Number Partitioning Problem (NPP), which is a classic NP-hard combinatorial optimization problem. The presented problem has applications in different areas, such as: logistics, production and operations management, besides important relationships with other combinatorial problems. This paper aims to perform a comparative analysis between the proposed algorithm with others metaheuristics using a group of instances available on the literature. Implementations of constructive heuristics, local search and metaheuristics ILS with path relinking as mechanism of intensification and diversification were made in order to improve solutions, surpassing the others algorithms.

This paper aims at minimizing total tardiness in a no-idle permutational flow shop environment. Even though this criterion is relevant for improving client satisfaction in production systems with strict due dates, no constructive heuristics have been developed for this specific problem so far. In this study, high performance constructive heuristics from related problems were adapted and compared to a new one proposed for the problem $${F_m}\left| {no - idle,prmu} \right|\mathop \sum{T}$$ . Computational experiments show that the new method significantly outperforms the adapted existing heuristics.

In this paper we present a beam-search-based constructive heuristic to solve the permutation flowshop scheduling problem with total flowtime minimisation as objective. This well-known problem is NP-hard, and several heuristics have been developed in the literature. The proposed algorithm is inspired in the logic of the beam search, although it remains a fast constructive heuristic.The results obtained by the proposed algorithm outperform those obtained by other constructive heuristics in the literature for the problem, thus modifying substantially the state-of-the-art of efficient approximate procedures for the problem. In addition, the proposed algorithm even outperforms two of the best metaheuristics for many instances of the problem, using much lesser computation effort. The excellent performance of the proposal is also proved by the fact that the new heuristic found new best upper bounds for 35 of the 120 instances in Taillard's benchmark.

Timetabling is one of the computationally difficult problems in scheduling and aims to find best time slots for a number of tasks which require limited resources. In this paper, we examine different solution approaches for the real-world examination timetabling problem (ETP) for university courses. The problem has unique hard and soft constraints, when compared to previous efforts, i.e. consecutive exams, sharing of rooms, room preferences, room capacity and number of empty slots. The aim of the problem is to achieve a timetable, which minimizes the total number of the examination slots without any conflicts. First, the real-world problem is formally defined and a mixed integer linear model is presented. Then, a constructive heuristic and a genetic algorithm based meta-heuristic are proposed in order to solve the ETP. Proposed approaches are tested on a problem set formed by using a real-life data. Results reveal that, proposed approaches are able to produce superior solutions in a limited time. Keywords: Timetabling, constructive heuristic, genetic algorithm

In this paper, we consider the time-dependent multi-depot vehicle routing problem. The objective is to minimize the total heterogeneous fleet cost assuming that the travel time between locations depends on the departure time. Also, hard time window constraints for the customers and limitation on maximum number of the vehicles in depots must be satisfied. The problem is formulated as a mixed integer programming model. A constructive heuristic procedure is proposed for the problem. Also, the efficiency of the proposed algorithm is evaluated on 180 test problems. The obtained computational results indicate that the procedure is capable to obtain a satisfying solution.

This paper addresses the minimization of makespan for the permutation flow shop scheduling problem with blocking and sequence and machine dependent setup times, a problem not yet studied in previous studies. The 14 best known heuristics for the permutation flow shop problem with blocking and no setup times are pre-sented and then adapted to the problem in two different ways; resulting in 28 different heuristics. The heuristics are then compared using the Taillard database. As there is no other work that addresses the problem with blocking and sequence and ma-chine dependent setup times, a database for the setup times was created. The setup time value was uniformly distributed between 1% and 10%, 50%, 100% and 125% of the processing time value. Computational tests are then presented for each of the 28 heuristics, comparing the mean relative deviation of the makespan, the computational time and the percentage of successes of each method. Results show that the heuristics were capable of providing interesting results.

In this paper, we consider a manufacturing system with two-machine no-wait flowshop scheduling problem where setup times are uncertain. The problem with the performance measure of maximum lateness was addressed in the literature (Computational and Applied Mathematics 37, 6774-6794) where dominance relations were proposed. We establish a new dominance relation and show that the new dominance relation is, on average, about 90 \begin{document}$ \% $\end{document} more efficient than the existing ones. Moreover, since it is highly unlikely to find optimal solutions for problems of reasonable size by utilizing dominance relations and since there exist no heuristic in the literature for the problem, we propose constructive heuristics to solve real life problems. We conduct extensive computational experiments to evaluate the proposed heuristics. Computational experiments indicate that the performance of the worst proposed heuristic is at least 20 \begin{document}$ \% $\end{document} better than a benchmark solution. Furthermore, they also indicate that the best proposed heuristic is about 130 \begin{document}$ \% $\end{document} better than the worst one. The average CPU time of the heuristics is significantly less than a second.

The distributed permutation flowshop scheduling problem (DPFSP) has been a hot issue in recent years. Due to the practical relevance of sequence-dependent setup time (SDST), we consider the DPFSP with SDST to minimize makespan. For the purpose, we propose three constructive heuristics and an effective discrete artificial bee colony (DABC) algorithm. All the heuristics are based on a greedy assignment rule and a local search of job blocks in each factory. In the local search, three different setup times are respectively considered for inserting a job block. In the DABC, to balance the local exploitation and the global exploration, we propose six composite neighborhood operators according to the problem characteristics. The first three are based on insertion and swap operators, and the second three have a close relationship with the critical factory. A problem-oriented local search method is developed to improve the best individual in the population. A comprehensive computational campaign against the closely related and state-of-the-art algorithms in the literature shows that both the proposed heuristics and DABC are very effective for solving the problem under consideration.

This paper studies the robust cyclic timetabling problem. The goal is to modify a given reference timetable to enhance its robustness against small stochastic disturbances. The robustness is measured by the expected total delay of the realised timetable. Kroon et al. (Transp Res Part B 42(6):553–570, 2008) propose a stochastic programming approach and implement it for Netherlands Railways (NS). While the model’s outcome is accepted by practitioners, relevant planning problems are rendered intractable by computation times of up to several days. In this paper we describe a Branch-and-Bound algorithm for solving the stochastic program of Kroon et al. (Transp Res Part B 42(6):553–570, 2008). We propose specific node selection rules, variable selection rules, constructive heuristics and lower bounds. We carry out computational tests on large real-life problem instances. The results confirm that our algorithm is able to considerably improve the robustness of the reference solutions. This is achieved with computation times of a few minutes. However, the weak lower bounds we use leave a considerable optimality gap. Therefore, our algorithm is best described as a heuristic solution method.

We address the blocking flow shop to minimise total flowtime.We conduct a comprehensive evaluation of a total of 35 heuristics.We propose an efficient constructive heuristic using a beam-search-based approach.We compare the proposal with the best-so-far algorithms for the problem. This paper focuses on the blocking flow shop scheduling problem with the objective of total flowtime minimisation. This problem assumes that there are no buffers between machines and, due to its application to many manufacturing sectors, it is receiving a growing attention by researchers during the last years. Since the problem is NP-hard, a large number of heuristics have been proposed to provide good solutions with reasonable computational times. In this paper, we conduct a comprehensive evaluation of the available heuristics for the problem and for related problems, resulting in the implementation and testing of a total of 35 heuristics. Furthermore, we propose an efficient constructive heuristic which successfully combines a pool of partial sequences in parallel, using a beam-search-based approach. The computational experiments show the excellent performance of the proposed heuristic as compared to the best-so-far algorithms for the problem, both in terms of quality of the solutions and of computational requirements. In fact, despite being a relative fast constructive heuristic, new best upper bounds have been found for more than 27% of Taillard's instances.

In this paper we address the problem of scheduling jobs in a permutation flowshop with a just-in-time objective, i.e. the minimisation of the sum of total tardiness and total earliness. Since the problem is NP-hard, there are several approximate procedures available for the problem, although their performance largely depends on the due dates of the specific instance to be solved. After an in-depth analysis of the problem, different cases or sub-problems are identified and, by incorporating this knowledge, four heuristics are proposed: a fast constructive heuristic, and three different local search procedures that use the proposed constructive heuristic as initial solution.The proposed Prod. Type: FLPheuristics have been compared on an extensive set of instances with the best-so-far heuristic for the problem, as well as with adaptations of efficient heuristics for similar scheduling problems. The computational results show the excellent performance of the proposed algorithms. Finally, the positive impact of the efficient heuristics is evaluated by including them as seed sequences for one of the best metaheuristic for the problem.