MILP Formulation and Genetic Algorithm for Non-permutation Flow Shop Scheduling Problem with Availability Constraints

Ramezanian, R.
October 2014
International Journal of Applied Operational Research;Autumn2014, Vol. 4 Issue 4, p11
In this paper, we consider a flow shop scheduling problem with availability constraints (FSSPAC) for the objective of minimizing the makespan. In such a problem, machines are not continuously available for processing jobs due to preventive maintenance activities. We proposed a mixed-integer linear programming (MILP) model for this problem which can generate nonpermutation schedules. Furthermore, an improving heuristic method and a genetic algorithm (GA) based heuristic are developed to evolve optimal or near optimal solutions. To obtain better and more robust solutions, The Taguchi method is performed for tuning the parameters of genetic algorithm. The MILP model can be used to compute optimal solutions for small-sized problems or to test the performance of solution algorithms. The presented methodology is evaluated for the solution quality. According to computational experiments, the GA can reach good-quality solutions in reasonable computational time, and can be used to solve large scale problems effectively.


Related Articles

  • Two-stage flow-shop scheduling problem with non-identical second stage assembly machines. Navaei, J.; Ghomi, S. M. T. Fatemi; Jolai, F.; Shiraqai, M. E.; Hidaji, H. // International Journal of Advanced Manufacturing Technology;Dec2013, Vol. 69 Issue 9-12, p2215 

    This paper addresses the two-stage assembly flow-shop problem (TSAFP) with multiple non-identical assembly machines in second stage with the objective function of makespan minimization. This problem is a generalization of previously proposed problems in TSAFP. Mathematical mixed-integer linear...

  • Comparing mathematical and heuristic rules for solving single machine scheduling problem with release and due date constraints. Yong Zhan; Haitao Zhu; Yuguang Zhong // Applied Mechanics & Materials;2014, Issue 630-642, p1707 

    The purpose of this paper is to compare a mixed integer programming(MIP) model, and heuristic rules based on their practical efficiency and the accuracy of results to tackle the minimum lateness single machine scheduling problem with release and due date constraints. Extensive numerical...

  • An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem. Coco, Amadeu; Júnior, João; Noronha, Thiago; Santos, Andréa // Journal of Global Optimization;Oct2014, Vol. 60 Issue 2, p265 

    The well-known Shortest Path problem (SP) consists in finding a shortest path from a source to a destination such that the total cost is minimized. The SP models practical and theoretical problems. However, several shortest path applications rely on uncertain data. The Robust Shortest Path...

  • Reentrant Flow Shop Scheduling considering Multiresource Qualification Matching. Chu, Feng; Liu, Ming; Liu, Xin; Chu, Chengbin; Jiang, Juan // Scientific Programming;7/9/2018, p1 

    With the development of technology and industry, new research issues keep emerging in the field of shop scheduling. Most of the existing research assumes that one job visits each machine only once or ignores the multiple resources in production activities, especially the operators with skill...

  • A matheuristic approach for the two-machine total completion time flow shop problem. Della Croce, Federico; Grosso, Andrea; Salassa, Fabio // Annals of Operations Research;Feb2014, Vol. 213 Issue 1, p67 

    This paper deals with the two-machine total completion time flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solutions provided by state of the art procedures. The proposed procedure is based on the...

  • Genetic Algorithm Based Generator Scheduling-A Review. Ali Bukhari, Syed Basit; Ahmad, Aftab; Raza, Syed Auon; Ul Munim Zaki, Atta // World Applied Sciences Journal;2014, Vol. 30 Issue 12, p1826 

    Generator Scheduling (GS) problemis a non-linear, mixed integer, combinatorial and constrained optimization problem. The main objective of generator scheduling is to prepare the most economic startup and shutdown schedule for generators to meet the forecasted load demand and spinning reserve for...

  • A novel genetic algorithm for the hybrid flow shop scheduling with parallel batching and eligibility constraints. Costa, Antonio; Cappadonna, Fulvio; Fichera, Sergio // International Journal of Advanced Manufacturing Technology;Nov2014, Vol. 75 Issue 5-8, p833 

    The hybrid flow shop with parallel batching (HFSPB) is a kind of flow shop production system wherein some stages may be populated by parallel processors that simultaneously process groups of jobs. This paper addresses the makespan minimization problem for a HFSPB system whose machines are...

  • A TRADE-OFF BETWEEN TIME AND COST IN SCHEDULING REPETITIVE CONSTRUCTION PROJECTS. LIHUI ZHANG; XIN ZOU; JIANXUN QI // Journal of Industrial & Management Optimization;Oct2015, Vol. 11 Issue 4, p1423 

    The discrete time/cost trade-off problem (DTCTP) is commonly encountered in repetitive project scheduling. The current models for this problem assume that logical sequences of activities cannot be changed in different units. However, logical sequences are often changed to shorten the project...

  • MILP-aided bit-based division property for primitives with non-bit-permutation linear layers. Ling Sun; Wei Wang; Wang, Meiqin Q. // IET Information Security;2020, Vol. 14 Issue 1, p12 

    In this study, the authors settle the feasibility of mixed integer linear programming (MILP)-aided bit-based division property for ciphers with non-bit-permutation linear layers. First, they transform the complicated linear layers to their primitive representations. Then, the original Copy and...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics