For Libraries For Publication Open Access Downloads About Us Contact Us
Paper Titles
Study on the Workshop Production Environment Remote Monitoring System
p.469
Reverse Engineering of Cam Design Based on BP NN
p.476
Approach of Composing Disassembly Model Based on the CAD Information for End of Life Product
p.484
Key Techniques in Intelligent Predictive Maintenance (IPdM) – A Framework of Intelligent Faults Diagnosis and Prognosis System (IFDaPS)
p.490
Partial Rescheduling Based on Branch and Bound for Single-Machine Problem
p.506
Two-Level Robust Optimization for Uncertain Job Shop Scheduling Problem
p.514
Research and Implementation of Real-Time Scheduling Management of WIP in the Workshop Based on RFID
p.522
A 3D Vision-Based Quality Inspection Study for Molded Part with Multiple Geometry Shapes
p.529
Quality Inspection with Chi-Square Automatic Interaction Detector and Self-Organizing Map
p.538

Partial Rescheduling Based on Branch and Bound for Single-Machine Problem

Article Preview

Abstract:

This paper addresses a single-machine large-scale rescheduling problems with efficiency and stability subject to machine breakdown. Partial rescheduling (PR) strategy is used to cope with the computational complexity. Two kinds of objective functions of PR sub-problem, where the global dual objectives are reflected to an extent, are designed respectively for the procedural PR horizon and the terminal PR horizon. The PR problem is solved by a branch and bound algorithm. Lower bound and upper bound procedures as well as dominance rules are developed for the branch and bound algorithm. An extensive experimentation was conducted. The computational results show that the branch and bound can solve PR sub-problems with certain scales and the partial rescheduling procedure developed can greatly improve the stability of schedule with little sacrifice in efficiency and provide a reasonable trade-off between solution quality and computational cost.

You might also be interested in these eBooks
Advanced Manufacturing and Automation View Preview

Info:

Periodical:

Advanced Materials Research (Volume 1039)

Pages:

506-513

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.1039.506

Citation:

Cite this paper

Online since:

October 2014

Authors:

Ying Ying Yu, Bing Wang*

Keywords:

Bound, Branch, Branch and Bound, Efficiency, Machine Breakdown, Partial Rescheduling, Stability

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2014 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

* - Corresponding Author

References

[1] Feng Liu, Jian-Jun Wang and De-Li Yang: Solving single machine scheduling under disruption with discounted costs by quantum-inspired hybrid heuristics. Journal of Manufacturing Systems. 32(2013) 716-732.

DOI: 10.1016/j.jmsy.2013.04.002

Google Scholar

[2] Bing Wang, Xiaoping Lai and Lifeng Xi: Single-Machine Partial Rescheduling with Bi-criterion Based on Genetic Algorithm. Advances in Intelligent Computing. 3644(2005) 947-956.

DOI: 10.1007/11538059_98

Google Scholar

[3] Bing Wang, Xiaoying Hong: Rolling Partial Rescheduling Driven by Disruptions on Single-machine Based on Genetic Algorithm. IEEE Symposium on Computational Intelligence in Scheduling. (2007) 72-78.

DOI: 10.1109/scis.2007.367672

Google Scholar

[4] Hoogeveen H., Lente C., Tkindt V.: Rescheduling for new orders on a single machine with setup times. European Journal of Operational Research. 223(2012) 40-46.

DOI: 10.1016/j.ejor.2012.05.046

Google Scholar

[5] Nicholas G. Hall, Chris N. Potts.: Rescheduling for job unavailability. Operations research. 58(2010) 746-755.

DOI: 10.1287/opre.1090.0751

Google Scholar

[6] Aytug H., Lawley MA, McKay K., Mohan S., Uzsoy R: Executing production schedules in the face of uncertainties: a review and some future directions. European Journal of Operational Research. 161(2005) 86–110.

DOI: 10.1016/j.ejor.2003.08.027

Google Scholar

[7] Ouelhadj D, Petrovic S.: A survey of dynamic scheduling in manufacturing systems. Journal of Scheduling. 12(2009) 417–31.

DOI: 10.1007/s10951-008-0090-8

Google Scholar

[8] Patrick Moratori, Sanja Petrovic and Jose Antonio Vazquez-Rodriguez.: Match-up approaches to a dynamic rescheduling problem. International Journal of Production Research. 50(2012) 261-276.

DOI: 10.1080/00207543.2011.571458

Google Scholar

[9] Qi X, Bard JF, Yu G.: Disruption management for machine scheduling: the case of SPT schedules. International Journal of Production Economics. 103(2006) 166–84.

DOI: 10.1016/j.ijpe.2005.05.021

Google Scholar

[10] Sabuncuoglu, M. Bayiz.: Analysis of reactive scheduling problems in a job shop environment. European Journal of Operational Research. 126(2000) 567-586.

DOI: 10.1016/s0377-2217(99)00311-2

Google Scholar

[11] Wu, S.D., Storer, R.H., Chang, P.C.: One-machine Rescheduling Heuristics with Efficiency and Stability as Criteria. Computers & Operations Research. 20(1993) 1–14.

DOI: 10.1016/0305-0548(93)90091-v

Google Scholar

[12] M. R. Garey and D. S. Johnson.: Computers Intractability. Freeman, San Francisico, Calif, (1979).

Google Scholar

[13] J. C. Bean, J. R. Birge.: Match-up real-time scheduling. In Proceeding of the Symposium on Real Time Optimization in Automated Manufacturing Facilities / pp.197-212 NBS publication 724, National Bureau of Standards (1985).

Google Scholar

[14] J. C. Bean, J. R. Birge, J. Mittenehal, C. E. Noon.: Match-up scheduling with multiple resources, release dates and disruption. Operations Research. Operations research. 39(1991) 470-483.

DOI: 10.1287/opre.39.3.470

Google Scholar

[15] Chris N. Potts, Luk N. Van Wasscnhove: A branch and bound algorithm for the total weighted tardiness problem . Operations Research. 33(1985) 363-377.

DOI: 10.1287/opre.33.2.363

Google Scholar

[16] Jacques Carlier.: The one-machine sequencing problem. European Journal of Operational Research. 11(1982) 42-47.

DOI: 10.1016/s0377-2217(82)80007-6

Google Scholar

[17] I. M. Ovacik, R. Uzsoy.: Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times. International Journal of Production Research. 32(1994) 1243-1263.

DOI: 10.1080/00207549408956998

Google Scholar

© 2025 Trans Tech Publications Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies. For open access content, terms of the Creative Commons licensing CC-BY are applied.
Scientific.Net is a registered trademark of Trans Tech Publications Ltd.