China
Africa
Explore chapters and articles related to this topic
Computational Complexity
Published in Craig A. Tovey, Linear Optimization and Duality, 2020
Several important problems are P-space complete. They include: stochastic scheduling, periodic scheduling, Markov decision problems, control of queueing networks, and solving systems of differential equations. Several motion planning problems involving jointed robot arms are P-space complete as well.
A branch-and-bound approach to minimise the value-at-risk of the makespan in a stochastic two-machine flow shop
Published in International Journal of Production Research, 2023
Stochastic and robust scheduling approaches have been developed to support planning and scheduling decisions, aiming at modelling uncertainties, mitigating the impact of uncertain events, and protecting the performance of a production schedule (Urgo and Váncza 2019). In stochastic scheduling approaches, relevant sources of uncertainty are modelled by defining random variables and the associated probability distributions. Different measures, such as expected makespan, maximum regret, value-at-risk and conditional value-at-risk, are exploited to indicate the robustness of the schedule. Among these, value-at-risk and conditional value-at-risk are designed to optimise the overall performance while avoiding the impact of extreme events that may lead to very poor performance of the objective function (Radke et al. 2013). Using these risk measures to support the devising of a robust scheduling solution is one of the most promising topics (Tolio, Urgo, and Váncza 2011; Alfieri, Tolio, and Urgo 2012; Urgo and Váncza 2019; Filippi, Guastaroba, and Grazia Speranza 2020).
Bad-scenario-set robust scheduling for a job shop to hedge against processing time uncertainty
Published in International Journal of Production Research, 2019
Bing Wang, Xiaozhi Wang, Hanxin Xie
Traditionally, uncertain scheduling approaches include stochastic scheduling, fuzzy scheduling and robust scheduling, which are classified by the adopted tools of modelling uncertain factors. Stochastic scheduling is the most popular approach in uncertain environments, which generally assumes known probability distributions for uncertain factors and aims at optimising the expected performance. However, knowledge about exact probabilistic distributions of uncertain parameters is usually hard to obtain especially when the decision environments have multiple interdependent uncertain factors. Another important criticism for stochastic scheduling is that independent distributional assumptions often used are inappropriate for machine scheduling environments, where a few factors determine the uncertainty of many elements in the processing times of jobs, thus inducing strong, but hard-to-specify, correlations among the associated probability distributions (Kouvelis and Yu 1997). In such situations, robust scheduling could be an alternative approach to stochastic programming when handling uncertainty (Murvey, Vanderbei, and Zenios 1995).
Modelling and an improved NSGA-II algorithm for sustainable manufacturing systems with energy conservation under environmental uncertainties: a case study
Published in International Journal of Sustainable Engineering, 2021
Behnam Ayyoubzadeh, Sadoullah Ebrahimnejad, Mahdi Bashiri, Vahid Baradaran, Seyed Mohammad Hassan Hosseini
Stochastic scheduling is used to schedule jobs under the uncertainties that occur during production and follow a pre-known probability distribution. A flexible job shop scheduling problem was conducted under uncertainty and dynamic jobs arriving as well as sequences-dependent setup time of machines and some dispatch rules were introduced that are typically incorporated into two new methods in a simulated model (Kianfar, Fatemi Ghomi, and Oroojlooy Jadid 2012). Then, researchers solved the problem of dynamic flow shop scheduling when new jobs have arrived and machines are not available (Dai 2015).