Bi-objective Scheduling of no wait flexible flow lines with a time window and the possibility of work rejecting

Document Type : Research Paper


1 MSc./ُShahid Beheshti University

2 Associate Prof. Faculty of Management and ccounting /Shahid Beheshti University

3 ُShahid Beheshti University /ph.D student


One of the main challenges for manufacturers in production systems on order is balancing between orders, inputs and limited resources. Hence, they have to choose some orders and reject the others. In addition, work schedule must be considered in order acceptance. In this research the integrated problem of scheduling and order acceptance in a no wait flexible flow line production system is discussed. In this study orders that can’t be delivered in due date are rejected . Most researches are single objective optimization but in real world different objectives should be considered in the decision making. Therefor a bi-objective model which maximizes profit and minimize delivery deviation, is presented. Due to the high complexity of the model, the exact methods are not able to produce the optimal solution , so the two meta- heuristic algorithms MOSA and NSGA II for this problem were developed and their performance were compared through quantitative indicators in three different categories.


Bartal, Y., Leonardi, S., Marhetti-Spaccamela, A., Sgall, J. & Stougie, L. )2000(. Multi- processor scheduling with rejection. SIAM Journal on Discrete Mathematics, 13(1):64–78.
Cesaret Bahriye, C., Oguz Ceyda, O. & Sibel Salman, F. (2012). A Tabu Search Algorithm for Order Acceptance and Scheduling. Computers & Operations Research, 39(6):1197–1205.
Charnsirisaksul, K., Griffin, P. & Keskinocak, P. (2004). Order selection and scheduling with leadtime flexibility. IIE Transactions, 36:697–707.
Coello Coello, C.A. Van Veldhuizen, D.A. and Lamont, G.B. (2007). Evaluationary Algorithm for solving Multi-objective problems, Kluwer Academic Publishers,New York, second edition,May,ISBN,0- 7062-6364-7,4004.
De, P., Ghosh, J.B. & Wells, C.E. (1993). Job selection and sequencing on a single machine in a random environment. European Journal of Operational Research, 70:425–431.
Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T., (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Evolutionary Computation, 6(2): 182-197.
Gupta, S.K., Kyparisis, J. & Ip, C.M. (1992). Note—Project selection and sequencing to maximize net present value of the total return. Management Science, 38:751–752.
Herbots, J,; Herroelen, W. S,; Leus, R and Demeulemeester, E. L. (2007). Dynamic Algorithms for Order Acceptance and Capacity Planning within a Multi-Project Environment. In proceedings of the 3rd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2007), 28 -31 August 2007, Paris, France, 572-574.
Ivanescu, V.C. (2004). Order acceptance under uncertainty in batch process industries. PhD thesis, Virginia Cristina, Technische Universiteit Eindhoven.
Ivanescu, V.C., Fransoo, J.C. & Bertrand, J.W.M. (2002). Makespan estimation and order acceptance in batch process industries when processing times are uncertain. OR Spectrum, 24:467–495.
Jolai Fariborz, F.,, Sheikh, ShayaSh., Rabbani, Massoud M. & Karimi, Behrooz. (2009). A genetic algorithm for solving no-wait flexible flow lines with due window and job rejection.International Journal of Advanced Manufacturing Technology 42:523–532.
Lewis, H.F. & Slotnick, S.A. (2002). Multi-period job selection: planning work loads to maximize profit. Computers & Operations Research, 29:1081–1098.
Nobibon, F. T, Herbots, J and & Leus, R. (2009). Order acceptance and scheduling in a single-machine environment: exact and heuristic algorithms. Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), 10-12 Aug 2009, Dublin, Ireland, 772-774, 2009.
Oguz Ceyda, O., Sibel Salman, F. & Zehra Bilgintürk Yalçın, Z.. (2010). Order acceptance and scheduling decisions in make-to-order systems, International Journal of Production Economics, 125(1):200-211.
Pourbabai, B. (1989). A short term production planning and scheduling model. Engineering Costs and Production Economics, 18:159–167.
Quadt, D. & Kuhn, H. K. (2007). Batch scheduling of jobs with identical process times on flexible flow lines. International Journal of Production Economics, 105(2):385–401.
Rom, W. & Slotnick, S.A. (2009). Order acceptance using genetic algorithms.Computers and Operations Research, 36:1758–1767.
Roundry, R., Chen, D., Chen, P. & Cakanyildirim, M. (2005). Capacity-driven acceptance of customer orders for a multi-stage batch manufacturing system: Models and algorithms. IIE Transactions, 37:1093–1106.
Sawik, T. (1993). A scheduling algorithm for flexible flow lines with limited intermediate buffers. Applied Stochastic Models and Data Analysis, 9:127–138.
Schott, J. (1995). Fault tolerant design using single and multicriteria genetic algorithm optimization.Master’s thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology.
Simonis, B.J. (2006). Order Acceptance in Multipurpose Batch Process Industries Using the Regression Policy, Master’s thesis. Technische Universiteit Eindhoven Department of Mathematics and Computer Science.
Slotnick, S.A. & Morton, T.E. (1996). Selecting jobs for a heavily loaded shop with lateness penalties, Computers & Operations Research, 23:131–140.
Slotnick, S.A. & Morton, T.E. (2007). Order acceptance with weighted tardiness, Computers & Operations Research, 34:3029–3042.
Stadje, W. (1995). Selecting jobs for scheduling on a machine subject to failure. Discrete Applied Mathematics, 63:257–265.
Suman, B. & Kumar, P. (2006). A survey of simulated annealing as a tool for single and multiobjective optimization, Journal of the Operational Research Society, 57:1143–1160.
Zhang, L., Lu, L. & Yuan, J. (2009). Single machine scheduling with release dates and rejection. European Journal of Operational Research, 198:975–978.
Zitzler, E. (1999). Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications.PhD thesis, Swiss Federal Institute of Technology (ETH) Zurich, Switzerland, TIK-Schriftenreihe Nr. 30, Diss ETH No. 13398,Shaker Verlag, Aachen, Germany.
Zitzler, E., Deb, K.,Thiele, L. ( 2000). Comparison of multiobjective evolutionary algorithms: Emprical results, Evolutionary Computation journal 8(2): 125-148.