On a branch-and-bound approach for a Huff-like Stackelberg location problem

Modelling the location decision of two competing firms that intend to build a new facility in a planar market can be done by a Huff-like Stackelberg location problem. In a Huff-like model, the market share captured by a firm is given by a gravity model determined by distance calculations to facilities. In a Stackelberg model, the leader is the firm that locates first and takes into account the actions of the competing chain (follower) locating a new facility after the leader. The follower problem is known to be a hard global optimisation problem. The leader problem is even harder, since the leader has to decide on location given the optimal action of the follower. So far, in literature only heuristic approaches have been tested to solve the leader problem. Our research question is to solve the leader problem rigorously in the sense of having a guarantee on the reached accuracy. To answer this question, we develop a branch-and-bound approach. Essentially, the bounding is based on the zero sum concept: what is gain for one chain is loss for the other. We also discuss several ways of creating bounds for the underlying (follower) sub-problems, and show their performance for numerical cases. This work has been supported by the Ministry of Education and Science of Spain through grant SEJ2005/06273/ECON. M. Elena Sáz was supported by a junior research grant of Mansholt Graduate School (Wageningen Universiteit).     

A branch-and-bound algorithm for a two-stage hybrid flowshop scheduling problem minimizing total tardiness

A two-stage hybrid flowshop-scheduling problem is considered with the objective of minimizing total tardiness of jobs. In the hybrid flowshop, there is one machine at the first stage and multiple identical parallel machines at the second stage. Dominance properties and lower bounds are developed for the problem and a branch-and-bound algorithm is suggested using them. Results of computational experiments show that the suggested algorithm can find optimal solutions for problems with up to 15 jobs in a reasonable amount of central processing unit time.     

A novel branch-and-bound algorithm for the chance-constrained resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) has been widely studied during the last few decades. In real-world projects, however, not all information is known in advance and uncertainty is an inevitable part of these projects. The chance-constrained resource-constrained project scheduling problem (CC-RCPSP) has been recently introduced to deal with uncertainty in the RCPSP. In this paper, we propose a branch-and-bound (B&B) algorithm and a mixed integer linear programming (MILP) formulation that solve a sample average approximation of the CC-RCPSP. We introduce two different branching schemes and eight different priority rules for the proposed B&B algorithm. The computational results suggest that the proposed B&B procedure clearly outperforms both a proposed MILP formulation and a branch-and-cut algorithm from the literature.     

The discrete time/resource trade-off problem in project networks: a branch-and-bound approach

In many solution methods for resource-constrained project scheduling, it is assumed that both the duration of each activity and its resource requirements are known and fixed. In real-life projects, however, it often occurs that only one renewable bottleneck resource is available and that the activities have a total work content which indicates how much work (expressed in man-periods) has to be performed. The objective then is to schedule each activity in one of its possible execution modes, subject to the precedence and resource constraints, in order to minimize the project makespan. We present a branch-and-bound procedure and report computational results, obtained using a full factorial experiment on a randomly generated problem set.     

Solving the spatial scheduling problem: a two-stage approach

The spatial scheduling problem that arises in hull block assembly shops occurs when scheduling and spatial allocation of the blocks must be considered simultaneously. We present a two-stage approach to this type of problem. The first stage aims to reduce the number of blocks. The second stage optimises the scheduling and spatial allocation of blocks using nonlinear mixed integer programming (NMIP) methods. The procedure proposed in this paper uses an agglomeration algorithm (AA) for the blocks. This procedure is based on the space–time coupling mechanism. The AA is a three-dimensional classification used to cluster blocks linked closely in time and space into virtual blocks. Extensive computational results from real cases are presented to demonstrate the effectiveness of the proposed approach, demonstrating a significant improvement over results obtained from existing methods.     

Economic lot and supply scheduling problem: a time-varying lot sizes approach

