Order acceptance and scheduling in capacitated job shops

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Abstract

We consider a capacitated job shop problem with order acceptance. This research is motivated by the management of a research and development project pipeline for a company in the agricultural industry whose success depends on regularly releasing new and innovative products. The setting requires the consideration of multiple problem characteristics not commonly considered in scheduling research. Each job has a given release and due date and requires the execution of an individual sequence of operations on different machines (job shop). There is a set of machines of fixed capacity, each of which can process multiple operations simultaneously. Given that typically only a small percentage of jobs yield a commercially viable product, the number of potential jobs to schedule is in the order of several thousands. Due to limited capacity, not all jobs can be started. Instead, the objective is to maximize the throughput. Namely, to start as many jobs as possible. We present a Mixed Integer Programming (MIP) formulation of this problem and study how resource capacity and the option to delay jobs can impact research and development throughput. We show that the MIP formulation can prove optimality even for very large instances with less restrictive capacity constraints, while instances with a tight capacity are more challenging to solve.

Details

Original languageEnglish
Title of host publicationOperations Research Proceedings 2023
EditorsGuido Voigt, Malte Fliedner, Knut Haase, Wolfgang Brüggemann, Kai Hoberg, Joern Meissner
Place of PublicationHamburg
PublisherSpringer, Cham
Pages341–347
Number of pages7
ISBN (electronic)978-3-031-58405-3
ISBN (print)978-3-031-58407-7
Publication statusPublished - 23 Jul 2025
Peer-reviewedYes

Publication series

SeriesLecture Notes in Operations Research
ISSN2731-040X

External IDs

ORCID /0000-0002-5869-0425/work/188859639
ORCID /0000-0003-4711-2184/work/188860319
ORCID /0000-0003-0753-0517/work/188860444
Mendeley 60f81a8d-492f-3728-8906-5ea3b9f51890
unpaywall 10.1007/978-3-031-58405-3_44
Scopus 105011683531

Keywords

Research priority areas of TU Dresden

DFG Classification of Subject Areas according to Review Boards

Subject groups, research areas, subject areas according to Destatis

Keywords

  • Capacity planning, OR in agriculture, Scheduling