An Excel Based Template for the Machinist's Sequencing Problem

(ProQuest: ... denotes formulae omitted.)IntroductionThe machinist's sequencing dilemma (MSD) is defined as a sequencing problem where the central question is to find the proper sequence of a series of jobs, each with a probability of failure and with an independent value added to a product be sequenced in order to minimize the overall loss of accumulated cost. The accumulated cost at risk involved in this scenario is sequence dependent as well as not intuitively obvious. This problem is shown to be NP hard (White and Asllani, 2008) and as such the goal is to find solution alternatives which are both optimal and practical. Improper sequencing in the MSD can lead to substantial losses; that is, optimal solutions may result in significant savings over suboptimal approaches.The purpose of this paper is to introduce an Excel based solution template for the machinist's dilemma sequencing problem. The template uses Excel's Solver and is based on the mathematical (nonlinear) programming formulation of MSD and provides optimal solutions to the problem. In addition, the template can be easily modified and is appropriate for large problems.The paper is structured as follows: In the next section, we describe the MSD problem and explore the body of previous research. Then, we offer a theoretical model formulation based on a mathematical mixed non-linear programming. Later, we describe the Excel-based template and its advantages and disadvantages.MSD and Literature ReviewIn the MSD problem, n jobs must be performed on a given product. Associated with each job j is a value pj (j= 1, 2... n) and a probability of failure fj with 0The MSD is a-priori scheduling problems. The machinist cannot re-optimize and will usually use a pre-designed sequencing heuristic hoping that the expected loss of accumulated value will be minimized. This approach is similar to the stochastic case of traveling salesman problem when probabilistic elements change (Jaillet 1988; Bianchi 2002). The subject of scheduling and sequencing has been one of the most studied areas among scholars and practitioners. A number of survey papers (Graham et al., 1979; Lawler et al.,1982; Lawler, 1983; Lenstra and Rinnooy Kan, 1985; Lawler et al, 1993) have been written on this subject as well as the books by Pinedo(1995) and Conway et al. (2003). One of the major results of the scheduling research is the successful addressing of many interesting and important problems through use of optimization and heuristic solution approaches (Bellalouna and Jaillet, 2007). Stochastic scheduling is among these interesting and challenging problems and has always been the focus of the research. However, stochastic cases of scheduling have been mainly limited to random processing times (Soroush, 1996; Xia et al., 2008) random release time (Hsieh et al. 2006), and random due dates (Cai and Zhou, 2005). A comprehensive discussion of stochastic scheduling problems is provided in Chapter 8 of Pinedo (1995).Assuming that the added value from each job is proportional to the job's processing time, White and Asllani (2008) reformulated the MSD as a sequence-dependent scheduling model, where the objective function is to minimize the expected added-value under the constraint of each job having a probability of failure. …