We study the economic lot and supply scheduling problem (ELSSP) that arises in the distribution and manufacturing industries. The ELSSP involves the simultaneous scheduling of end-item production and inbound transportation of input materials over an infinite time horizon to minimise the average costs of inventory, production set-up and transportation. We present a new methodology based on a time-varying lot sizes approach for the ELSSP. We also provide computational experiments showing that the developed algorithm outperforms the existing heuristic for improved integrated scheduling.     

Vendor selection problem: a multi-criteria approach based on strategic decisions

Many factors in the current scenario have influenced manufacturing organisations to have a competitive edge by concentrating on entire supply chains. Sourcing decisions are one of the strategic decisions because they enable companies to reduce costs and improve profit figures. The main task in sourcing is vendor selection. Recent challenges such as shortened product life cycle, just-in-time environment, and the importance of strategic partnerships in upstream chains always influence companies to prioritise vendor selection. In addition, outsourced parts and components account for a significant contribution in the cost of finished goods. Thus evaluating and selecting the right vendor is the key to business. Vendors are selected merely on the basis of cost factors in the traditional approach. However, companies eventually have understood that their approach which emphasises costs as the sole criterion is inefficient and needs to be changed. To deal with the complex process of vendor evaluation, multiple criteria decision-making techniques have evolved. This study presents the integrated approach of multiple multi criteria decision making (MCDM) techniques such as fuzzy logic, strength-weakness-opportunity-threat (SWOT) analysis, and data envelopment analysis. The efficacy of the proposed approach is evident from the case study of an automotive component manufacturer involving 20 vendors, comprising of pre-qualification by fuzzy SWOT and final selection by DEA.     

A practical approach to scheduling a multistage,multiprocessor flow-shop problem

This paper describes a rubber manufacturing system and the numerous technological, operating and quality constraints governing its scheduling process. The complex system resembles a flow-shop problem where all jobs share the same general processing order on a progression of machines. The manufacturing system is defined in terms of production stages and parallel processing lines. One stage can process two or more jobs simultaneously. Jobs are often split on the last stage so that two or more parallel processing lines process the same job simultaneously. The scheduling for such a multistage, multiprocessor flow shop is dominated by the quality constraints. A pragmatic approach is provided in which a schedule is constructed through extensive iterations of analysis and simulation.     

Research on job-shop scheduling problem based on genetic algorithm

With job-shop scheduling (JSS) it is usually difficult to achieve the optimal solution with classical methods due to a high computational complexity (NP-hard). According to the nature of JSS, an improved definition of the JSS problem is presented and a JSS model based on a novel algorithm is established through the analysis of working procedure, working data, precedence constraints, processing performance index, JSS algorithm and so on. A decode select string (DSS) decoding genetic algorithm based on operation coding modes, which includes assembly problems, is proposed. The designed DSS decoding genetic algorithm (GA) can avoid the appearance of infeasible solutions through comparing current genes with DSS in the decoding procedure to obtain working procedure which can be decoded. Finally, the effectiveness and superiority of the proposed method is clarified compared to the classical JSS methods through the simulation experiments and the benchmark problem.     

Auction-based approach for a flexible job-shop scheduling problem with multiple process plans

This study addresses the flexible job-shop scheduling problem with multiple process plans with the objective of minimizing the overall makespan. A nonlinear programming model is formulated to allocate machines and schedule jobs. An auction-based approach is proposed to address the integrated production route selection and resource allocation problem and focus on improving resource utilization and productive efficiency to reduce the makespan. The approach consists of an auction for process plans and an auction for machines. The auctions are evaluated to select a more suitable route for production and allocate resources to a more desirable job. Numerical experiments are conducted by testing new large benchmark instances. A comparison of Lingo and other existing algorithms demonstrates the effectiveness and stability of the proposed auction-based approach. Furthermore, SPSS is used to prove that the proposed method exhibits an absolute advantage, particularly for medium-scale or large-scale instances.     

Solving comprehensive dynamic job shop scheduling problem by using a GRASP-based approach

There are many dynamic events like new order arrivals, machine breakdowns, changes in due dates, order cancellations, arrival of urgent orders etc. that makes static scheduling approaches very difficult. A dynamic scheduling strategy should be adopted under such production circumstances. In the present study an event driven dynamic job shop scheduling mechanism under machine capacity constraints is proposed. The proposed method makes use of the greedy randomised adaptive search procedure (GRASP) by also taking into account orders due dates and sequence-dependent set-up times. Moreover, order acceptance/rejection decision and Order Review Release mechanism are integrated with scheduling decision in order to meet customer due date requirements while attempting to execute capacity adjustments. We employed a goal programming-based logic which is used to evaluate four objectives: mean tardiness, schedule unstability, makespan and mean flow time. Benchmark problems including number of orders, number of machines and different dynamic events are generated. In addition to event-driven rescheduling strategy, a periodic rescheduling strategy is also devised and both strategies are compared for different problems. Experimental studies are performed to evaluate effectiveness of the proposed method. Obtained results have proved that the proposed method is a feasible approach for rescheduling problems under dynamic environments.     

Hybrid intelligent water drops algorithm to unrelated parallel machines scheduling problem: a just-in-time approach

Minimising earliness and tardiness penalties as well as maximum completion time (makespan) simultaneously on unrelated parallel machines is tackled in this research. Jobs are sequence-dependent set-up times and due dates are distinct. Since the machines are unrelated, jobs processing time/cost on different machines may vary, i.e. each job could be processed at different processing times with regard to other machines. A mathematical model which minimises the mentioned objective is proposed which is solved optimally via lingo in small-sized cases. An intelligent water drop (IWD) algorithm, as a new swarm-based nature-inspired optimisation one, is also adopted to solve this multi-criteria problem. The IDW algorithm is inspired from natural rivers. A set of good paths among plenty of possible paths could be found via a natural river in its ways from the starting place (source) to the destination which results in eventually finding a very good path to their destination. A comprehensive computational and statistical analysis is conducted to analyse the algorithms’ performances. Experimental results reveal that the proposed hybrid IWD algorithm is a trustable and proficient one in finding very good solutions, since it is already proved that the IWD algorithm has the property of the convergence in value.     

The economic lot scheduling problem: a survey

This paper aims to present a literature review and an analysis of research works in the field of economic lot scheduling problem (ELSP) based on the related articles published since 1958. Because of ELSP complexity, there are a noticeable number of studies that use algorithms based on different approaches in order to deliver a feasible solution. Therefore, the contribution of this paper is to introduce a taxonomic classification based on scheduling policies and solving methodologies proposed by authors. Also, a simple data analysis is carried out to understand the evolution of ELSP and to identify potential research areas for further studies. The results show that there is an increasing trend in this topic but there are still much needs from industrial manufacturing systems. This study is expected to provide a comprehensive list of references for other researchers, who are interested in ELSP research.     

Two FMS scheduling methods based on Petri nets: A global and a local approach

We are interested in the Flexible Manufacturing System (FMS) scheduling problem. Different methods have been explored to solve this problem and to master its combinatorial complexity, which is NP-hard in the general case. In this paper we will give two different scheduling methods based on Petri nets. The first one tends to solve the general scheduling problem (acyclic schedule) using the Constraint Programming method to avoid exhaustive search. The second method is a dedicated cyclic scheduling method. The aim is not to compare the methods' performances (computation time, results' quality) because they do not solve exactly the same problem, but to compare their application domains in terms of parts number.     

A Bayesian stochastic programming approach to an employee scheduling problem

Bayesian forecasting models provide distributional estimates for random parameters, and relative to classical schemes, have the advantage that they can rapidly capture changes in nonstationary systems using limited historical data. Unlike deterministic optimization, stochastic programs explicitly incorporate distributions for random parameters in the model formulation, and thus have the advantage that the resulting solutions more fully hedge against future contingencies. In this paper, we exploit the strengths of Bayesian prediction and stochastic programming in a rolling-horizon approach that can be applied to solve real-world problems. We illustrate the methodology on an employee production scheduling problem with uncertain up-times of manufacturing equipment and uncertain production rates. Computational results indicate the value of our approach.     

