Query: schedule problem  sustenaible

Candidate papers:

abstract: Hoist scheduling in automated electroplating lines has been extensively studied in a static environment. However, practical electroplating lines are subject to diversified unforeseen disruptions that require frequent rescheduling to maintain or optimize system performance. This paper addresses a hoist scheduling problem, where randomly arriving jobs need to be inserted into an existing schedule without changing the sequence of hoist moves already scheduled. The objective is to minimize the total completion time of all the jobs in the existing schedule and a newly inserted job. We develop a polynomial time heuristic that adjusts the starting times of the existing hoist moves to a limited extent but does not bring about a severe disturbance of the existing hoist moves. We compare our algorithm with two existing approaches with different rescheduling policies (i.e. partial and zero adjustment of the existing schedule) We empirically analyze the productivity and the stability of the schedules generated by the three approaches. Computational results demonstrate that our algorithm can generate more productive and stable schedules than the two existing approaches. Note to Practitioners Electroplating and chemical surface treatment lines with automated material handling hoists are commonplace in electronics, semiconductor, and many other manufacturing industries. In an uncertain environment, hoist rescheduling plays an important role in improving the productivity and reducing the impact of disruptions. This paper presents a hoist scheduling algorithm to deal with dynamic job arrivals by considering the impact of the disturbance incurred by rescheduling. Our algorithm can generate a better schedule with smaller total completion time and slighter disturbance than the existing algorithms. The proposed algorithm runs in polynomial time and can be used to control hoist operations in practical electroplating lines. A comparative analysis provides useful insights on the implementation of rescheduling approaches and policies to industry practitioners.
author_names: Pengyu Yan

Ada Che

Eugene Levner

Shi Qiang Liu
title: A Heuristic for Inserting Randomly Arriving Jobs Into an Existing Hoist Schedule
venue: IEEE Transactions on Automation Science and Engineering
year: 2018

abstract: The cyclic hoist scheduling problem (CHSP) is a well studied optimisation problem due to its importance in industry. Despite the wide range of solving techniques applied to the CHSP and its variants, the models have remained complicated and inflexible, or have failed to scale up with larger problem instances. This article re examines modelling of the CHSP and proposes a new simple, flexible constraint programming formulation. We compare current state of the art solving technologies on this formulation, and show that modelling in a high level constraint language, MiniZinc, leads to both a simple, generic model and to computational results that outperform the state of the art. We further demonstrate that combining integer programming and lazy clause generation, using the multiple cores of modern processors, has potential to improve over either solving approach alone.
author_names: Mark Wallace

N Yorke-Smith
title: A new constraint programming model and solving for the cyclic hoist scheduling problem
venue: Constraints An Int. J.
year: 2020

abstract: The Hoist Scheduling Problem is combinatory, so tools such as mathematical programming need to be used to get the sequence of movements, respecting the constraints of the process by minimizing the cycle time. A sequence in which the order of movements follows the order of the process is known as the basic diagram. These schedules do not have any clearance for the hoist to make any other movements, resulting in a loss in productivity. This chapter takes the production line of a Mexican factory as a case study, analyzing the hoist's travelling speed to find sequences of movements that could improve productivity. The results of the study indicate that the cycle time has a nonlinear behavior in respect of the hoist's travelling speed and it was determined that there are travelling speeds for which sequences are obtained with enough clearance to make other movements and keep other carriers on the line. A suitable speed was estimated in the case. An Analysis of the Traveling Speed in the Traveling Hoist Scheduling Problem for Electroplating Processes
author_names: Jose Itzcoatl Gomar-Madriz

Salvador Hernandez-Gonzalez

J Navarrete-Damian
title: An Analysis of the Traveling Speed in the Traveling Hoist Scheduling Problem for Electroplating Processes
year: 2020

abstract: In this paper, we propose a Mixed Integer Linear Programming model for solving a hoist scheduling problem with several transportation resources. This model complements initial work that neglected the risk of collisions between hoists. This new model identifies and manages the various possible collision situations, and it is intended to be integrated as a solution evaluation module in a hybrid algorithm addressing the broader and more complex joint problem of sizing transport resources and scheduling surface treatment workshops. In this global approach, an evolutionary algorithm first generates partially feasible solutions, whose total feasibility is then verified a posteriori, thanks to the proposed new model. This model is validated through tests performed on instances of the literature.
author_names: Emna Laajili

Sid Lamrous

Marie-Ange Manier

Jean Marc Nicod
title: Collision Free Based Model for the Cyclic Multi Hoist Scheduling Problem
venue: 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC)
year: 2019

abstract: Electroplating facilities often face the Cyclic Hoist Scheduling Problem when a repetitive sequence of moves is searched for the hoists. This paper addresses this optimization problem extended to the design of the workshop, where we aim to minimize both the cycle time and the number of hoists used. For this goal, we propose a genetic meta heuristic approach which introduces a novel solution encoding to enlarge the solutions' search space. Our encoding procedure is based on hoists' empty moves, and includes separator characters. With the latter, we obtain solutions that were not reachable by previous approaches. Each solution obtained thanks to the genetic operators is evaluated by using a Mixed Integer Linear Program. This one checks the constraints of the problem (such as capacity constraints and soaking time bounds) and computes the smallest cycle time for a given moving sequence and its associated number of hoists. Some results are presented using benchmark instances for which our approach allows to improve the best known solutions.
author_names: Laajili Emna

