Maximization of solution flexibility for robust shop scheduling |
| |
| Institution: | 1. Faculty of Chemistry and Chemical Engineering, University of Maribor, Smetanova ul. 17, Maribor, Slovenia;2. Department of Chemical Engineering, University of Salamanca, Salamanca, Spain;3. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, USA;1. Department of Chemical Engineering, Imperial College London, London, United Kingdom.;2. Artie McFerrin Department of Chemical Engineering, Texas A&M University, College Station TX, United States.;1. Faculty of Economics and Business Administration, Ghent University, Tweekerkenstraat 2, Gent 9000, Belgium;2. Technology and Operations Management, Vlerick Business School, Reep 1, Gent 9000, Belgium;3. UCL School of Management, University College London, 1 Canada Square, London E14 5AA, United Kingdom;1. Donlinks School of Economics and Management, University of Science and Technology Beijing, No 30 Xueyuan Road, Haidian District 100083 Beijing, China;2. Law and Social Sciences School, University of Castilla-La Mancha, Ronda de Toledo s/n, 13071 Ciudad Real, Spain |
| |
| Abstract: | We consider the problem of introducing flexibility in the schedule determination phase, for shop scheduling problems with release dates and deadlines. The flexibility is provided by generating a family of schedules, instead of a unique one. We represent a family of schedules by an ordered group assignment defining for each machine a sequence of groups where the operations within a group are totally permutable. We propose a polynomial time algorithm to evaluate the worst case completion time of operations in an ordered group assignment. We then consider the single machine problem with heads and deadlines associated to operations, as a sub-problem of the job shop problem. We propose polynomial time dynamic programming algorithms for minimizing the number of groups and for maximizing the number of characterized sequences, under specific constraints. Finally, computational experiences on job shop benchmarks, show the impact of grouping operations on the solution makespan value. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
