IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v32y2004i2p145-153.html
   My bibliography  Save this article

Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming

Author

Listed:
  • Lee, Sang M.
  • Asllani, Arben A.

Abstract

Flexibility, speed, and efficiency are major challenges for operations managers in today's knowledge-intensive organizations. Such requirements are converted into three production scheduling criteria: (a) minimize the impact of setup times in flexible production lines when moving from one product to another, (b) minimize number of tardy jobs, and (c) minimize overall production time, or makespan, for a given set of products or services. There is a wide range of solution methodologies for such NP-hard scheduling problems. While mathematical programming models provide optimal solutions, they become too complex to model for large scheduling problems. Simultaneously, heuristic approaches are simpler and very often independent of the problem size, but provide "good" rather than optimal solutions. This paper proposes and compares two alternative solutions: 0-1 mixed integer linear programming and genetic programming. It also provides guidelines that can be used by practitioners in the process of selecting the appropriate scheduling methodology.

Suggested Citation

  • Lee, Sang M. & Asllani, Arben A., 2004. "Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming," Omega, Elsevier, vol. 32(2), pages 145-153, April.
    • Handle: RePEc:eee:jomega:v:32:y:2004:i:2:p:145-153
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305-0483(03)00132-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Tan, Keah-Choon & Narasimhan, Ram & Rubin, Paul A. & Ragatz, Gary L., 2000. "A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times," Omega, Elsevier, vol. 28(3), pages 313-326, June.
    2. Van Wassenhove, Luk N. & Baker, Kenneth R., 1982. "A bicriterion approach to time/cost trade-offs in sequencing," European Journal of Operational Research, Elsevier, vol. 11(1), pages 48-54, September.
    3. J. Wesley Barnes & Lawrence K. Vanston, 1981. "Scheduling Jobs with Linear Delay Penalties and Sequence Dependent Setup Costs," Operations Research, INFORMS, vol. 29(1), pages 146-160, February.
    4. Allahverdi, Ali, 2003. "The two- and m-machine flowshop scheduling problems with bicriteria of makespan and mean flowtime," European Journal of Operational Research, Elsevier, vol. 147(2), pages 373-396, June.
    5. Yano, Candace Arai & Kim, Yeong-Dae, 1991. "Algorithms for a class of single-machine weighted tardiness and earliness problems," European Journal of Operational Research, Elsevier, vol. 52(2), pages 167-178, May.
    6. Roslof, Janne & Harjunkoski, Iiro & Westerlund, Tapio & Isaksson, Johnny, 2002. "Solving a large-scale industrial scheduling problem using MILP combined with a heuristic procedure," European Journal of Operational Research, Elsevier, vol. 138(1), pages 29-42, April.
    7. Portmann, M. -C. & Vignier, A. & Dardilhac, D. & Dezalay, D., 1998. "Branch and bound crossed with GA to solve hybrid flowshops," European Journal of Operational Research, Elsevier, vol. 107(2), pages 389-400, June.
    8. Chen, Chuen-Lung & Bulfin, Robert L., 1993. "Complexity of single machine, multi-criteria scheduling problems," European Journal of Operational Research, Elsevier, vol. 70(1), pages 115-125, October.
    9. Peng Si Ow & Thomas E. Morton, 1989. "The Single Machine Early/Tardy Problem," Management Science, INFORMS, vol. 35(2), pages 177-191, February.
    10. Aytug, Haldun & Saydam, Cem, 2002. "Solving large-scale maximum expected covering location problems by genetic algorithms: A comparative study," European Journal of Operational Research, Elsevier, vol. 141(3), pages 480-494, September.
    11. R. G. Vickson, 1980. "Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine," Operations Research, INFORMS, vol. 28(5), pages 1155-1167, October.
    12. Walsh, William D., 1966. "The Diffusion of Technological Change in the Pennsylvania Pig Iron Industry, 1850–1870: A Summary," The Journal of Economic History, Cambridge University Press, vol. 26(4), pages 591-594, December.
    13. Rosser T. Nelson & Rakesh K. Sarin & Richard L. Daniels, 1986. "Scheduling with Multiple Performance Measures: The One-Machine Case," Management Science, INFORMS, vol. 32(4), pages 464-479, April.
    14. Neppalli, Venkata Ranga & Chen, Chuen-Lung & Gupta, Jatinder N. D., 1996. "Genetic algorithms for the two-stage bicriteria flowshop problem," European Journal of Operational Research, Elsevier, vol. 95(2), pages 356-373, December.
    15. Houpt, Stefan, 1998. "Location of Spanish integrated steel, 1880-1936," IFCS - Working Papers in Economic History.WH wh983303, Universidad Carlos III de Madrid. Instituto Figuerola.
    16. Koksalan, Murat & Burak Keha, Ahmet, 2003. "Using genetic algorithms for single-machine bicriteria scheduling problems," European Journal of Operational Research, Elsevier, vol. 145(3), pages 543-556, March.
    17. Van Wassenhove, Luc N. & Gelders, Ludo F., 1980. "Solving a bicriterion scheduling problem," European Journal of Operational Research, Elsevier, vol. 4(1), pages 42-48, January.
    18. Uttarayan Bagchi, 1989. "Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems," Operations Research, INFORMS, vol. 37(1), pages 118-125, February.
    19. Tzafestas, Spyros & Triantafyllakis, Alekos, 1993. "Deterministic scheduling in computing and manufacturing systems: a survey of models and algorithms," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 35(5), pages 397-434.
    20. Cenna, Ahmed Abu & Tabucanon, Mario T., 1991. "Bicriterion scheduling problem in a job shop with parallel processors," International Journal of Production Economics, Elsevier, vol. 25(1-3), pages 95-101.
    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. Nauss, Robert M., 2008. "Optimal sequencing in the presence of setup times for tow/barge traffic through a river lock," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1268-1281, June.
    2. Allahverdi, Ali & Ng, C.T. & Cheng, T.C.E. & Kovalyov, Mikhail Y., 2008. "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 985-1032, June.
    3. Martin, Clarence H, 2009. "A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming," Omega, Elsevier, vol. 37(1), pages 126-137, February.
    4. Melissa R. Bowers & Anurag Agarwal, 2007. "Fewer Equipment Changeovers for the Embroidery Process at Oxford Industries," Interfaces, INFORMS, vol. 37(6), pages 526-538, December.
    5. Chung, Ji-Won & Oh, Seog-Moon & Choi, In-Chan, 2009. "A hybrid genetic algorithm for train sequencing in the Korean railway," Omega, Elsevier, vol. 37(3), pages 555-565, June.

    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. Neppalli, Venkata Ranga & Chen, Chuen-Lung & Gupta, Jatinder N. D., 1996. "Genetic algorithms for the two-stage bicriteria flowshop problem," European Journal of Operational Research, Elsevier, vol. 95(2), pages 356-373, December.
    2. Hoogeveen, Han, 2005. "Multicriteria scheduling," European Journal of Operational Research, Elsevier, vol. 167(3), pages 592-623, December.
    3. Nagar, Amit & Haddock, Jorge & Heragu, Sunderesh, 1995. "Multiple and bicriteria scheduling: A literature survey," European Journal of Operational Research, Elsevier, vol. 81(1), pages 88-104, February.
    4. Vincent T’kindt & Karima Bouibede-Hocine & Carl Esswein, 2007. "Counting and enumeration complexity with application to multicriteria scheduling," Annals of Operations Research, Springer, vol. 153(1), pages 215-234, September.
    5. Loukil, T. & Teghem, J. & Tuyttens, D., 2005. "Solving multi-objective production scheduling problems using metaheuristics," European Journal of Operational Research, Elsevier, vol. 161(1), pages 42-61, February.
    6. Subhash C. Sarin & Divya Prakash, 2004. "Equal Processing Time Bicriteria Scheduling on Parallel Machines," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 227-240, September.
    7. Dhaenens-Flipo, Clarisse, 2001. "A bicriterion approach to deal with a constrained single-objective problem," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 93-101, December.
    8. Erenay, Fatih Safa & Sabuncuoglu, Ihsan & Toptal, Aysegül & Tiwari, Manoj Kumar, 2010. "New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs," European Journal of Operational Research, Elsevier, vol. 201(1), pages 89-98, February.
    9. Wang, Ji-Bo & Xia, Zun-Quan, 2007. "Single machine scheduling problems with controllable processing times and total absolute differences penalties," European Journal of Operational Research, Elsevier, vol. 177(1), pages 638-645, February.
    10. Sayin, Serpil & Karabati, Selcuk, 1999. "A bicriteria approach to the two-machine flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 113(2), pages 435-449, March.
    11. Chen, Rubing & Yuan, Jinjiang & Ng, C.T. & Cheng, T.C.E., 2021. "Single-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterion," European Journal of Operational Research, Elsevier, vol. 293(1), pages 79-92.
    12. Koksalan Kondakci, Suna & Bekiroglu, Tuncay, 1997. "Scheduling with bicriteria: total flowtime and number of tardy jobs," International Journal of Production Economics, Elsevier, vol. 53(1), pages 91-99, November.
    13. Mosheiov, Gur, 2005. "Minimizing total completion time and total deviation of job completion times from a restrictive due-date," European Journal of Operational Research, Elsevier, vol. 165(1), pages 20-33, August.
    14. Kate, H.A. ten & Wijngaard, J. & Zijm, W.H.M., 1995. "Minimizing weighted total earliness, total tardiness and setup costs," Research Report 95A37, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    15. Ventura, Jose A. & Radhakrishnan, Sanjay, 2003. "Single machine scheduling with symmetric earliness and tardiness penalties," European Journal of Operational Research, Elsevier, vol. 144(3), pages 598-612, February.
    16. Gerardo Minella & Rubén Ruiz & Michele Ciavotta, 2008. "A Review and Evaluation of Multiobjective Algorithms for the Flowshop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 451-471, August.
    17. Chung‐Lun Li & Edward C. Sewell & T. C. E. Cheng, 1995. "Scheduling to minimize release‐time resource consumption and tardiness penalties," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(6), pages 949-966, September.
    18. Murat Güngör, 2016. "A note on efficient sequences with respect to total flow time and number of tardy jobs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(4), pages 346-348, June.
    19. Cheng, T. C. E. & Oguz, C. & Qi, X. D., 1996. "Due-date assignment and single machine scheduling with compressible processing times," International Journal of Production Economics, Elsevier, vol. 43(2-3), pages 107-113, June.
    20. George Li, 1997. "Single machine earliness and tardiness scheduling," European Journal of Operational Research, Elsevier, vol. 96(3), pages 546-558, February.

    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:eee:jomega:v:32:y:2004:i:2:p:145-153. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    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.