Lamrous Sid

Manier Marie-Ange

Nicod Jean-Marc
title: Genetic Algorithm Based Approach for the Multi Hoist Design and Scheduling Problem
venue: 2019 International Conference on Industrial Engineering and Systems Management (IESM)
year: 2019

abstract: The current paper deals with the cyclic multi hoist scheduling problem in electroplating lines considering rentrance. Identical parts are produced with processing time windows. Moreover, re entrance is also considered. These together make it more challenged to obtain better schedules improving the productivity. To achieve this, multi degree cycles are considered. To our best knowledge, this is the first research in this generally complicated scenario. In order to maximize the productivity of the production line, i.e. minimize the cycle time for a given degree, operations of hoists are first analyzed in detail to avoid their collision. Then, operations related the re entrance are modeled. Based on these work, a mixed integer linear programming model is proposed. An industrial instances is used to test the proposed model. It is solved using the commercial software ILOG CPLEX. Results illustrate the efficiency of the proposed approach.
author_names: Xin Li

Yanchun Pan

Richard Y K Fung
title: Optimal Scheduling of the Reentrant Multi Degree Cyclic Multi Hoist Scheduing Problem
venue: 2019 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM)
year: 2019

abstract: This paper deals with the robust optimization for the cyclic hoist scheduling problem with processing time window constraints. The robustness of a cyclic hoist schedule is defined as its ability to remain stable in the presence of perturbations or variations of certain degree in the hoist transportation times. With such a definition, we propose a method to measure the robustness of a cyclic hoist schedule. A bi objective mixed integer linear programming (MILP) model, which aims to optimize cycle time and robustness, is developed for the robust cyclic hoist scheduling problem. We prove that the optimal cycle time is a strictly increasing function of the robustness and the problem has infinite Pareto optimal solutions. Furthermore, we derive the so called ideal point and nadir point that define the lower and upper bounds for the objective values of Pareto front. A Pareto optimal solution can be obtained by solving a single objective MILP model to minimize the cycle time for a given value of robustness or maximize the robustness for a specific cycle time. The single objective MILP models are solved using commercial optimization software CPLEX. Computational results on several benchmark instances and randomly generated instances indicate that the proposed approach can solve large scale problems within a reasonable amount of time.
author_names: Ada Che

Jianguang Feng

Haoxun Chen

Chengbin Chu
title: Robust optimization for the cyclic hoist scheduling problem
venue: Eur. J. Oper. Res.
year: 2015

abstract: When various kinds of products must receive the same treatments in a production line of tanks and the size of batches is high, a cyclic manufacturing composed of a job from each batch can be scheduled. A hoist ensures the auto mated transfer of the jobs between tanks. The probl em consists in the scheduling of repetitive hoist movements, which is known as CHSP (Cyclic Hoist Scheduling Problem) The objective is to find a sequence which minimizes the cycle time for jobs from different products. We consider the problem where types of products must be treated and we search an n cyclic schedule. The algorithm is based on the resolution of different sequences of products. For each one, a branch and bound is solved which considers only coherent subsequences. It enables to reduce the com putational times most of the time for instances with 5 tanks and 4 product types
author_names: Manuel Mateo Doll

Marie-Ange Manier

Ramon Pascual
title: A procedure based on branch and bound for the Cyclic Hoist Scheduling Problem
year: 2015

abstract: The cyclic hoist scheduling problem is encountered in electroplating facilities, when mass production is required. This class of problems is a branch stemming from the Hoist Scheduling Problem (HSP) where automatic hoist is used for moving electroplates through chemical baths. A repetitive sequence of moves is searched for the hoist in cyclic schedule. To minimize the cycle time of r different part jobs, we propose a linear optimization approach. An illustrative example is given in order to show some feedback of our exact solving method. Afterward, two comparisons are presented: firstly, between a two 1 cycle homogenous schedule and a 2 cycle heterogeneous part job and secondly, between 2 cycle and 4 cycle heterogeneous part job. These comparisons show how, by considering r cyclic scheduling, we can optimize the cycle length considerably and then the throughput rate of the electroplating line.
author_names: Adnen El Amraoui

Marie-Ange Manier

Abdellah El Moudni

Mohamed Benrejeb
title: A linear optimization approach to the heterogeneous r cyclic hoist scheduling problem
venue: Comput. Ind. Eng.
year: 2013

abstract: The performance of an enterprise largely depends on the schedule of its resources. A good schedule may increase the output rate and reduce the production costs. Therefore, in this paper, we consider the cyclic schedule of hoist activities in automated electroplating lines which is commonly known as cyclic hoist scheduling problem (CHSP) The CHSPs appear in the manufacturing facilities to achieve a mass production and to search a repetitive sequence of moves for the hoist. In such kind of lines, hoist is used for moving electroplates through a line of tanks containing chemical baths. In this paper, we first study the impact of non fixed processing time in cycle duration and then we extend our elaborated two degree cyclic model to a more complex configuration of the production lines. [Received 26 June 2010; Revised 14 November 2010; Accepted 15 February 2011]
author_names: Adnen El Amraoui

Marie-Ange Manier

Abdellah El Moudni

Mohamed Benrejeb
title: Resolution of the two part cyclic hoist scheduling problem with bounded processing times in complex lines' configuration
year: 2012