Abstract
A proportionate flowshop is a special case of the classical flowshop, where the job processing times are machine-independent. We study the problem of minimizing the number of early jobs in this machine setting. This objective function has hardly been investigated on a single machine, and never on a flowshop. We introduce an efficient iterative solution algorithm. In each iteration, a single job is moved to the first position (and is added to the set of early jobs), and the remaining jobs are rescheduled such that the maximum earliness is minimized. The algorithm guarantees an optimal solution in O(n3) time, where n is the number of jobs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Gerstl E, Mor B and Mosheiov G (2014). A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop. Information Processing Letters. Available online 16 September doi:10.1016/j.ipl.2014.09.004.
Huang RH and Yang CL (2007). Single-machine scheduling to minimize the number of early jobs. Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management, 2–4 December, pp. 955, 957, doi: 10.1109/IEEM.2007.4419333.
Jackson JR (1955). Scheduling a production line to minimize maximum tardiness. Research Report 43, Management Science Research Project, University of California, Los Angeles, CA.
Kanet JJ (1986). Tactically delayed versus non-delay scheduling: An experimental investigation. European Journal of Operational Research 24 (1): 99–105.
Monden Y (2011). Toyota Production System: An Integrated Approach to Just-In-Time. CRC Press, Taylor and Francis Group: Boca Raton, FL.
Moore JM (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science 15 (1): 102–109.
Mor B and Mosheiov G (2014a). Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents. Journal of the Operational Research Society 65 (1): 151–157.
Mor B and Mosheiov G (2014b). A note: Minimizing maximum earliness on a proportionate flowshop. Information Processing Letters. Available online 2 October, doi: 10.1016/j.ipl.2014.09.023.
Panwalkar SS, Smith ML and Koulamas C (2013). Review of ordered and proportionate flow shop scheduling research. Naval Research Logistics 60 (1): 46–55.
Pinedo ML (2012). Scheduling: Theory, Algorithms and Systems. 4th edn. Springer: New York.
Schaller J and Valente JMS (2012). An evaluation of heuristics for scheduling a non-delay permutation flow shop with family setups to minimize total earliness and tardiness. Journal of the Operational Research Society 64 (6): 805–816.
Shabtay D (2012). The just-in-time scheduling problem in a flow-shop scheduling system. European Journal of Operational Research 216 (3): 521–532.
Shakhlevich N, Hoogeveen H and Pinedo M (1998). Minimizing total weighted completion time in a proportionate flow shop. Journal of Scheduling 1 (3): 157–168.
Sprecher A, Kolisch R and Drexl A (1995). Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem. European Journal of Operational Research 80 (1): 94–102.
Acknowledgements
This research was supported by the Israel Science Foundation (grant No. 1286/14). The second author was supported in part by the Recanati Fund of The School of Business Administration, and Charles I. Rosen Chair of Management, The Hebrew University, Jerusalem, Israel.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mor, B., Mosheiov, G. Minimizing the number of early jobs on a proportionate flowshop. J Oper Res Soc 66, 1426–1429 (2015). https://doi.org/10.1057/jors.2014.112
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2014.112