Modeling and solving the distributed and flexible job shop scheduling problem with WIPs supply planning and bounded processing times

Document Type: Research Paper

Author

University of Bojnord, Bojnord, Iran

Abstract

In this paper, for the first time in the literature, we integrated production scheduling decisions and WIPs planning decisions in a distributed environment. We study the distributed and flexible job shop scheduling problem (DFJSP) which involves the scheduling of jobs (products) in a distributed manufacturing environment, under the assumption that the shop floor of each factory/cell is configured as a flexible job shop. It is also assumed that the work-in-process (WIP) parts can be bought from the market instead of manufacturing them in-house, and they also can be sold in the market instead of processing their remaining operations and selling the end products. Moreover, the processing times of the operations can be decreased by paying a cost. However, there are a lower limit and an upper limit for the processing time of each operation. We formulate this general problem as a mixed integer linear programming (MILP) model. A fast heuristic algorithm is also developed to obtain good solutions in very short time. The algorithm is tested on some problem instances in order to evaluate its performance. Computational results show that the proposed heuristic is a computationally efficient and practical approach.

Keywords

Main Subjects


Baker K. (1974). Introduction to sequencing and scheduling. NewYork: Wiley.

Chan F.T.S., Chung S.H. and Chan P.L.Y. (2005). An adaptive genetic algorithm with dominated genes for distributed
scheduling problems. Expert Systems with Applications, Vol.29, pp. 364–371.

Chan F.T.S., Chung S.H. and Chan P.L.Y. (2006a). Application of genetic algorithms with dominated genes in a
distributed scheduling problem in flexible manufacturing. International Journal of Production Research, Vol. 44 (3),
pp. 523–543.

Chan F.T.S., Chung S.H., Chan L.Y., Finke G. and Tiwari M.K. (2006b). Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach. Robotics and Computer-Integrated Manufacturing, Vol. 22, pp. 493–504.

Demir Y. and Isleyen K. (2013). Evaluation of mathematical models for flexible job-shop scheduling problems. Applied Mathematical Modeling, Vol. 37, pp. 977–988.

Fattahi P., Mehrabad M.S. and Jolai F. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing, Vol. 18, pp. 331–342.

Gao J., Chen R. and Deng W. (2013). An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem. International Journal of Production Research, Vol. 51 (3), pp. 641-651.

Garey M.R., Johnson D.S. and Sethi R. (1976). The complexity of flow shop and job-shop scheduling. Mathematics of Operations Research, Vol. 1 (2), pp. 117–129.

Giovanni L. D. and Pezzella F. (2010). An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. European Journal of Operational Research, Vol. 200, pp. 395–408.

Jia H.Z., Fuh J.Y.H., Nee A.Y.C. and Zheng Y.F. (2002). Web-based multi-functional scheduling system for a distributed manufacturing environment. Concurrent Engineering-Research and Applications, Vol.10(1), pp. 27–39.

Jia H.Z., Fuh J.Y.H., Nee A.Y.C. and Zhang Y.F. (2003). A modified genetic algorithm for distributed scheduling problems. Journal of Intelligent Manufacturing, Vol. 15, pp. 351–362.

LINDO Systems Inc. (1999). LINGO User’s Guide. LINDO Systems Inc.: Chicago.

Özgüven C., Ozbakır L. and Yavuz Y. (2010). Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling, Vol. 34, pp. 1539–1548.

Pan C.H. (1997). A study of integer programming formulations for scheduling problems. International Journal of Systems Science, Vol. 28 (1), pp. 33–41.

Pinedo M. (2002). Scheduling: theory, algorithms and systems. Englewood cliffs, NJ: Prentice-Hall.

Rosenau M.D. (1996). The PDMA Handbook of New Product Development. Wiley, New York.

Unlu Y. and Mason S.J. (2010). Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems. Computers and Industrical Engineering, Vol. 58, pp. 785–800.

Wang B. (1997). Integrated product, process and enterprise design. Chapman & Hall, London.

Wang L. and Shen W. (2007). Process Planning and Scheduling for Distributed Manufacturing. Springer, London.

Wang S.-Y., Wang L., Liu M. and Xu Y. (2013). An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem. International Journal of Production Economics, Vol. 145 (1). pp. 387–396.

Zhang Q., Manier H. and Manier M.-A. (2012). A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times. Computers & Operations Research, Vol. 39, pp. 1713–1723.

Ziaee M. (2014). A heuristic algorithm for the distributed and flexible job-shop scheduling problem. Journal of Supercomputing, Vol. 67, pp. 69–83.