Scheduling has turned out to be a fundamental activity for both production and service organizations. As competitive markets emerge, Just-In-Time (JIT) production has obtained more importance as a way of rapidly responding to continuously changing market forces. Due to their realistic assumptions, job shop production environments have gained much research effort among scheduling researchers. This research develops exact and heuristic methods and algorithms to solve the job shop scheduling problem when the objective is to minimize both earliness and tardiness costs over a common due date. The objective function of minimizing earliness and tardiness costs captures the essence of the JIT approach in job shops. A dynamic programming procedure is developed to solve smaller instances of the problem, and a Multi-Agent Systems approach is developed and implemented to solve the problem for larger instances since this problem is known to be NP-Hard in a strong sense. A combinational auction-based approach using a Mixed-Integer Linear Programming (MILP) model to construct and evaluate the bids is proposed. The results showed that the proposed combinational auction-based algorithm is able to find optimal solutions for problems that are balanced in processing times across machines. A price discrimination process is successfully implemented to deal with unbalanced problems. The exact and heuristic procedures developed in this research are the first steps to create a structured approach to handle this problem and as a result, a set of benchmark problems will be available to the scheduling research community.
","abstract_html":"<p>Scheduling has turned out to be a fundamental activity for both production and service organizations. As competitive markets emerge, Just-In-Time (JIT) production has obtained more importance as a way of rapidly responding to continuously changing market forces. Due to their realistic assumptions, job shop production environments have gained much research effort among scheduling researchers. This research develops exact and heuristic methods and algorithms to solve the job shop scheduling problem when the objective is to minimize both earliness and tardiness costs over a common due date. The objective function of minimizing earliness and tardiness costs captures the essence of the JIT approach in job shops. A dynamic programming procedure is developed to solve smaller instances of the problem, and a Multi-Agent Systems approach is developed and implemented to solve the problem for larger instances since this problem is known to be NP-Hard in a strong sense. A combinational auction-based approach using a Mixed-Integer Linear Programming (MILP) model to construct and evaluate the bids is proposed. The results showed that the proposed combinational auction-based algorithm is able to find optimal solutions for problems that are balanced in processing times across machines. A price discrimination process is successfully implemented to deal with unbalanced problems. The exact and heuristic procedures developed in this research are the first steps to create a structured approach to handle this problem and as a result, a set of benchmark problems will be available to the scheduling research community.</p>","abstract_has_math":false,"creators":["Bedoya-Valencia, Leonardo"],"institution":null,"degree_name":"Doctor of Philosophy (PhD)","degree_level":"Dissertation","degree_discipline":"Engineering Management & Systems Engineering","degree_department":null,"school":null,"contributors":["Ghaith Rabadi","Andres Sousa-Poza","Resit Unal","Ali Ardalan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007-01-01T08:00:00Z","date_published":"2007-01-01T08:00:00Z","updated_at":"2026-07-24T03:34:18Z","subjects":["Common due date","Earliness","Job shop scheduling","Scheduling","Tardiness","Industrial Engineering","Operational Research"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["9780549320463"],"render_values":[{"text":"9780549320463","href":null,"code":true}]}]},"links":{"outbound_url":"https://digitalcommons.odu.edu/emse_etds/51","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ghaith Rabadi","Andres Sousa-Poza","Resit Unal","Ali Ardalan"]},{"key":"dc:creator","label":"Author","values":["Bedoya-Valencia, Leonardo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2019-03-14T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering Management & Systems Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Common due date","Earliness","Job shop scheduling","Scheduling","Tardiness","Industrial Engineering","Operational Research"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["9780549320463","https://digitalcommons.odu.edu/emse_etds/51"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Scheduling has turned out to be a fundamental activity for both production and service organizations. As competitive markets emerge, Just-In-Time (JIT) production has obtained more importance as a way of rapidly responding to continuously changing market forces. Due to their realistic assumptions, job shop production environments have gained much research effort among scheduling researchers. This research develops exact and heuristic methods and algorithms to solve the job shop scheduling problem when the objective is to minimize both earliness and tardiness costs over a common due date. The objective function of minimizing earliness and tardiness costs captures the essence of the JIT approach in job shops. A dynamic programming procedure is developed to solve smaller instances of the problem, and a Multi-Agent Systems approach is developed and implemented to solve the problem for larger instances since this problem is known to be NP-Hard in a strong sense. A combinational auction-based approach using a Mixed-Integer Linear Programming (MILP) model to construct and evaluate the bids is proposed. The results showed that the proposed combinational auction-based algorithm is able to find optimal solutions for problems that are balanced in processing times across machines. A price discrimination process is successfully implemented to deal with unbalanced problems. The exact and heuristic procedures developed in this research are the first steps to create a structured approach to handle this problem and as a result, a set of benchmark problems will be available to the scheduling research community.
"]},{"key":"dc:title","label":"Title","values":["Exact and Heuristic Algorithms for the Job Shop Scheduling Problem with Earliness and Tardiness Over a Common Due Date"]}]}],"canonical_facts":{"dc:contributor":["Ghaith Rabadi","Andres Sousa-Poza","Resit Unal","Ali Ardalan"],"dc:creator":["Bedoya-Valencia, Leonardo"],"dc:date.available":["2019-03-14T07:00:00Z"],"dc:description.abstract":["Scheduling has turned out to be a fundamental activity for both production and service organizations. As competitive markets emerge, Just-In-Time (JIT) production has obtained more importance as a way of rapidly responding to continuously changing market forces. Due to their realistic assumptions, job shop production environments have gained much research effort among scheduling researchers. This research develops exact and heuristic methods and algorithms to solve the job shop scheduling problem when the objective is to minimize both earliness and tardiness costs over a common due date. The objective function of minimizing earliness and tardiness costs captures the essence of the JIT approach in job shops. A dynamic programming procedure is developed to solve smaller instances of the problem, and a Multi-Agent Systems approach is developed and implemented to solve the problem for larger instances since this problem is known to be NP-Hard in a strong sense. A combinational auction-based approach using a Mixed-Integer Linear Programming (MILP) model to construct and evaluate the bids is proposed. The results showed that the proposed combinational auction-based algorithm is able to find optimal solutions for problems that are balanced in processing times across machines. A price discrimination process is successfully implemented to deal with unbalanced problems. The exact and heuristic procedures developed in this research are the first steps to create a structured approach to handle this problem and as a result, a set of benchmark problems will be available to the scheduling research community.
"],"dc:identifier":["9780549320463","https://digitalcommons.odu.edu/emse_etds/51"],"dc:subject":["Common due date","Earliness","Job shop scheduling","Scheduling","Tardiness","Industrial Engineering","Operational Research"],"dc:title":["Exact and Heuristic Algorithms for the Job Shop Scheduling Problem with Earliness and Tardiness Over a Common Due Date"],"thesis:degree_discipline":["Engineering Management & Systems Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-24T03:34:18Z"}