Single machine lot scheduling with optional job-rejection
- PDF / 281,896 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 27 Downloads / 209 Views
Single machine lot scheduling with optional job-rejection Baruch Mor1
· Gur Mosheiov2
· Dana Shapira3
Accepted: 18 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We consider single machine lot scheduling problems. A number of customer orders of different sizes may be processed in the same lot. Splitting orders between consecutive lots is allowed. Three scheduling measures are considered: makespan, total completion time and total weighted completion time. In all cases, the goal is minimizing the relevant scheduling measure, subject to an upper bound on the total permitted rejection cost. All three problems studied here are NP-hard. We introduce efficient pseudo-polynomial dynamic programming algorithms for all cases. Our numerical tests indicate that the proposed algorithms can solve efficiently large-size problems. Keywords Lot scheduling · Single machine · Order rejection · Dynamic programming
1 Introduction In a recent paper, Zhang et al. (2019) solve a single machine lot scheduling problem to minimize total weighted completion time. Lot scheduling is a production setting where a number of customer orders (jobs) of different sizes are processed in the same lot. The total size of orders processed in one lot cannot exceed the lot size. All the lots are assumed to have a common size, and an identical processing time, which is independent of the total size of the orders processed in the lot. Hou et al. (2014), Zhang et al. (2019) and Mor (2020) mention a number of applications of lot scheduling, including integrated circuit tests in a semiconductor factory, glue production with a heated container, stone wash processing of textile products, and digital advertisement display in the e-commerce industry. An illustrative trivial example is the lot scheduling problem that the manager of a pizza fast food restau-
B
Gur Mosheiov [email protected]
1
Department of Economics and Business Administration, Ariel University, 40700 Ariel, Israel
2
School of Business Administration, The Hebrew University, 91905 Jerusalem, Israel
3
Department of Computer Science, Ariel University, 40700 Ariel, Israel
123
Journal of Combinatorial Optimization
rant faces. The manager receives orders from different customers, each may contain a number of pizzas of varying sizes (e.g., regular, medium, large and extra-large). The single oven can handle orders up to its capacity. It is possible that a number of orders will be processed simultaneously (i.e., in one lot), or that one order will be processed along a number of consecutive lots. Completed orders are delivered to customers as soon as possible. Both Hou et al. (2014) and Zhang et al. (2019) consider the setting that a single order can be split between two consecutive lots. Splitting is relevant when the size of the next order to be processed exceeds the remaining capacity of the lot. Hou et al. (2014) solved the problem of minimizing total completion time, and, as mentioned, Zhang et al. (2019) solved the weighted version. Both papers
Data Loading...
