IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v42y1995i5p737-755.html
   My bibliography  Save this article

Scheduling target illuminators in naval battle‐group anti‐air warfare

Author

Listed:
  • Hanif D. Sherali
  • Youngho Lee
  • Donald D. Boyer

Abstract

We schedule a set of illuminators (homing devices) to strike a set of targets using surface‐to‐air missiles in a naval battle. The task is viewed as a production floor shop scheduling problem of minimizing the total weighted flow time, subject to time‐window job availability and machine downtime side constraints. A simple algorithm based on solving assignment problems is developed for the case when all the job processing times are equal and the data are all integer. For the general case of scheduling jobs with unequal processing times, we develop two alternate formulations and analyze their relative strengths by comparing their respective linear programming relaxations. We select the better formulation in this comparison and exploit its special structures to develop several effective heuristic algorithms that provide good‐quality solutions in real time; this is an essential element for use by the Navy. © 1995 John Wiley & Sons, Inc.

Suggested Citation

  • Hanif D. Sherali & Youngho Lee & Donald D. Boyer, 1995. "Scheduling target illuminators in naval battle‐group anti‐air warfare," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(5), pages 737-755, August.
    • Handle: RePEc:wly:navres:v:42:y:1995:i:5:p:737-755
    DOI: 10.1002/1520-6750(199508)42:53.0.CO;2-T
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199508)42:53.0.CO;2-T
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199508)42:53.0.CO;2-T?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Sherali, Hanif D., 1988. "Bounds on penalties for dummy arcs in transportation networks," European Journal of Operational Research, Elsevier, vol. 36(3), pages 353-359, September.
    2. Marshall L. Fisher, 1981. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 27(1), pages 1-18, January.
    3. C. N. Potts, 1980. "Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times," Operations Research, INFORMS, vol. 28(6), pages 1436-1441, December.
    4. Blazewicz, Jacek & Dror, Moshe & Weglarz, Jan, 1991. "Mathematical programming formulations for machine scheduling: A survey," European Journal of Operational Research, Elsevier, vol. 51(3), pages 283-300, April.
    5. Roy E. Marsten, 1974. "An Algorithm for Large Set Partitioning Problems," Management Science, INFORMS, vol. 20(5), pages 774-787, January.
    6. Grabowski, J. & Nowicki, E. & Zdrzalka, S., 1986. "A block approach for single-machine scheduling with release dates and due dates," European Journal of Operational Research, Elsevier, vol. 26(2), pages 278-285, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Orhan Karasakal & Nur Evin Özdemirel & Levent Kandiller, 2011. "Anti‐ship missile defense for a naval task group," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(3), pages 304-321, April.
    2. Moustafa Elshafei & Hanif D. Sherali & J. Cole Smith, 2004. "Radar pulse interleaving for multi‐target tracking," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(1), pages 72-94, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    2. Federico Alonso-Pecina & José Alberto Hernández & José Maria Sigarreta & Nodari Vakhania, 2020. "Fast Approximation for Scheduling One Machine," Mathematics, MDPI, vol. 8(9), pages 1-18, September.
    3. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    4. Egon Balas & Alkis Vazacopoulos, 1998. "Guided Local Search with Shifting Bottleneck for Job Shop Scheduling," Management Science, INFORMS, vol. 44(2), pages 262-275, February.
    5. Joao António Noivo & Helena Ramalhinho-Lourenço, 1998. "Solving two production scheduling problems with sequence-dependent set-up times," Economics Working Papers 338, Department of Economics and Business, Universitat Pompeu Fabra.
    6. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    7. M Diaby & A L Nsakanda, 2006. "Large-scale capacitated part-routing in the presence of process and routing flexibilities and setup costs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(9), pages 1100-1112, September.
    8. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    9. Mutsunori Yagiura & Toshihide Ibaraki & Fred Glover, 2004. "An Ejection Chain Approach for the Generalized Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 133-151, May.
    10. Wenda Zhang & Jason J. Sauppe & Sheldon H. Jacobson, 2021. "An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1091-1102, July.
    11. Biber Nurit & Mor Baruch & Schlissel Yitzhak & Shapira Dana, 2023. "Lot scheduling involving completion time problems on identical parallel machines," Operational Research, Springer, vol. 23(1), pages 1-29, March.
    12. S Bilgin & M Azizoǧlu, 2006. "Capacity and tool allocation problem in flexible manufacturing systems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(6), pages 670-681, June.
    13. Weijun Xie & Yanfeng Ouyang & Sze Chun Wong, 2016. "Reliable Location-Routing Design Under Probabilistic Facility Disruptions," Transportation Science, INFORMS, vol. 50(3), pages 1128-1138, August.
    14. Peter Francis & Karen Smilowitz & Michal Tzur, 2006. "The Period Vehicle Routing Problem with Service Choice," Transportation Science, INFORMS, vol. 40(4), pages 439-454, November.
    15. Gueret, Christelle & Jussien, Narendra & Prins, Christian, 2000. "Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems," European Journal of Operational Research, Elsevier, vol. 127(2), pages 344-354, December.
    16. Park, Moon-Won & Kim, Yeong-Dae, 2000. "A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints," European Journal of Operational Research, Elsevier, vol. 123(3), pages 504-518, June.
    17. Shangyao Yan & Chun-Ying Chen & Chuan-Che Wu, 2012. "Solution methods for the taxi pooling problem," Transportation, Springer, vol. 39(3), pages 723-748, May.
    18. Jenny Carolina Saldana Cortés, 2011. "Programación semidefinida aplicada a problemas de cantidad económica de pedido," Documentos CEDE 8735, Universidad de los Andes, Facultad de Economía, CEDE.
    19. Sun Lee, Ik & Yoon, S.H., 2010. "Coordinated scheduling of production and delivery stages with stage-dependent inventory holding costs," Omega, Elsevier, vol. 38(6), pages 509-521, December.
    20. Jordan, Carsten & Drexl, Andreas, 1993. "A comparison of logic and mixed-integer programming solvers for batch sequencing with sequence-dependent setups," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 322, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:42:y:1995:i:5:p:737-755. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.