A Batching Machine Model for Lot Scheduling on a Single Machine

被引：0
|
作者：
Kovalyov, Mikhail Y. [1 ]
机构：
[1] Natl Acad Sci Belarus, United Inst Informat Problems, Surganova 6, Minsk 220012, BELARUS
来源：
FOUNDATIONS OF COMPUTING AND DECISION SCIENCES | 2018年 / 43卷 / 01期
关键词：
scheduling; lot-sizing; single machine; batching machine; polynomial time algorithm;
D O I：
10.1515/fcds-2018-0003
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
A recently introduced lot scheduling problem is considered. It is to find a partition of jobs of n orders into lots and to sequence these lots on a single machine so that the total average completion time of the orders is minimized. A simple O(n log n) time algorithm is presented for this problem in the literature, with a relatively sophisticated proof of its optimality. We show that modeling this problem as a classic batching machine problem makes its optimal solution obvious.
引用
收藏
页码：37 / 40
页数：4
相关论文
共 50 条
  • [1] Lot scheduling on a single machine
    Hou, Yung-Tsung
    Yang, Dar-Li
    Kuo, Wen-Hung
    INFORMATION PROCESSING LETTERS, 2014, 114 (12) : 718 - 722
  • [2] Scheduling a flexible batching machine
    Fan, Baoqiang
    Gu, Jianzhong
    Tang, Guochun
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2007, 4508 : 91 - +
  • [3] Scheduling jobs on a flexible batching machine: Model, complexity and algorithms
    Fan, Baoqiang
    Tang, Guochun
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2006, 3959 : 118 - 127
  • [4] Scheduling a single semi-continuous batching machine
    Tang, Lixin
    Zhao, Yufang
    OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2008, 36 (06): : 992 - 1004
  • [5] A Scheduling Problem on a Single Batching Machine with Batch Deliveries
    Gong Hua
    Tang Lixin
    2011 30TH CHINESE CONTROL CONFERENCE (CCC), 2011, : 2175 - 2179
  • [6] Single-Batching-Machine Scheduling Problem with Deterioration and Release Time
    Gong, Hua
    Tang, Lixin
    2008 CHINESE CONTROL AND DECISION CONFERENCE, VOLS 1-11, 2008, : 1061 - 1064
  • [7] Single-machine lot scheduling with variable lot processing times
    Mor, Baruch
    ENGINEERING OPTIMIZATION, 2021, 53 (02) : 321 - 334
  • [8] An Improved Heuristic for Single Machine Lot Scheduling Problem
    Zheng, Feifeng
    Jin, Kaiyuan
    IFAC PAPERSONLINE, 2019, 52 (13): : 217 - 222
  • [9] Lot scheduling on a single machine to minimize the (weighted) number of tardy orders
    Mor, Baruch
    Mosheiov, Gur
    Shapira, Dana
    INFORMATION PROCESSING LETTERS, 2020, 164 (164)
  • [10] Bi-objective scheduling on a restricted batching machine
    Cabo, Marta
    Luis Gonzalez-Velarde, Jose
    Possani, Edgar
    Rios Solis, Yasmin A.
    COMPUTERS & OPERATIONS RESEARCH, 2018, 100 : 201 - 210
12345