Stochastic Scheduling for a Network of Flexible Job Shops

Subhash C. Sarin (), Hanif D. Sherali, Amrusha Varadarajan and Lingrui Liao
Additional contact information
Subhash C. Sarin: Virginia Tech
Hanif D. Sherali: Virginia Tech
Amrusha Varadarajan: Virginia Tech
Lingrui Liao: Virginia Tech

Chapter Chapter 3 in Heuristics, Metaheuristics and Approximate Methods in Planning and Scheduling, 2016, pp 45-75 from Springer

Abstract: Abstract In this chapter, we address the problem of optimally routing and sequencing a set of jobs over a network of flexible machines for the objective of minimizing the sum of completion times and the cost incurred, assuming stochastic job processing times. This problem is of particular interest for the production control in high investment, low volume manufacturing environments, such as pilot-fabrication of microelectromechanical systems (MEMS) devices. We model this problem as a two-stage stochastic program with recourse, where the first-stage decision variables are binary and the second-stage variables are continuous. This basic formulation lacks relatively complete recourse due to infeasibilities that are caused by the presence of re-entrant flows in the processing routes, and also because of potential deadlocks that result from the first-stage routing and sequencing decisions. We use the expected processing times of operations to enhance the formulation of the first-stage problem, resulting in good linear programming bounds and inducing feasibility for the second-stage problem. In addition, we develop valid inequalities for the first-stage problem to further tighten its formulation. Experimental results are presented to demonstrate the effectiveness of using these strategies within a decomposition algorithm (the L-shaped method) to solve the underlying stochastic program. In addition, we present heuristic methods to handle large-sized instances of this problem and provide related computational results.

Keywords: Stochastic scheduling; Flexible job shop; Multi-site scheduling; L-shaped method; Branch-and-bound (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-319-26024-2_3

Ordering information: This item can be ordered from
http://www.springer.com/9783319260242

DOI: 10.1007/978-3-319-26024-2_3

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().