The economic lot scheduling problem: a content analysis

The paper at hand addresses the Economic Lot Scheduling Problem (ELSP), which is concerned with finding a feasible and cost-minimal production schedule for multiple items produced in lots on a single machine. The ELSP started to attract the attention of researchers in the 1950s, where the focus was primarily on the development of simple heuristics for solving the problem. Over the subsequent decades, this topic has frequently been addressed in the literature, with the subject of research being the development of new scheduling policies or solution procedures or extensions of the scope of the original model. To date, a large number of journal articles has been published on the ELSP and its model variants. To identify key research themes, publication patterns and opportunities for future research, the paper at hand applies a content analysis to a sample of 242 papers published on the Economic Lot Scheduling Problem. The results of the content analysis indicate that prior research on this topic had a strong focus on the development of solution methodologies, and that several aspects that are directly connected to lot sizing and scheduling have not attracted much attention in research on the ELSP yet, such as, for example, energy cost and sustainability.     

Dispatching rules in scheduling Dispatching rules in scheduling: a fuzzy approach

Job-shop scheduling through simulation uses various kinds of dispatching rules such as SPT or the slack time rule. Each of these rules aims at satisfying a single criterion although workshop management is a multi-criteria problem. This paper proposes a way to use fuzzy logic in order to build aggregated rules allowing to obtain a compromise between the satisfaction of several criteria. When the criteria of performance change with the evolution of the production environment, these aggregated rules can be parametrized in order to modify the respective influence of the elementary rules they are composed of.     

A fuzzy-based approach to the liquid crystal injection scheduling problem in a TFT-LCD fab

In a thin film transistor-liquid crystal display (TFT-LCD) fab, the liquid crystal injection (LCI) process is to inject liquid crystal into the cell gaps on panels. Since its processing time is enormous (typically 12?h) compared to other processes, the LCI process is a bottleneck in the entire cell process. This study focuses on the LCI scheduling problem, which is divided into two sub-problems: automated guided vehicle (AGV) dispatching and LCI machine scheduling. A self-adjusted fuzzy (SAF) method is developed to solve the AGV dispatching problem. The SAF method is fuzzy based, and it is capable of adjusting the inference rules according to the status of the system to determine which cassette is to be transported first. A modified least slack time (MLST) method is proposed for the LCI machine scheduling problem. The MLST method assigns available LCI machines to first work on processing batches which will be finished beyond their due dates. If there are no such batches, the system releases a new batch, which is waiting in the input buffer with the least slack time, to the available LCI machine. Results indicate that the proposed SAF and MLST methods are able to finish a certain number of batches in a shorter time and reduce the tardiness of cassettes.     

SMT production scheduling: a generalized transportation approach

A generalized transportation model is first formulated for the scheduling of Surface Mount Technology (SMT) production. Its dual form is next discussed. By specially coding the SMT scheduling problem, it is unnecessary to develop the constraint matrix for the dual. The simplex method is not applicable for this problem due to its sparse data structure. An efficient algorithm for the dual model is then developed from the idea of the revised simplex method. To illustrate the algorithm, a numeric example is presented.     

Open shop scheduling problem with a multi-skills resource constraint: a genetic algorithm and an ant colony optimisation approach

The continuous evolution of manufacturing environments leads to a more efficient production process that controls an increasing number of parameters. Production resources usually represent an important constraint in a manufacturing activity, specially talking about the management of human resources and their skills. In order to study the impact of this subject, this paper considers an open shop scheduling problem based on a mechanical production workshop to minimise the total flow time including a multi-skill resource constraint. Then, we count with a number of workers that have a versatility to carry out different tasks, and according to their assignment a schedule is generated. In that way, we have formulated the problem as a linear as and a non-linear mathematical model which applies the classic scheduling constraints, adding some different resources constraints related to personnel staff competences and their availability to execute one task. In addition, we introduce a genetic algorithm and an ant colony optimisation (ACO) method to solve large size problems. Finally, the best method (ACO) has been used to solve a real industrial case that is presented at the end.